[Algorithm] 알고리즘 구현 접근법

<알고리즘 구현 접근법>

필자는 알고리즘을, 모든 케이스에 대하여 적절한 결과를 반환하는 것이라고 정의한다

그리고 알고리즘을 구현하는 과정은 아래와 같다

1. 알고리즘을 머릿속에 정리한다

2. 그것을 코드로 구현한다

어떻게 하면 정리를 할수있는걸까?

필자의 경우 아래와 같이 생각하였다

 - 간단한 케이스만 대응가능한 알고리즘부터 작성 후 발전시켜 나가는 것

 - 결과적으로, 모든 케이스들의 규칙을 찾는 것

 - 코드를 간단하게 만드는 것 (ex: 함수로 모듈화하는 것, ex: swap())

<재귀 알고리즘>

자신의 책임(역할)에만 집중한다

탈출조건은 마지막에 생각해도 된다

--------------------------------------

<hannoi top과 approach>

"일반/추상적인 알고리즘"을 바로 디자인하는 게 어렵다면, "구체적인 입/출력"을 통해서 접근해보자.

이 글은 알고리즘을 구현할 때의 접근방법을 설명하고 있다. 그 예로 하노이 탑을 들고 있다.

글로된 설명이라 이해하기 어려울 수 있으나, 이것 하나만 기억하자

"처음부터 일반적인 알고리즘을 작성하는 것은 어렵지만, 가장 간단한 케이스의 알고리즘부터 작성하고 그것을 발전시켜나가는 것은 비교적 쉽다"

N=3일 때의 기대출력결과이다

A B, 

A C, 

B A, 

C B, 

A B,

A C, 

B A, 

B C, 

A C

N=2일 때의 기대출력결과이다

A B

A C

B C

하노이 탑은 재귀호출로 해결할수 있는 알고리즘이다

하지만 두 입출력 결과를 비교해보아도 포함관계를 파악하기 어렵다

어떻게 접근하는게 좋을까?

N=3과 N=2 출력의 공통규칙을 찾는 것이 중요하다

가장 간단한 N=2에서 규칙을 찾고 그것을 좀더 복잡한 N=3에서 찾는 방식으로 접근하자

N=2일 때, 알고리즘을 생각하기 전에 우리의 목표가 무엇인지부터 확인해보자. 두께에 따라 1,2의 원반이라고 하겠다

2개의 원반을 두께 순서대로 3번째에 놓는 것이므로 계획은 아래와 같다

1. 두께 2의 원반을 3번째에 놓는다

2. 두께 1의 원반을 3번째에 놓는다

목표는 이러한데, 1을 바로 실행할 수가 없다

1의 목표를 달성하기 위한 좀더 구체적인 알고리즘을 생각해보자

1-1. 두께 1의 원반을 2번째에 놓는다 (A B)

1-2. 두께 2의 원반을 3번째에 놓는다 (A C)

하노이 탑 알고리즘의 핵심은 목표지점(3번째)에 원반을 놓기 위해, 나머지 한 곳(2번째)을 buffer로서 활용한다는 점이다

이런 알고리즘의 아이디어를 생각하는 것이 가장 어려운 부분이다.

하지만 원반갯수 N에 대하여 알고리즘을 생각하는 것보다는, 구체적인 입/출력을 놓고 그 케이스에 대한 알고리즘을 추상화시키는 것이 더 쉬운 접근방법일 것이다.

목표 2를 달성하는 데에는 문제가 없지만, 처음 계획과 달라진 점이 하나 있다

두께 1의 원반이 1번째가 아닌 2번째로 이동되었다는 점이다

그러므로 B C가 출력될 것이다

N=2의 분석이 끝났으므로, N=3의 케이스도 위와 같이 분석해보는 것이 다음 단계이다

이때 N=2와 공통된 부분을 찾는 것이 중요하다

N=3 케이스를 분석해보면 나머지 한 곳을 buffer로 활용하여 원반을 옮기는 과정이 반복된다는 것을 확인할 수 있다

글이 너무 길어지니 하노이 탑 예시는 여기서 줄이도록 하겠다 (쓰기 힘들다)

위에서 말한 문장만 기억하도록 하자

조금더 복잡한 알고리즘을 구현할수 있게 해주는 접근방법이 될것이다