NEMOSTAR5

Union-find는 대표적인 그래프 알고리즘이다. 바로 '합집합 찾기'라는 의미를 가진 알고리즘. 서로소 집합(Disjoint-set) 알고리즘 이라고도 불린다. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 처음에는 자기 자신이 부모 노드로 되어있는 상태이다. 만일 1과 2과 연결되었다고 생각해보자. 그렇게 되면 2의 부모 인덱스에는 1이 들어간다. 부모를 합칠 때에는 일반적으로 더 작은 값 쪽으로 합친다. 1 2 3 4 5 6 7 1 1 3 4 5 6 7 이번에는 2와 3이 연결되었다고 가정해보자. 1 2 3 4 5 6 7 1 1 2 4 5 6 7 그렇다면 1과 3이 연결되었는지를 어떻게 파악하냐가 문제이다. 1과 3은 부모가 각각 1과 2로 다르기 때문에 '부모 노드'만 보고는 한번에 파악 할..

힙 정렬의 시간 복잡도는 nlog n이다. 힙을 생성하는 알고리즘의 시간 복잡도는 log n이다. 그 이유는 완전 이진트리 구조를 사용하기 때문이다. 상향식 구현방법 #include using namespace std; int number = 9; int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6}; int main() { // 힙을 구성 for(int i = 1; i < number; i++) { int c = i; do { int root = (c - 1) / 2; if(heap[root] < heap[c]) { int temp = heap[root]; heap[root] = heap[c]; heap[c] = temp; } c = root; }while (c != 0); } /..

이 문제에는 빙산이 존재한다. 빙산은 일년마다 지구온난화로 인해 녹는다. 얼마나 녹느냐의 기준은 바닷물로부터 얼마나 둘러싸여있느냐에 따라 다르다. 그림 2는 그림 1의 일년뒤이다. 동, 서, 남, 북으로 바닷물의 닿아있는 정도에 따라 1년에 녹는 정도가 다르다. 출력은 빙산이 그림 3처럼 두조각으로 분리되는 최조의 시간(년)을 출력하는것이다. 문제풀이 방법 count를 이용해 bfs, dfs를 이용해 count >= 2이상 될시 두조각으로 분리된것으로 판단해 그 시간을 출력. #include #include using namespace std; #define MAX 301 int n, m; //y, x int map[MAX][MAX]; int visit[MAX][MAX] = {0, }; int cnt =..

https://www.acmicpc.net/problem/1182 #include #include using namespace std; int out[13]; int n = -1; int arr[13]; void lotto(int depth, int count) { if(depth == 6) { for(int i = 0; i arr[i]; lotto(0, 0); cout