![]()
문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 이진 트리는 루트, 왼쪽 서브트리, 오른쪽 서브트리로 나눌 수 있습니다. 인오더와 포스트오더에서도 똑같이 3 부분으로 나눌 수 있습니다. 서브트리는 또다시 루트와 2개의 서브트리로 나눌 수 있습니다. 하나의 트리를 루트와 두 서브트리, 두 서브트리는 다시 루트와 서브트리로 나눌 수 있으며 이렇게 분할정복을 통해 문제를 해결할 수 있습니다. 예시를 들어서 구체적으로 설명해보겠습니다. 위와같은 트리가 주어졌을 때 인..
문제 2749번: 피보나치 수 3 (acmicpc.net) 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 피보나치를 풀기 위해 대표적으로 다이나믹 프로그래밍을 활용할 수 있습니다. 메모이제이션을 활용한 재귀호출로 원하는 수 까지 $O(n)$의 속도로 빠르게 구할 수 있지만 이번 문제는 n 은 최대 1,000,000,000,000,000,000로 굉장히 크기 때문에 $O(n)$ 으로는 시간초과가 발생합니다. 더 빠른 속도로 문제를 해결하기 위해 점화식을 수정해 봅시다. 우선 기본적인 피보나치 수열의 점화식을 살펴봅시다. $$ F_{n+1} = F_{n} + F_{n-1} $$ 여기서 ..
