프로그래민👨‍💻

재귀를 이용하여 분할정복하는 문제이다. func(int i, int j, int size) 함수를 이용하여 size==1이 될때까지 계속 호출하는 형태로 재귀를 반복하게 된다. 기저조건은 size가 1이 될때 cnt++를 해주고 return을 한다. 재귀는 Z모양으로 4번을 호출하게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

재귀를 사용하는 대표적인 문제이다. N개의 원판을 옮기려면 크게 3가지 부분으로 생각하여 접근할 수 있다. 첫번째로 N-1개의 원판을 목적지가 아닌 중간 지점 고리로 옮겨놓고, 두번째로는 가장 밑바닥에 위치한 원판을 목적지로 옮긴다. 마지막으로 중간지점에 위치해있던 N-1개의 원판을 목적지 고리로 옮기는 과정을 반복하다보면 전체 N개의 원판을 목적지로 옮기는 것이 가능하다. 재귀함수의 기저조건으로는 옮길 원판이 없는 경우를 사용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 package chap06; import java.io.BufferedReader; import java.io.Inp..

재귀를 이용하는 기초적인 문제이다. 주어진 숫자의 범위가 2,147,483,647이므로 일반적인 방법으로 접근하면 시간초과가 발생할수밖에 없다. 따라서 재귀를 사용해야하는데 위와 같은 성질을 이용하여 재귀를 사용해준다. 즉, 지수를 계속 제곱해준다는 개념으로 접근하여 B의 값까지 도달하는 것을 구하는 방법으로 해결하면 되는 문제이다. 기저조건으로는 B의 값이 0이 될때를 사용하였다. 또한 보통 분할정복을 사용하는 알고리즘은 3가지의 구성요소를 가지고있다. 1. 문제를 더 작은 문제로 분할하는 과정 (divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case) 1 2 3 4 5 ..