Problem Solving

https://www.acmicpc.net/problem/1167 서로 다른 두 노드를 잇는 최단 경로는 두 노드의 최소 공통 조상을 거친다는 것을 먼저 관찰해야 한다. (물론 최소 공통 조상이라는 용어를 꼭 알아야 이런 생각을 하는 건 아니다. LCA 알고리즘은 이 문제에서 전혀 쓰이지 않는다) 이걸 관찰하는 데에 성공했으면 최소 공통 조상의 관점으로 이 문제를 풀어볼 생각을 할 수 있다. 즉 각각의 노드에 대해 그 노드를 최소 공통 조상으로 갖는 두 노드 쌍 중에서 거리가 최대인 것을 찾으면 된다. 그러려면 각각의 노드 v에 대해 v를 루트로 갖는 서브트리의 노드 중에서 v와의 거리가 최대인 것과 2번째로 큰 것을 찾아야 한다. (물론 가중치가 양수이므로 이 두 노드들은 전부 리프 노드들일 것이다) ..

https://www.acmicpc.net/problem/1517 이 문제는 N이 크므로 당연히 버블 소트를 직접 해서 푸는건 아니다. swap의 최대 횟수 역시 O(n^2)이므로 swap을 '하나씩' 세어서는 시간 안에 답을 낼 수 없다. 여러개의 swap을 한번에 카운팅하는 알고리즘이 필요하다. 즉 swap을 다른 방식으로 세어야 하므로 세는 관점을 한번 바꿔보자. 각각의 A[i]에 대해 A[i]가 다른 항과 몇번 swap되는지를 세는 것이다. 작은 N에 대해 예를 들어보면서 직접 이걸 세어보면, A[i]가 겪는 swap이 2종류가 있다는 것을 발견할 수 있다. A[i]가 왼쪽에서 오른쪽으로 가는 swap과 오른쪽에서 왼쪽으로 가는 swap 이렇게 2종류가 있다. 그래서 한번 경우를 나눠서 세어보려고..

https://www.acmicpc.net/problem/17298 아주 유명하고 기초적인 유형의 문제이지만, 그냥 풀이를 외우기만 하지 말고 사고과정을 이해해보자. 일단 우리는 특정한 하나의 i값에 대해 NGE(i)를 구해야 하는게 아니고, 모든 i값에 대해 NGE값을 전부 구해야 하므로, NGE(i)를 구하는 것을 n번 반복하는 '무식한' 코드를 짜서는 안된다는걸 알 수 있다. 하나의 NGE값을 O(n)보다 빠르게 구할 수는 없을 것이기 때문이다. (NGE(i)를 구하려면 A_i보다 오른쪽에 있는 수들을 하나씩 보기는 해야 하므로...)  따라서 우리는 여러 NGE값들을 '한꺼번에' 구해야 한다. 먼저 수들을 왼쪽에서부터 차례대로 한번 봐보자. 물론 이것도 당연히 그래야 하는건 아니다. 오른쪽부터 봐..