C 자료구조
-
5. The Tower Of Hanoi ( 하노이 타워 )C 자료구조/1. 재귀함수 2020. 6. 10. 10:26
원반이 3개인 경우의 그림부터 보자. 가장 작은 원반을 1번, 가장 큰 원반을 3번이라고 하자. [그림 1 : 3개의 원반을 가지는 하노이의 탑 문제 ] 위의 그림에서 원반의 이동의 순서를 알아보도록 하자. 각 이동단계는 아래의 그림들과 같다. [ 그림 Step 1 ] [ 그림 Step 2 ] [ 그림 Step 4 ] [ 그림 Step 5 ] [ 그림 Step 6 ] [ 그림 Step 7 ] 위 그림을 통해 알 수 있는 규칙은 아래와 같다. 이 규칙은 원반이 4개인 경우에 대해서도 성립한다. 1. A막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 B로 이동시킨다. 2. 그리고 나서 가장 큰 원반인 3번 원반을 막대기 C로 이동시킨다. 3. B 막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 C로 이동..
-
4. BinarySearch( 이진 탐색 )C 자료구조/1. 재귀함수 2020. 6. 8. 19:15
이진 탐색에서 반드시 배열은 정렬되어 있어야 한다. 아래는 이진탐색의 수도 코드이다. 위의 의사코드를 보면 list는 탐색할 배열, low는 탐색 시작 인덱스, high는 탐색 마지막 인덱스이다. list[low]에서 list [high]에서의 탐색은 list[low]에서 list[middle-1]의 탐색이 되거나 list[middle+1]에서 list[high]에서의 탐색이 된다. 이들 2가지의 탐색은 원래 문제의 크기를 반으로 줄인 부분 문제가 되고, 따라서 재귀 호출을 이용하여 쉽게 만들 수 있다. 맨 처음에 BinarySearch함수의 탐색 범위는 low가 0, high가 n-1이 되어 배열 전체가 탐색 범위가 된다. 재귀 함수의 탈출조건은 low가 high보다 커지는 경우로 이 경우는 탐색 실..
-
3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기C 자료구조/1. 재귀함수 2020. 6. 8. 12:10
피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자. designatedroom87.tistory.com/3?category=868275 2. Fibonacci Sequence( 피보나치 수열 ) 아래는 피보나치 수열의 점화식이다. 아래는 프로그램 소스이다. 아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다. 중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 designatedroom87.tistory.com 아래는 memoization 방법을 이용해 피보나치 수열을 구할 알고리즘이다. 앞서, 피보나치 수열을 구할 때, 이미 구한 항의 값을 다시 구하는 것이 문제라 하였는데, 여기서 기록을 통해 이를 해결하고자 한다. 즉, 기록한 항이 있으면 그 값을 리턴하면 되고,..
-
2. Fibonacci Sequence( 피보나치 수열 )C 자료구조/1. 재귀함수 2020. 6. 8. 11:48
아래는 피보나치 수열의 점화식이다. 아래는 프로그램 소스이다. 아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다. 중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 수열의 4번째 항을 중복으로 구한다. 즉, 이미 알아낸 항의 값을 다시 구하려고 한다. 이에 대한 한 가지 방법은 뒤에서 설명하도록 한다. 아래로 이동해서 중복을 제거하는 방법을 알아보자. designatedroom87.tistory.com/4 3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기 피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자. designatedroom87.tistory.com/3?category=868275 2. Fibonacci Sequence( 피..
-