BOJ 12849 - 본대 산책 문제 링크(Link)https://www.acmicpc.net/problem/12849 문제 해결 (Solution) 1. dp[i][j] = i 건물에서 j분 일 때의 경우의 수. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 출발 지점과 도착 지점 모두 "정보과학관"이다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 6549 - 히스토그램에서 가장 큰 직사각형 문제 링크(Link)https://www.acmicpc.net/problem/6549 문제 해결 (Solution) 1. 여러가지 풀이 방법이 있지만, 분할 정복(divide & conquer)과 구간 트리(segment tree)를 이용해서 문제를 해결. 2. 가장 큰 직사각형은 일정한 구간 내에서 가장 낮은 높이에 의해 결정된다. 3. tree[node] = 일정한 구간 (i, j)에서의 가장 낮은 높이의 인덱스. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 2로 나누고 곱하는 과정을 쉬프트 연산을 이용하면 조금 더 빠르게 해결할 수 있다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1761 - 정점들의 거리 문제 링크(Link)https://www.acmicpc.net/problem/1761 문제 해결 (Solution) 1. 문제에서 주어지는 그래프가 트리(Tree)임을 알고있다. 2. 트리에서 두 정점의 거리를 일반적인 방법으로 구하기 위해선 시간복잡도 O(N)이 소요된다. 쿼리의 개수를 고려하면 전체 시간복잡도는 O(NM)이 소요된다. 즉, 400,000,000(4억) 이므로 시간 초과에서 자유로울 수 없다. 3. dp를 이용한 LCA(최소 공통 조상) 알고리즘을 이용하면 O(logN)만에 두 정점의 거리를 구할 수 있다.(트리에서만...) 4. dp[i][j] = 정점 i에서의 2^j 번째 조상. 5. dist (dist[i] = 루트에서 부터 정점 i 까지의 거리) 라는 배열을 활용해서 두 정점사이.. 더보기 이전 1 ··· 5 6 7 8 9 10 11 ··· 32 다음