본문 바로가기

알고리즘/Baekjoon

 (196)
최소신장트리. [1774] [1. 문제 설명] 이미 연결된 간선이 존재하고, 아직 연결되지 않은 정점을 연결해야 할 때, 필요한 최소길이를 구한다. 정점은 2차원 평면 좌표형태로 주어진다. [2. 풀이 접근] 먼저 피타고라스 정리를 이용하여 모든 edge 의 길이를 구하도록 한다. 정점의 개수가 N 이므로, 전체 edge 의 개수는 N(N-1)/2 이다. 문제에서 주어진 정점의 최대 개수는 1000 이므로, edge 를 위한 메모리는 충분하다. 여기서 주의할 점은 이미 연결 된 edge 에 대한 처리이다. 이 문제의 답을 구하기 위해서는 최소신장트리를 만들고, 이미 연결된 edge 의 길이를 빼서 만들 수 있을 것 같지만, 이미 연결된 edge 를 포함해서 만들어야 하는 부분이 까다롭다. 예를들어, 아래 그림에서 실선은 문제에서 ..
최소신장트리. [1197] [1. 문제 설명] 그래프가 주어졌을 때, 최소 신장 트리의 가중치를 출력한다. [2. 풀이 접근] A. 크루스칼 알고리즘 edge 를 가중치를 기준으로 하여 오름차순 정렬한다. 가중치가 낮은 edge 부터 tree 에 추가하도록 한다. => edge 추가로 인해 cycle 이 발생하는 경우, 이번 edge 는 버리도록 한다. tree 에 추가된 edge 개수가 정점의 개수 - 1 일 때 까진 반복한다.\ => cycle 여부 판별을 union-find 를 이용하면 전체 알고리즘은 정렬 시간에 가장 큰 영향을 받는다. (최적의 union-find 는 거의 상수 시간으로 동작 하기 때문이다.) => 시간복잡도: O(ElogE) B. 프림 알고리즘 임의의 정점에서 시작한다. (보통 번호가 가장 빠른 노드) ..
Meet in the middle. [1450] [1. 문제 설명] N 개의 물건을 최대 C 만큼의 무게를 넣을 수 있는 가방에 넣을 수 있는 경우의 수를 구한다. N 은 30 이하의 자연수 C 는 10억 이하의 자연수 [2. 풀이 접근] 이 문제는 동적 계획법으로 풀이가 가능하다. 단, 완전 탐색 중 i 번째 물건을 포함할지 말지를 결정할 때, 아래에 대해서 메모이제이션 할 수 있어야 한다. i번째 물건의 index 현재까지 누적된 무게 그러나 문제에서 C 는 최대 10억이 될 수 있으므로, 메모리가 부족하여, 다른 접근법이 필요하다. 다시 완전 탐색으로 돌아와서 생각해보면, 문제는 탐색의 개수가 너무 많다는 것이다. 재귀의 각 단계에서 i번째 물건 선택여부가 존재하니, 총 탐색 개수는 2N 이다. N 이 최대 30이니, 대략 10억 정도 된다. 여..
투 포인터 .[1644] [1. 문제 설명] 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구한다. (N https://testkernelv2.tistory.com/378 소수 리스트를 구할 수 있으므로, 부분 합을 구하면 나머지는 여타 다른 문제들과 비슷하다. head 와 tail 을 옮겨가면서 주어진 자연수가 되는지 확인하는 것이다. [3. 코드]
투 포인터. [1806] [1. 문제 설명] 10,000 이하의 자연수로 이루어진 길이 N 인 수열에서 연속된 부분 합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구한다. [2. 풀이 접근] 먼저 부분 합을 구한다. 연속된 부분 합을 찾기 위한 탐색을 해야 하는데, 자연수로 이루어진 수열의 부분 합은 값이 증가할 수 밖에 없으므로, 여기서는 head 와 tail 을 맨 앞에서 부터 움직이도록 한다. 최초 head 를 고정 시킨 상태에서 tail 을 움직이면서 부분 합이 S 이상이 되는지 확인하도록 한다. S 이상이 된 경우 head 를 움직이도록 한다. head 를 움직인 경우 S 미만이 되면, tail 을 움직이도록 한다. 부분 합은 오름차순으로 되어있기 때문이다. === 실수했던 사항 === 불가능 한 경우 ..
투 포인터. [3273] [1. 문제 설명] n 개의 서로 다른 양의정수로 이루어진 수열에서 두 수의 합이 x 가 되는 쌍의 개수를 찾는다. [2. 풀이 접근] 투 포인터 란? 배열 형태에 자료 구조에 순차적으로 접근 해야 할 때, 배열 내 두개의 위치를 기록하면서 하는 방식 병합정렬에서 나눈 두 배열을 다시 병합하는 방식을 생각하면 된다.. ↓ ↓ [head] ........[mid].......[tail] 포인터 혹은 index 를 각각 배열의 시작(head) 과 끝(tail) 에 위치 시키고, head 또는 tail 을 이동시키면서 처리하는 방식 head 와 tail 이 역전되는 순간 탐색을 종료하게 된다. 특별한 경우 간단하게 생각할 수 있는 O(N2) 알고리즘을 O(N) 으로 풀 수 있게 해준다. 가급적 정렬 시킨 배열..
Union-Find. [20040] [1. 문제 설명] Cycle 이 발생한 순서를 출력한다. (없는 경우 0을 출력) [2. 풀이 접근] 그래프에서 Cycle 을 감지하는 여러 방법이 있다. A. dfs, bfs 중 한번 방문한 정점을 재 방문 하는 경우 (from->to->from 으로 가는 것은 제외) B. union-find 를 이용하여 union 하지 않은 경우 union-find 자료구조는 최초 모든 집합은 자기 자신이 root 인 상태이며, 두 집합이 합쳐지면서, (두 정점이 서로 연결되면서) 그래프를 만들어 나가는데, union 이 실패한다는 것은 두 노드가 이미 같은 집합(트리)에 있다는 것을 말하며, 이미 서로 연결되었다는 것을 의미하기도 한다. (=> 직접 연결되었다는 것이 아니라, 다른 정점을 거쳐 연결된다.) [3...
Union-Find. [4195] [1. 문제 설명] 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 친구 관계가 생길 때 마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하도록 한다. [2. 풀이 접근] 문제를 아래와 같이 변형 해볼 수 있다. => 친구 네트워크 == 두 정점이 연결 혹은 두 정점이 같은 집합 => 두 개의 집합이 합쳐질 때마다, => 집합에 속한 원소의 개수를 출력하도록 한다. 즉, 두 노드(집합) 을 합칠 때 마다, 합쳐진 집합에 속한 원소 개수를 출력하면 된다. union find 로 접근한다. 문자열 id 를 정수형 id 로 변환해야 한다. map 을 사용할 경우 O(1) 에 정수형 id 를 얻을 수 있다. union 시, 균형 잡힌 tree 를 만들기 위한 rank 배열 이외 에 집합의 개..
Union-Find. [1976] [1. 문제 설명] N 개의 도시가 있고, 각 도시 사이는 연결될 수도 안될 수도 있다. 여행 일정이 주어졌을 때, (방문할 도시들의 순서) 이 여행 경로가 가능한지 확인한다. 여행 일정을 만족하기 위해, 다른 도시를 경유해서 갈 수도 있다. ex) 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. [2. 풀이 접근] 이 문제에서 bfs 등으로 여행 경로를 확인하기에는 무리가 있다. 왔던 길을 되돌아가도 되기 때문이다. 그래서 일반적인 그래프 순회로 풀이하기에는 까다로울 수 있다. 여기서는 상호 배타적 집합을 통해 풀 수 있다. 여행 계획에 있는 도시들이 모두 같은 집합에 있다면, 여행 계획을 만족하는 경로가 반드시 존재하기 때문이다. (왔던 길..
Union-Find. [1717] [1. 문제 설명] 초기에 0~n 이 각각의 집합을 이루고 있다. 합집한 연산과 두 원소가 같은 집합에 포함되어있는지 확인하는 연산을 수행 같은 집합에 포함되어있는 연산이 있을 때, YES 또는 NO 를 출력 [2. 풀이 접근] union find 이론 설명 링크로 대체 == union 시 주의 할 점 u 가 속한 집합, u 의 root 를 v 의 root 로 재설정해야 한다. (u 가 속한 집합이 v 가 속한 집합의 높이보다 항상 작도록 만드는 경우) 이후, find 시 parents 배열은 알아서 재조정된다. [3. 코드]

티스토리툴바