유자의 코딩모험

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 N의 M 거듭제곱 값을 구하는 프로그램을 재귀호출을 이용하여 구현하는 문제다. M이 0일 때는 1, 그 이외의 경우에는 n * power(n, m - 1)을 리턴해주면 거듭제곱을 쉽게 구할 수 있다. 하지만 이 방법은 시간 복잡도가 O(N)이라서 지수가 커지면 문제가 발생할 수 있다. 이때 분할정복을 이용하면 O(logN)의 시간 복잡도로 거듭 제곱을 구할 수 있다. 2의 8제곱을 예로 들어보자. 2의 8제곱은 2를 8번 곱하여 구할 수도 있지만 거듭 제곱을 3번만 해서 해결할 수도 있다. 홀수번 거듭 제곱을 하는 경우에는 N을 한 번 곱하고 N의 (M-..

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 문제풀이 처음에 문제를 읽고 어떻게 해야될지 한참 생각해도 잘 모르겠어서 다른 블로그 글을 참고했다. [백준 4256] 트리 예제로 트리 구조를 유추해보자. 전위 순회 : 3 6 5 4 8 7 1 2 중위 순회 : 5 6 8 4 3 1 2 7 전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다. 전위 baelanche.tistory.com 위 트리를 살펴보자. 전위 순회 : 3 6 5 4 8 7 1 2..