코딩스타트

재귀를 이용한 하노이탑(백준1914번문제)

재귀를 이용한 하노이탑 문제풀이

여기서 문제는 N값이 20 이하 일때만 원반을 옮기는 과정을 출력하지만 20보다 클 경우에는 원반의 옮긴 수만 출력하면 된다. 여기서 옮긴 횟수를 함수 안에서 재귀호출 할때마다 카운트를 1씩 증가시키는 것으로 코드를 짜게되면 아마 시간 초과가 발생할 것이다.  왜냐면 조건에서의 가장 큰수 100을 입력하면 1267650600228229401496703205375라는 원반을 옮긴 횟수가 나오는데 보통 1억번에 1초정도 걸리는데 이것은 어마어마한 시간이 걸릴 것이므로 횟수는 카운트를 1씩 증가시키는 것이 아니라 점화식을 이용하여 횟수를 구한다.

즉, 원반을 옮기는 횟수는 2^N-1번이다.  N값이 100이라 가정했을 때는, 이 값은 long 데이터 타입도 수용하지 못할 값이므로 자바의 BigInteger 클래스를 이용해 횟수를 저장한다. 내부적으로 String을 가지므로 무한히 큰 값도 수용이 가능하다.

원반을 옮기는 과정의 함수를 설명하자면 예를들어 3개의 원반을 1번탑에서 3번탑으로 옮긴다면 hanoi(3,'1','2','3') 함수를 호출하게 된다. 그러면 함수 내부에서 재귀호출을 통해서 문제를 쪼개는 과정에 들어간다. 3개의 원반을 1번탑에서 3번탑으로 옮기는 것이라면 우선 더 작은 문제로 1번,2번 원반을 2번탑으로 옮긴후에 그다음 3번원반을 3번탑에 옮기고 그리고 1번,2번의 원반을 다시 2번탑에서 3번탑으로 옮기는 것 이렇게 문제를 작은 단위로 쪼개는 것이다. 이것이 총 3번의 과정으로 1번 n-1개의 원반을 보조탑(2번탑으로 옮기는과정)으로 옮기는 과정은 hanoi(2,from,to,aux) 함수에서 해결하고 그다음 3번원반을 1번탑에서 3번탑으로 옮기는 과정은 system.out.println(from+" "+to); 라는 출력문으로 그리고 마지막으로 보조탑에 있던 1번,2번 원반을 3번탑으로 옮기는 과정은 hanoi(2,aux,from,to) 함수에서 해결하게 된다. 그리고 각 함수 내에서 문제를 더 작은 단위로 쪼개고 쪼갠다. 예를 들어 1,2번 원반을 보조탑으로 옮기는 hanoi(2,from,to,aux) 함수에서 다시 문제를 1번원반을 보조탑인 3번탑으로 옮기는 과정(hanoi(1,1,2,3)과 2번원반을 2번탑으로 옮기는 과정(system.out.println(from+" "+to) 그리고 마지막으로 보조탑에 있던 1번원반을 목적탑인 2번탑으로 옮기는과정(hanoi(1,3,1,2))으로 마무리 되는 것이다. 

즉,

 hanoi(N-1,from,to,aux);

System.out.println(from+" "+to);

hanoi(N-1,aux,from,to);

이 과정이 n의 수가 1이 될때까지 계속 각 n값에 대하여 반복하게 되는 것이다.

재귀함수-백준1074번 Z문제

풀이-재귀호출을 이용한 알고리즘풀이

이 문제를 보면 딱 떠오르는 것이있다. Z방향으로 배열을 순회하는 것이다. 그 말은 즉슨 배열을 1사분면->2사분면->3사분면->4사분면 순서로 방문을 하는 것이다. 여기서 이용되는 재귀호출의 기능은 예를들어 8x8의 배열이라면 재귀호출을 통해 4x4배열로 줄여주는 역할을 한다.(이말을 재귀호출을 통해서 큰 문제를 작은 문제로 쪼개나가는 과정이라고 생각하면 된다.) 1/4씩 배열의 크기를 줄여가며 방문한 횟수를 카운트해주는 것이다. 예를 들어 8x8의 배열의 2사분면이라면? 8x8배열에서 이미 1사분면을 지나왔으므로 (64/4)*(해당분면-1=1)의 배열만큼 방문해서 2사분면을 온것이므로 방문횟수에 (64/4)*1만큼의 수를 증가시켜주고 8x8의 2사분면인 4x4배열로 재귀를 통해 문제의 크기를 줄여준다. 그 다음의 위치가 4x4의 배열에서 몇 사분면이냐라는 것을 다시 따져서 위처럼 횟수를 증가시켜준다. 그리고 배열을 줄여가다 마지막으로 2x2의 배열이 되었을때 1사분면일때는 횟수를 0, 2사분면은 횟수를 1, .....4사분면은 횟수를 3을 증가시켜주면된다.