https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 동생이 이동하는 것을 확인하면서 동생이 어떤 시간에 어디에 위치하는지 "discovered1[위치] = 도착 시간"에 표시하고, 수빈이 이동하는 것을 확인하면서 수빈이 어떠한 위치에 짝수(홀수) 시간에 도착하면, 해당 도착시간 이상의 짝수(홀수) 시간에 모두 도달할 수 있음을 이용해서 "discovered2[위치][짝수:0, 홀수:1] = 도착시간"을 표시하고..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 현재 장대에 위치한 n개를 목표하는 장대에 옮려면, 우선 현재 장대의 위의 n-1개를 임시로 사용할 장대에 옮겨 놓고, 현재 장대의 가장 밑에 있는 원판을 목표하는 장대로 옮기고, 임시로 놓아둔 장대의 n-1개를 다시 목표하는 장대로 옮겨 놓는 과정으로 문제를 해결했다. 코드 #include #include #include using namespace std; int n; vector..

https://www.acmicpc.net/problem/23059 23059번: 리그 오브 레게노 첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구 www.acmicpc.net 아이템의 관계를 그래프로 표현하여, 위상 정렬과 같은 방법을 통해 문제를 해결했다. 이때 현재 구매할 수 있는 "아이템 중 아직 구매하지 않은 아이템을 모두 찾고, 찾은 아이템을 사전순으로 구매하는 과정"을 거치므로, indegree가 0 인 아이템을 모두 그래프에서 깊이를 0으로 표시하여 그래프의 탐색을 이어나갈수록 깊이가 깊어지는 것으로 표시하였으며, 아이템..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 입력받은 중위 순회(인오더)와 후위 순회(포스트오더)에서 같은 부분을 나타내는 인덱스의 범위를 표현하여, 같은 부분의 후위 순회의 범위는 range_post_left ~ range_post_right, 중위 순회의 범위는 range_in_left ~ range_in_right로 확인하며, 후위 순회의 마지막은 루트 노드라는 점을 이용하여, 전위 순회(프리오더)의 값을 채우고 해당 노드 왼쪽을 확인하고 다음으로 해당 노드 오..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net a가 b보다 무거울 때 b에서 a로 가는 그래프로 생각하고 'info[b][a] = a가 b보다 무겁다는 정보가 있을 때 1'에 정보를 표시했다. 그리고 info를 플로이드 와샬을 이용해 특정 위치에서 도달할 수 있는 위치를 판단하여 비교가 가능한지 확인하는 방법으로 문제를 해결했다. 코드 #include #include #include using namespace std..

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 회의실 배정 문제와 유사하게, 필요한 책의 범위 들을 범위가 끝나는 게 짧은 것 순으로 정렬하고, 정렬된 순서로 그리디 하게 책을 배정하여 문제를 해결했다. 코드 #include #include #include using namespace std; int tc; int n, m; int book_check[1005]; vector range; //학생이 원하는 책 번호 (a~b)를 (b,a) 순으로 ..