Algorithm7 [백준] 2162번 선분 그룹 - CCW & Union-Find 선분그룹 ccw 알고리즘과 union find를 이용해 해결할 수 있는 문제입니다. ccw알고리즘이란 세 점이 주어졌을 때 세 점이 이루는 각도를 벡터의 외적을 통해 구하는 알고리즘이고, union find는 합집합을 효율적으로 수행하는 알고리즘입니다. 아래 문제들을 먼저 해결하면 2162번 선분 그룹을 쉽게 해결할 수 있습니다.11758번 CCW17386번 선분 교차 117387번 선분 교차 21717번 집합의 표현CCW CCW는 점 a, b, c가 있을 때 a -> b -> c로 이어지는 선분들이 어느 방향으로 꺾이는지 판별할 수 있는 알고리즘입니다. CCW를 이해하기 위해서는 먼저 벡터와 외적에 대한 이해가 필요합니다. 이 문제에서는 2차원 벡터를 다룹니다. 2차원 벡터는 좌표 평면 상에서 방향과.. 2025. 6. 21. [백준] 14003번 가장 긴 증가하는 부분 수열 5 - LIS 역추적 들어가며 오늘은 LIS 역추적 문제를 해결했다. LIS란 Longest Increasing Subsequence. 가장 긴 증가하는 부분 수열이다. 이전에 LIS의 길이만 구하면 되는 문제를 풀었었는데 이번 문제는 길이와 최종 LIS까지 구해야 하는 문제이다. 풀이 LIS의 길이만 구하는 방법은 다음과 같다.변수 num에 입력을 받는다.num이 배열의 가장 끝 원소보다 크다면 배열의 끝에 삽입한다.그렇지 않다면 처음으로 num 이상의 값이 나오는 인덱스를 num으로 교체한다.배열은 오름차순 정렬이기 때문에 이분탐색을 사용해 시간을 줄일 수 있다.입력이 끝날 때까지 1 ~ 3을 반복한다.배열의 길이를 출력한다. 최종 LIS의 상태를 알기 위해서는 배열이 수정된 기록과 배열에 삽입된 순서를 알아야 한다. 경.. 2025. 6. 18. [Templates] Topological sort 위상 정렬 들어가며 오늘은 위상 정렬 알고리즘, 그중에서도 Kahn's algorithm을 템플릿 코드 형태로 작성해 보겠습니다.위상 정렬 위상정렬은 DAG(Directed Acyclic Graph) 즉, 사이클이 없는 유향 그래프의 각 노드들을 방향을 거스르지 않게 나열하는 것을 말합니다. 쉽게 말하면 어떤 노드 i는 반드시 노드 j의 뒤에 와야 한다는 조건이 복수개 주어졌을 때 이를 만족하는 형태로 정렬하는 것입니다. 자세한 내용은 위키를 참조하세요. 위상 정렬을 수행하려면 먼저 유향 그래프를 구성해야 합니다. 문제에서 "A 작업을 먼저 수행해야 B 작업을 수행할 수 있다"는 조건이 주어졌다면, 이는 A → B 방향의 간선을 그래프에 추가하라는 의미입니다. 즉, 선수 조건은 방향이 있는 간선으로 표현되며, 이러.. 2025. 5. 31. [Templates] Dijkstra's algorithm 다익스트라 알고리즘 들어가며 오늘은 PS에서 흔히 쓰이는 다익스트라 알고리즘을 쉽게 쓸 수 있도록 정리해 보았습니다. 앞으로 가능하면 하루에 하나씩 자주 쓰이는 알고리즘을 템플릿 코드 형태로 정리해보려고 합니다.다익스트라 알고리즘 다익스트라 알고리즘은 V개의 노드로 이루어진 그래프와 시작점 root가 주어졌을 때, root로부터 모든 노드까지의 최단거리를 구하는 알고리즘입니다. 음의 가중치 또는 음의 사이클을 포함하는 그래프에서는 사용할 수 없습니다. 입력으로는 노드의 개수 V, 시작점 root, 최단거리를 저장할 배열 distance, 인접리스트 형태의 graph를 받습니다. 반환값은 따로 없고 입력으로 받은 distance배열에 최단거리를 저장합니다. 아래 코드는 0-based index를 기준으로 작성되었습니다.// .. 2025. 5. 30. [백준] 15965번 K번째 소수: 에라토스테네스의 체 최적화 해보기 - C++ 들어가며 알고리즘 문제해결을 하다 보면 소수와 관련한 문제를 자주 만나볼 수 있습니다. 오늘은 소수판별법 중 하나인 에라토스테네스의 체를 몇 가지 방법으로 최적화해보겠습니다.K번째 소수 자연수 K가 주어지면 K번째 소수를 출력하는 간단한 문제이지만 K의 범위가 최대 50만이기 때문에 시간초과가 나오기 쉬운 문제입니다.풀이방법 기본적인 에라토스테네스의 체 알고리즘은 다음과 같습니다. 소수의 배수들을 제거해 나가면서 소수의 후보를 줄이는 방식입니다.#include #include using namespace std;int main(){ vector prime(500001); // 소수를 담는 배열. 처음엔 비어있음. int prime_num = 1; // 첫번째 소수를 입력할 차례. int limit = 7.. 2025. 2. 14. [코테] 코딩 테스트 사전 준비 들어가며 코딩테스트를 준비하면서 책을 하나 샀습니다. 이정표 없이 사이트에서 문제만 푸는 것은 좀 비 효율적인 것 같아서 저에게 방향을 제시해 줄 것이 필요하다고 생각해서 구매했는데 나쁘지 않은 것 같습니다. 완전 정독까지 파이팅~!코딩 테스트를 준비하기 전에합격자가 꼭 되고 싶은 여러분타인의 풀이를 보면 사고를 넓힐 수 있다.나만의 테스트 케이스를 추가하는 건 좋은 알고리즘을 생각할 때 도움이 된다.아는 것과 모르는 것을 명확하게첫 번째, 기록하라.두 번째, 시험 보듯 공부하라.세 번째, 짧은 시간 공부해서는 절대 코딩 테스트를 통과할 수 없다.네 번째, 나만의 언어로 요약하라.코딩 테스트 효율적으로 준비하기문제 분석 연습하기첫 번째, 문제를 쪼개서 분석하라.두 번째 제약 사항을 파악하고 테스트 케이스.. 2024. 9. 4. 이전 1 2 다음
