코린이 탈출기

Algorithm 유향 그래프의 정점을 정렬 정점을 오른쪽 방향으로 쭉 나열했을 때, 오른쪽에 있는 정점에서 왼쪽의 정점으로 이동하는 간선은 하나도 없도록 만듦 위상정렬 조건: 그래프가 DAG(Directed Acyclic Graph)의 형태를 띄어야함. -> 방향이 있고 싸이클이 없는 그래프 적용 그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는 조건이 주어지는 경우 Ex) 줄 세우기를 하는데, 키가 작은 사람은 키가 큰 사람보다 무조건 앞에 서야함 Queue로 구현하기 들어오는 간선이 없는 (indegree가 0인) 정점을 모두 큐에 넣는다. 정점의 개수만큼 이를 반복한다. 2-1. 큐의 front를 pop해서 그 정점에서 나가는 간선을 모두 삭제한다. 2-2. 삭제하..

Logic low, high를 정한다. low가 high보다 작거나 같을 때까지 while문을 반복한다. while문 내에서 mid를 정한다. 탐색할 값이 mid보다 작다면 반틈으로 나눈 것 중에서 앞부분에 있다는 뜻이므로 high = mid - 1로 바꾼다. 탐색할 값이 mid보다 크다면 반틈으로 나눈 것 중에서 뒷부분에 있다는 뜻이므로 low = mid + 1로 바꾼다. 관련 문제 www.acmicpc.net/problem/2805 더보기 풀이보기 나무의 길이 최댓값이 매우 크기 때문에 그냥 구현하면 시간 초과가 발생한다. 이분탐색을 이용해서 절단기 높이 최댓값을 효율적으로 찾을 수 있다. low = 0, high = 1000000000(최대)로 정해두고, 이분탐색을 통해서 각 경우의 절단된 나무길이..

- 순열 void Permutation(int now_c, int goal_c, vector arr) { if (now_c == goal_c) { //순열 생성 완료 cout