Basic/자료구조,알고리즘 썸네일형 리스트형 하노이타워(재귀) 1. 하노이 타워 문제 하노이 타워 문제는 재귀함수의 대표적인 예로 꼽힌다. 하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법에 관한 것이다. 막대가 3개인 이유는 제약조건이 있기 때문이다. 2. 제약조건 원반은 한 번에 하나씩만 옮길수 있다. 그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다 따라서 막대 B의 도움이 필요하다. 3. 문제 해결 원반의 수가 늘어나도 위 해결 과정처럼 해결방법은 똑같다. 일련의 과정을 더 많이 반복할 뿐 이다. 그래서 위 해결과정에서 반복의 패턴을 찾아야 한다. 먼저 처음 3번 원반을 C로 옮기려면1번과2번 막대를 B에다 옮기는 방법에 대해 고민해야한다. 이것이 하노이타워 문제해결의 핵심이다. 1번과 2번만 B로 옮기면 3번 원반을.. 이진 탐색 알고리즘의 재귀적 구현 이진 탐색 알고리즘의 재귀적 구현 이진 탐색 알고리즘의 재귀적 구현 이진 탐색의 알고리즘을 재귀적으로 구현해 보았다. 재귀적으로 구현해 성능은 좋지 않다. 이 알고리즘에서는 재귀적 성격을 다음의 반복적인 패턴에서 찾을수 있다. 1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인. 2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 재탐색. 그리고 탐색 대상을 찾을때 까지 위 2가지 패턴을 반복한다. 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 public class b_04_RecursiveBinarySearch { static int BSearchRecur(int ar[], int first, int last, int target) { if(first > last)//재.. 이진 탐색 알고리즘의 재귀적 구현 이진 탐색 알고리즘의 재귀적 구현 재귀의 활용(피보나치 수열) 피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열로서 다음과 같이 전개가 된다 앞의 수 두개를 더해서 현재의 수를 만들어가는 수열이다. 그래서 처음 0과 1이 주어진 상태에서 다음의수 1을 만들어 가게 된다. 수열의 1번째 위치의 값은 0을 반환 수열의 2번째 위치의 값은 1을 반환 3번째 이상 n번째 부터는 n-1번째+n-2번째의 값의 합을 반환 한다. 이를 코드로 구현해보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class b_03_FibonacciFunc { static int Fibo(int n) { if(n==1)//수열의 1번째 위치의 값은 0을 반환 return 0; else if(n==2)//수열의 2번째 위치의 값은 1을 반환 ret.. 재귀의 활용(피보나치 수열) 1. 재귀의 활용(피보나치 수열) 재귀(Recursive) 1. 재귀(Recursive): - 함수(메소드) 내에서 자기자신을 다시 호출하는것을 의미한다. - 완료되지 않은 함수를 다시 호출하는것 - 제일 첫번째로 호출된 함수가 가장 마지막에 종료가 되는 특성 - 탈출 조건이 있어야한다. 없으면 무한 반복 한다. 1) 예시1 - 간단한 출력 12345678910111213141516public class b_01_Recursive { static void Recursive(int num) { if(num 재귀(Recursion) 재귀(Recursion) 이전 1 2 3 4 5 다음
