Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 하노이의 탑 설명 1, 2, 3번 기둥 이렇게 3개의 기둥과 크기가 모두 다른 n개의 원판이 있을 때, n개의 원판 모두 1번 기둥에 크기가 큰 원판순으로 아래에 위치되어 있다. 이러한 기둥들을 3번 기둥에 모두 옮겨야 하는데, 한 번에 한 원판만 옮길 수 있고 크기가 작은 원판 위에 크기가 큰 원판을 올릴 수 없다. 이러한 원판 이동을 최소한의 횟수로 옮기는 것이 하노이의 탑의 규칙이다. 하노이의 탑 풀이 가장 위에 있는 원반을 1번원반, 그 아래의 원반을 2번 원반, 가장 아래에 있는 원반을 n번 원반이라고 하면 디테일한 과정 말고 큰 과정을 나열하면 3가지로 압축할 수 있다. 1 ~ n-1번 원반을 2번 기둥에 옮..

일반 재귀 간단 요약 재귀 함수는 정지 조건(재귀 앵커)을 충족하기 전 까지 계속 호출하게 된다. 그러면 함수가 한 번씩 호출될 때마다 파라미터, 리턴값, 리턴 후 돌아갈 위치 등이 스택(메모리 저장공간)에 쌓이게 된다. 재귀 함수를 너무 많이 호출하게 되면 스택의 공간이 모두 차버리는 스택 오버플로가 일어날 수 있다. 꼬리 재귀 static int factorial(int n) { if(n > 0) return n * factorial(n-1); //반환(return)부에 연산이 존재 else return 1; //정지 조건 } 위 코드는 일반 재귀를 이용하여 팩토리얼을 구하는 재귀함수이다. 위 코드는 정지 조건을 충족한 재귀 함수가 1을 리턴을 해야 나머지 재귀 함수의 리턴 값이 정해진다. 아래의 첫..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 재귀 알고리즘의 비재귀적 표현 static void recur(int n) { if(n > 0) { recur(n - 1); System.out.println(n); recur(n-2); } } 위 메소드의 꼬리 재귀를 제거하는 방법과 비재귀적 표현으로 나타내는 방법을 정리하려고 한다. 꼬리 재귀의 제거 메소드의 꼬리에서 재귀 호출하는 메소드 recur(n-2)는 파라미터로 n-2를 전달하여 recur 메소드를 호출한다는 뜻이다. 따라서 이 호출은 'n의 값을 n-2로 업데이트하고 메소드의 시작 지점으로 돌아간다'는 뜻이다. 아래는 위 방법을 그대로 구현한 코드이다. n의 값을 -2만큼 감소한 후 메소드의 시작 지점으로..