순회

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

순회 알고리즘(Iterative)의 개념

• 자신이 직접 구했던 이전 값을 기반으로 정답을 계산하며.

• 순차적으로 계산이 이루어지는 방식.

여기서 순차적이란 용어는 처음부터 정답까지 모든 경우를 차례대로 계산한다는 의미로 사용되었다.

N=10인 경우의 정답을 구하기 위해 N=0, .. ,9인 경우의 정답까지 전부 구해놓는다는 의미이다.

N=10와 전혀 상관없는 케이스의 정답도 전부 구해놓는다.

또한 각 케이스의 결과는 순차적으로 구해지나, 중간결과로써 병렬적으로 계산될 수 있다.

N=0의 결과가 N=1, ..., N 을 계산하는데 필요하다면, 각 공간에 중간값으로써 저장해놓는 것 이다.

아래는 순차적으로 구해지나, 중간결과가 병렬적으로 계산되는 피보나치 함수 알고리즘이다.

각 중간결과를 계속하여 누적함으로써, 각 케이스의 최종결과가 계산되고 있다.

재귀 알고리즘(Recursion)와의 비교

• 재귀는 이전값을 얻기 위해, 또 다른 자신을 호출한다.
• 재귀는 순차적으로 계산이 이루어지지 않을 수 있다.

N=10인 경우의 정답을 구하기 위해,  관련된 케이스의 정답만을 계산한다.

N=10의 정답을 구했더라도 N=0, .., 9는 구해지지 않았을 수 있다.

재귀는 이전값을 얻는 과정에서 아래로 인한 성능저하가 발생할 수 있다.

• 함수호출 오버헤드

• 중복계산 오버헤드

순회 알고리즘의 성능

순회 알고리즘은 재귀에 비해 구현이 어렵고 복잡하지만, 

재귀와 달리 호출스택을 많이 소비하지 않고, 불필요한 중복계산을 하지 않는다.

모든 케이스의 결과를 계산하더라도 상당히 빠르다는 것 인데,

한 케이스만 계산하는 재귀보다야 느릴 수 있겠지만,

모든 케이스를 계산하는 재귀에 비해 월등히 빠르다.

예제 # N번째 피보나치 수

순회(1)

순회(2)

재귀

예제 # N의 약수의 개수 구하기

순회

여기서는 각각의 케이스가 독립이므로, 

모든 경우의 정답을 구해두는 것이 굉장한 낭비로 보일 수 있을 것 이다.

하지만 독립이 아닌 문제(N=10을 구하기 위해 N=5를 계산해야 하는 경우)를 풀어야 하는 경우도 있다.

이 경우에는 0부터 9까지 미리 정답을 구해놓아야 한다.

순차적으로 문제를 해결하는 접근방법이 순회라는 것을 기억하자.

재귀