1. 문제 이 문제는 이미 연결된 집합을 한 정점으로 표현하여 최소 스패닝 트리를 구하는 문제이다. 이 문제의 핵심은 연결된 집합을 한 정점으로 어떻게 표현할 것인가에 있다. 2. 유니온 파인드 : 크루스칼 알고리즘 이미 연결된 집합을 유니온-파인드 자료구조로 표현하여 각 집합사이의 최소 거리를 구하려면 많이 복잡하다. 이를 간결하게 구현하려면 소방차 문제에서 그랬듯이 임의적인 방법이 필요하다. 그러므로 책에서는 연결된 정점끼리 이어지는 간선의 가중치를 0으로 설정해서 항상 이 간선을 선택하게끔 하였고 가중치가 0이므로 추가되는 가중치의 합을 구할 수 있게 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

1. 문제 이 문제는 경유점이 중요하다. 한 정점마다 경유하는지를 조사하고 그 경유점으로 인해 최소거리가 되는지 조사하는 플로이드 알고리즘을 이용하여 이 문제를 해결할 수 있다. 2. 경유점 정렬 플로이드 알고리즘에서 정점들의 추가 순서는 알고리즘의 정당성에는 영향을 미치지 않는다. 따라서 delay에 대해 정렬하고, delay가 작은것 부터 조사하게 되면 경로에서 어떤점이 최대의 delay를 가지는지 별도의 연산이 필요없게된다. (항상 추가하는 정점이 현재 최대 delay이므로) 3. 플로이드 알고리즘: 잘못된 풀이 플로이드 알고리즘을 적용시킨 처음 풀이는 다음과 같았다. 정점 w를 추가 하였을 때 adj[i][w] + adj[w][j] + delay[w] 에서 i->w 에서 생기는 딜레이와 w->j ..

1. 문제 기둥이 4개가 있다. 네 개의 기둥에 원반들이 자유롭게 배치되어있을 때 (작은것이 위로 와야함) 모든 원반을 맨 오른쪽 기둥으로 옮겨 놓기 위해 필요한 최소한의 움직임 수를 계산하는 프로그램을 작성하여라 2. 최소거리 탐색 기둥이 4개, 원반이 최대 12개 이므로 기둥은 2비트로 표현가능하므로 각 원반마다 해당하는 기둥을 나타내는 상태공간은 최대 24비트만 있으면 표현가능하다. 상태공간에서 최단거리를 구하기위해 너비우선 탐색을 사용하면 시간이 초과 될 수 있다. 분기점은 최대 6개에 최소 3개이니 대략 5라고하자 그러면 최단거리가 d일때 O(5^d) 의 시간이 걸린다. 하지만 목표상태에서 역방향으로 움직이기 쉬우므로 양방향 탐색을 통해 시간을 줄일 수 있다. 그러면 O(5^(d/2))로 어느정..

1. 문제 중복이 없는 정수 수열에서 이 수열의 임의의 구간을 선택 해당 구간을 뒤집을 수 있다. => 뒤집기 연산으로 전체 수열을 정렬하고 싶다. 정렬을 위해 뒤집기 연산을 최소 몇번해야 하는지를 계산하여라 2. 그래프 수열의 길이는 1~8 이다. 따라서 이는 최대 8!의 상태가 있는것이다. 각각의 상태를 그래프로 표현하고, 각각 뒤집기 한번한 연산 결과와 이어주는 간선으로 표현하면 그래프가 만들어질 것이다 이 그래프를 bfs로 정렬된 상태까지의 거리를 구하면 답이 될것이다 하지만 내가 생각한 그래프를 만드는 방법은 수열하나에 번호 하나를 매기고 하나하나 뒤집으며 간선을 이어주는 것 이었다. 전체 수열 40320 개 중 하나를 뒤집으면 28개의 뒤집어진 수열이 생기고 28개를 뒤집는데 2중 반복문에 거..

1. 문제 모든 방을 감시할 수 있게 감시 카메라를 최소한으로 설치해야한다. 이때 방은 모두 트리 간선을 이루고 있다고 한다. (연결되지 않은 방 또한 있다.) 어떤 방에 카메라를 설치했다고 하자. 그러면 그 방 주위의 방들을 감시할 수 있다. 1칸밖에 감시를 못하므로 이것은 '리프' 에서부터 차근 차근 카메라를 설치해야한다. '리프' 에서부터 탐색하는하는 것은 dfs를 이용하면 쉽게 구현할 수 있다. 2. dfs 일단 루트에서부터 dfs를 실행하게 되면 제일먼저 종료되는 dfs는 '리프'이다. '리프' 이전의 방에서는 무조건 카메라가 설치되어야 '리프'를 감시 할 수 있다. 그러므로 '리프' 이전의 방에 카메라를 설치한다. 이 문제에서 '리프'는 연결점이 타고내려온 것을 제외하고는 아무것도 없는 정점을..

1. 문제 이 문제는 여러 집합들을 세 집합으로 나누는 문제이다 - 아무것도 속해있지 않은 집합 - b집합과 대치되는 a집합 - a집합과 대치되는 b집합 m개의 댓글에서 두명의 정보가 주어진다. 두명의 정보는 ack -> 같은 편, dis -> 다른편 으로 주어지고 이를 통해 a와 b 집합으로 나누는 것이다. 그 후 a와 b의 모순이 생기면 모순이 생기는 댓글의 인덱스를 모순이 생기지 않으면 아무것도 속해있지 않은 집합의 크기와 a,b중 더 큰 집합의 크기를 더한 값을 반환하면 문제를 해결할 수 있다. 2. 상호 배타적 집합: 유니온-파인드 자료구조 ack a b 가 주어지면 a 와 b를 합친다. 이때 a와 b가 대치되는 사람 r[a] r[b] 가 있다고 하자 그러면 ack r[a] r[b] 또한 참이 ..