LCA 2 썸네일형 리스트형 백준 11438 LCA 2 트리를 입력받은 뒤, 공통 조상 중 가장 가까운(높이가 낮은) 노드를 찾는 문제이다. LCA 1이 있고 LCA 2가 있는데, LCA 1은 나이브하게 공통 조상을 밑에서부터 같이 찾아 올라가도 정답 처리가 되지 않을까 싶다. 그 문제는 골드3이고 이 문제는 플레 5이므로 난이도 차이가 꽤 난다. 문제의 접근은 DP-Like 하다. DP도 제대로 본건 아니지만, 연산 과정을 배열에 저장한다는 관점에선 비슷하다고 볼 수 있지 않을까? DP를 좀 더 많이 해보고 차이점을 더 잘 알게 된다면 이 글을 수정해야겠다. 그럼 여기서 DP-Like 하게 연산과정을 저장한다고 했는데, 무엇을 저장하는가? 바로 어떤 노드의 2^K번째 조상을 저장한다. 100000개의 노드가 있을 때, Worst Case일 경우 높이는 10.. 더보기 이전 1 다음