[C++로 쉽게 풀어쓴 자료구조] 7장 순환 요점정리

안녕하세요 공대생 블로거 여니입니다.

오늘은 7장 순환 요점정리 포스팅을 해보도록  하겠습니다.

(C++로 쉽게 풀어쓴 자료구조 책을 참조하여 글을 쓰고 있습니다.)

 

 

 

1. 거듭제곱 계산

제일 먼저 거듭제곱 계산하는 프로그램에 대해 살펴보도록 하겠습니다.

반복문을 사용하는 방식과 순환 함수를 사용하는 방식 총 2가지가 있습니다.

 

알고리즘을 살펴보면,

만약 거듭제곱이 0이면 1을 반환하고 거듭제곱 n이 짝수, 홀수일 경우를 나눠서 return 해줍니다.

내용출처 C++로 쉽게풀어쓴 자료구조

순환적인 거듭제곱 계산 프로그램에서도 반복문을 사용할 때와 차이가 별로 없습니다. 단지 자기 자신을 호출한다는 점 빼고는요.

 

 

 

2. 피보나치 프로그램

이번에는 피보나치 프로그램에 대해 살펴보도록 하겠습니다.

여기서도 순환과 반복 2가지 방식으로 코딩하는 방법이 있어요.

 

fib(3) = fib(2) + fib(1)

fib(3) = fib(1) + fib(0) + fib(1)

fib(3) = 1 + 0 + 1 = 2

이런 식으로 피보나치를 계산하는 거 다들 알고 계시죠!?

fib(0)= 0이고 , fib(1)=1로 정해져 있고요.

만약에 fib(4)를 구하고 싶다면?

fib(4) = fib(3) + fib(2)를 계산해주면 됩니다.

즉 fib(n) = fib(n-1) + fib(n-2)

 

 

내용출처 C++로 쉽게풀어쓴 자료구조

 

마지막으로 하노이 함수에 대해 살펴보도록 하겠습니다.

 

 

내용출처 C++로 쉽게풀어쓴 자료구조

 

하노이탑이 가장 복잡하더라고요.

근데 구조만 파악하면 바로 이해가 가능합니다.

(왼쪽) from, tmp, to (오른쪽)

하노이탑은 from에 있는 원판들을 쌓여있는 순서 그대로 to로 옮겨야 하는 게임입니다.

그래서 from에 있는 원판들 중에서 맨 아래에 있는 원판만을 빼고 tmp로 옮깁니다.

그러고 난 뒤에 from에 홀로 남겨져있는 원판을 to로 옮겨주고 tmp로 옮겨놨던 원판들을 그대로 다시 to로 가져오면 게임 끝입니다.

 

코드를 잘 보시면 이해되리라 믿습니다.

구독과 좋아요는 좋아요!