이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
02 - 1 함수의 재귀적 호출의 이해
EX.1 피보나치 수열
피보나치 수열의 5번째 항을 예시로 구해보자.
EX.2 별찍기 - 10
(참고) https://velog.io/@honeyricecake/%EB%B3%84%EC%B0%8D%EA%B8%B0-10
N = 27일 때를 예시로 보자.
이렇게 이해하고나면 재귀에 대한 이해도가 한층 높아지고 이후 재귀함수의 호출에 대해 모든 순서를 고민해보지 않아도 스스로의 논리에 대한 의심없이 구현할 수 있게 될 것이다.
02 - 2 재귀의 활용
이진탐색 알고리즘의 재귀적 구현
<재귀로 구현할 수 있다는 확신을 가질 수 있는 이유>
mid = (first + last) / 2 로 구하고
arr[mid]가 target과 같은지 검사하는 일련의 과정을 반복하기 때문
내 코드
int binsearch(int* arr,int first, int last, int target)
{
if (first >= last) return -1;
int mid = (first + last) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binsearch(arr, first, mid - 1, target);
else return binsearch(arr, mid + 1, last, target);
}하노이 타워
https://www.acmicpc.net/problem/11729
아이디어
1개 더 원반을 추가하면
원래 1번에 있던 원반을 3번으로 옮기는 과정을 2번으로 옮기는 과정으로 바꾸면 되므로
함수를
Hanoi(n, from, by, to)라 하면
처음에는 Hanoi(n -1 , from, to , by)를 출력하면 된다.
그리고 1 3 을 출력한 후
원래 1번에 있던 원반을 3번으로 옮기는 과정이 2번에 있는 원반을 3번으로 옮기는 과정이 되므로
Hanoi(n - 1,by, from, to)를 출력하면 된다.
내 코드
#include <stdio.h>
void Hanoi(int n, char from, char by, char to)
{
if (n == 1) printf("%d %d\n", from, to); // n이 1이면 당연히 from에서 to로 이동, 그리고 from과 to가 바뀌면 즉, Hanoi(1, from, to ,by)가 들어오면 당연히 n == 1에서도 from에서 원래 by였던 곳으로 간다.
이는 Hanoi(N,1,2,3)에서 Hanoi(N,1,3,2)를 받으면 by가 3이 되고 to가 2가 된다고 해석해도 된다.
else
{
Hanoi(n - 1, from, to, by);
printf("%d %d\n",from,to);
Hanoi(n - 1, by, from, to);
}
}
int main()
{
int x, N;
int y = 1;
scanf("%d", &N);
x = N;
while (x--)
{
y *= 2;
}
printf("%d\n", y - 1);
Hanoi(N, 1, 2, 3);
return 0;
}또는
#include <stdio.h>
void Hanoi(int n, char from, char by, char to)
{
if(n == 1) printf("%d %d", from, to);
else if (n == 2)
{
printf("%d %d\n", from, by);
printf("%d %d\n", from, to);
printf("%d %d\n", by, to);
}
else
{
Hanoi(n - 1, from, to, by);// Hanoi(n - 1, 1,3,2)
즉, 여기서는 출발지가 1 경유지가 3 목적지가 2
printf("%d %d\n",from,to);
Hanoi(n - 1, by, from, to);
// 여기서는 출발지가 2 경유지가 1 목적지가 3
}
}
int main()
{
int x, N;
int y = 1;
scanf("%d", &N);
x = N;
while (x--)
{
y *= 2;
}
printf("%d\n", y - 1);
Hanoi(N, 1, 2, 3);
return 0;
}두번째 코드가 처음에 메모리가 초과됐었다.
n = 1을 불러오는 과정에서 시간이 많이 걸릴 것 같아서 n == 2를 바로 썼는데
n == 1일때를 따로 적어주지 않아서 else 문에 들어가서
n이 무한히 줄어들었기 때문이다.
재귀함수의 시간을 줄이고자 할 때 각별히 주의해야할 점인 것 같다.
또 다른 교훈도 얻었다.
백준에서 에러가 나면 다 이유가 있다
이게 안 될리가 없다고 하지 말고 조금 수정해보고 막 제출하지 말자...
흑흑......
