본문 바로가기

알고리즘

 (403)
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. 코드]
트리. [4803] [1. 문제 설명] 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리는 정점이 n개, 간선이 n-1개 있다. => 정점이 n 개 간선이 n-1 개 인 그래프는 트리이다? => FALSE 트리에서 임의의 두 정점에 대해서 경로는 유일하다. 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오. [2. 풀이 접근] A. DFS 무방향 연결 그래프에서 임의의 트리를 하나 만들 수 있다. 어떤 정점에서 DFS 로 그래프를 한번 순회하면 된다. (혹은 BFS) 트리에서 임의의 두 ..
04. 탐욕법 - 예제3 [1. 문제 설명] [2. 풀이 접근] 적당한 사람을 배정 해야 할 때 vector 를 정렬해서 사용했을 시 문제점 탐색은 O(logn) 이 가능하나, 배정했으므로 vector 에서 제거해야 한다. 이 때, vector 특성 상 제거하는데, O(n) 시간이 소요된다. 이진검색트리인 set 혹은 multiset 을 사용한 경우 탐색과 제거 모두 O(logn) 에 할 수 있다. 그런데 set 은 중복 값을 저장 할 수 없으나 multiset 은 중복 값을 저장 할 수 있다. [3. 코드]
04. 탐욕법 - 예제2 [1. 문제 설명] n 개의 문자열들의 길이가 주어질 때, n 개의 문자열들을 순서와 상관없이 합쳐서 한개의 문자열로 만들 때 필요한 비용의 최소 값 ex) {al, go, spot} 을 합칠 때 {al+go}+spot => al+go 비용: 4, algo+spot 비용 8 => 총 비용 12 [2. 풀이 접근] 한 문자열이 전체 비용에 미치는 영향에 대해서 생각해보면 병합되는 문자열들의 총 길이가 전체 비용에 더해진다. 병합의 대상이 되는 문자열의 길이가 매번 전체 비용에 누적된다고 볼 수 있다. 위 예제에서 "al" 은 "al" + "go" 에서 전체 비용에 더해지고 "algo" + "spot" 에서 전체 비용에 더해진다 볼 수 있다. 그래서, 항상 길이가 짧은 두 문자열이 병합의 대상이 되게 하는 ..
04. 탐욕법 - 예제1 [1. 문제 설명] n 개의 도시락이 있고, i번째 도시락을 데우는데 m[i] 초, 먹는데는 e[i] 초가 걸린다. 도시락을 먹기 위해서는 도시락을 먼저 데워야 한다. 도시락을 여러번에 나누어 데울수는 없다. 모든 사람이 도시락을 다 먹을 때 까지 걸리는 최소 시간 [2. 풀이 접근] 스케줄링 문제는 보통 탐욕법으로 풀 수 있다. (모든 경우는 아님) 전체 시간 = n-1 개의 도시락을 데우는 시간 + 마지막 도시락을 먹는데 걸리는 시간 먹는데 오래 걸리는 도시락부터 데우면 된다. 먹는데 오래 걸리는 도시락을 먼저 데우면, 다른 도시락을 데우는 시간 동안 이 도시락을 먹을 수 있기 때문이다. === 탐욕적 선택 속성 증명 먹는데 가장 오래 걸리는 샤브샤브 도시락을 먼저 데우는 최적해가 반드시 하나 있음을..
04. 탐욕법 [1. 개요] 탐욕법은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다. 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없으나, 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다는 것이 다르다. 그래서, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다. 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있다. => 모든 단계를 고려하는 동적 계획법이 틀릴 이유가 없기 때문 그럼에도, 탐욕법을 사용하는 이유는 동적 계획법에 필요한 메모리나 시간이 너무 크기 때문이다. 탐욕적 알고리즘을 설계하는 좋은 방법은 간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것 [2. 사용되는 경우] A. 탐욕법을 사용..
03. 동적계획법 - 예제4 [1. 문제 설명] 2xN 크기의 직사각형을 2x1 크기의 타일로 채울 때 좌우 대칭으로 채우지 않는 경우의 수를 구한다. 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지 (1e9 + 7) [2. 풀이 접근] A. 여사건 방식 전체 타일링 방법에서 대칭 타일링 방법의 수를 빼서 구한다. 대칭 타일링 수는 n 이 짝수인 경우와 홀수인 경우를 나누어서 생각한다. n 이 짝수인 경우 => 가운데를 가로 타일링으로 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식 => 절반 한쪽을 채우고, 나머지 한쪽을 마찬가지로 동일하게 채우는 방식 n 이 홀수인 경우 => 가운데러르 세로 타일링을 채우고, 한쪽을 채운 뒤, 나머지 한쪽을 동일하게 채우는 방식 == 전체 계산 후 주의할 점 =..

티스토리툴바