KPU CE

최소 공통조상이란? 두 노드의 조상이 처음으로 같은 경우를 최소 공통 조상이라고 한다. 지금부터 최소 공통 조상을 구하는 알고리즘을 알아보도록 하겠다. 위와 같이 트리가 하나 있다. 여기서 1이 루트라 하고 각 깊이를 구하면 다음과 같다. 여기서 노드 3과 노드 8의 최소 공통 조상은 그림과 같이 노드 2인 것을 알 수 있다. 하나 더 예시를 보자면 노드 8과 노드 10의 최소 공통 조상은 노드 10인 것을 알 수 있다. 바로 본론으로 들어가자면 최소 공통 조상 알고리즘은 1. 두 노드의 깊이를 확인한다. 2. 만약 하나가 다른 노드보다 작다면 깊이-1을 해준다. 3. 만약 깊이가 같다면 두 노드 모드 깊이 -1를 해준다. 4. 깊이-1 해주면서 만약 노드가 같아지는 지점을 찾는다. 5. 같아지는 지점이..

인접 행렬 위와 같이 무방향으로 노드들이 이어져 있다. 이제 이 그래프를 저장하는 2차원배열 ary[6][6]를 만들어준다. 그리고 노드a과 노드b가 이어져있다는 것을 배열로 표현해준다면 ary[a][b] = true, ary[b][a] = true 로 표현해줄 수 있다. 하지만 여기서 단방향 그래프로 만들고 싶으면 예를 들어 a->b인 노드이면 ary[a][b] = true 라고만 해주면 된다. 이렇게 표현하게 된다면 위의 그림은 ary[6][6]의 크기의 배열이 필요하다(ex. ary[5][4] = 1) 이걸 배열로 나타낸다면 아래와 같다. [0] [1] [2] [3] [4] [5] [1] 0 1 0 0 0 [2] 1 0 1 0 0 [3] 0 1 0 0 1 [4] 0 0 0 0 1 [5] 0 0 1 ..

문제 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 1. BFS를 이용해서 탐색을 할 때 방문할 노드가 개방 가능 조건에 있다면 border배열을 true로 해준다 2. true로 되어 있는 노드를 하나 방문 후 연결되어 있는 모든 true노드를 방문한다. 3. 방문할 때마다 cnt++ 을 해줘서 몇 개의 노드를 방문해 줬는지와 sum+=map [y][x]를 해줌으로써 방문한 노드들의 평균값을 구할 수 있다. 4. 방문을 마친 노드..

문제 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제해결 1.벡터에 정점과 가중치를 입력받는다. 2.DFS를 통해서 각 노드들마다 부모와 깊이를 알아낸다. 3.LCA알고리즘을 실행한다 3-1. 만약 두 노드가 같으면 출력한다 3-2. 두 노드가 같지 않고 깊이가 같으면 두 노드 다 깊이-1로 이동한다. 3-3 한 노드가 다른노드보다 깊이가 크면 큰 노드가 깊이-1로 이동한다. 4. 두 노드가 같아 질때까지 반복한다. 코드 ide...

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 이 문제는 최소 스패닝 트리 알고리즘을 사용하면 바로 풀리는 문제이다. 문제해결 1.vector v 를 사용하여 가중치,노드1,노드2 순으로 입력받는다. 2.가중치에 대하여 오름차순으로 정렬한다. 3.parent배열을 모두 parent[i] = i로 초기화 한다 (처음에는 모두 부모가 자기 자신이다 -> 모두 다 끊어진 상태로 시작한다,최소스패닝..

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이 문제는 최소 스패닝 트리 알고리즘을 사용하면 바로 풀리는 문제이다. 문제해결 1.vector v 를 사용하여 가중치,노드1,노드2 순으로 입력받는다. 2.가중치에 대하여 오름차순으로 정렬한다. 3.parent배열을 모두 parent[i] = i로 초기화 한다 (처음에는 모두 부모가 자기 자신이다 -> 모두 다 끊어진 상태로 시작한다,최소스패닝 알고리즘이다) 4.만약 두 노드가 연결되지 않은 노드라면 연결하고 가중치를 result에 더해간다. ->두 노드가 연결된 유무는 find..