백준34 [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]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 2 3 4 5 ··· 9 다음
