BOJ75 [BOJ]10655번: 마라톤 1 www.acmicpc.net/problem/10655 수학 문제입니다. 1번부터 N번 체크포인트까지 순서대로 이동한다는 제약이 있습니다. 그러므로 정답 후보들끼리도 하나의 체크포인트를 제외하여도 나머지 경로는 동일합니다. 예시) 1-2-3-4-5 경로가 있다고 가정 1. 2번 체크포인트 제외하는 경우 1-3-4-5 2. 3번 체크포인트 제외하는 경우 1-2-4-5 3. 4번 체크포인트 제외하는 경우 1-2-3-5 즉, x번 체크포인트를 제외한다고 가정하면 x-1번 체크포인트 -> x번 체크포인트 x번 체크포인트 -> x+1번 체크포인트 위 두 경로만 빼면 나머지 경로는 다른 정답후보들과 동일하다는 뜻입니다. 풀이) 1. 1번부터 N번 체크포인트까지의 경로를 전부 구합니다. 2. 2번~N-1번 체크포인트에.. 2021. 3. 30. [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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 19 다음
