전체 글361 [BOJ]1167번: 트리의 지름 www.acmicpc.net/problem/1167 stonejjun님의 풀이(stonejjun.tistory.com/149)를 참고하여 해결하였습니다. 자세한 사항은 위 링크를 참고하시면 됩니다. 풀이를 요약하자면 1. 그래프(트리)를 만들면서 임의의 리프 노드 'A'를 하나 구합니다. 2. 'A'에서 DFS를 돌려서 'A'랑 가장 먼 거리의 노드인 'B'를 구합니다. - 노드 'B'는 무조건 트리 지름의 한 점입니다. 3. 'B'에서 다시 DFS를 돌려서 'B'와 가장 먼 거리의 노드인 C'를 구합니다. 4. 'B'와 'C'의 거리가 트리의 지름이 됩니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ1167.cc 2021. 3. 10. [BOJ]3197번: 백조의 호수 www.acmicpc.net/problem/3197 R, C 값이 크기 때문에 직접 하루하루씩 날짜를 올리면서 BFS를 돌리면 O(N^3)으로 시간초과가 납니다. (R,C를 N으로 퉁치겠습니다.) 1. 맨 처음에 BFS 탐색을 통해 가장 마지막에 녹는 빙판의 날짜 MAXV 를 구합니다. 2. 1번 값에 의해서 백조가 만나게 되는 날의 후보는 0~MAXV 사이에 존재합니다. 3. 0~MAXV 날짜 사이의 후보값을 이분탐색으로 BFS를 돕니다. 4. 그러면 시간복잡도는 O(N^2LogN)이 되서 제한시간 내에 통과할 수 있습니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ3197.cc 2021. 3. 8. [BOJ]3584번: 가장 가까운 공통 조상 www.acmicpc.net/problem/3584 트리에서 두 노드의 가장 깊이가 깊은 공통 조상을 찾는 문제입니다. 1. 각 각의 두 노드에 대해 root 부터 자신의 부모까지를 stack으로 저장합니다. (계산의 편의를 위해 stack으로 집어넣어 root가 가장 맨 위에 들어가게 했습니다.) 2. 두 노드의 부모 stack을 앞에서부터 하나씩 빼면서 서로 부모가 달라질 때 까지 값을 뽑습니다. (당연히 맨 처음에 뽑히는 건 root입니다.) 3. 스택에서 서로 부모가 달리지기 직전에 뽑힌 동일한 부모가 가장 가까운 공통 조상입니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ3584.cc 2021. 3. 8. [BOJ]1516번: 게임 개발 www.acmicpc.net/problem/1516 건물 짓는 선후 관계가 있기 때문에 위상정렬로 해결할 수 있습니다. 1. 선후 관계를 만족하는 임의의 위상 정렬 순서 구하기 2. 1번에서 구한 순서를 바탕으로 실제 BuildTime 구하기 아래와 같은 관계가 성립합니다. 현재 빌딩을 짓는데 실제 걸리는 시간 = 현재 빌딩을 짓는데 원래 걸리는 시간 + 먼저 지어야 하는 건물을 짓는데 실제 걸리는 시간 중 최댓값 realBuildTime[now] = max(realBuildTime[preBuilding]) + buildTime[now] 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ1516.cc 2021. 3. 5. 이전 1 ··· 37 38 39 40 41 42 43 ··· 91 다음
