IT/모바일
저자: 김대곤
* 알고리즘에 발가락 담그기
* 알고리즘의 Complexity 또는 계산복잡도
* 탐욕 알고리즘(Greedy Algorithm)
* 동적 프로그래밍(Dynamic Programming) – 고급 설계 기법인가?
* Induction과 병합 정렬(Merge Sort) 알고리즘
Induction을 우리나라 말로 하면, “귀납법”인데. 그러면 당장 “연역법”이 생각난다. 야후 국어사전에 따르면 귀납법은 “개별적인 사실이나 원리를 전제로 하여 일반적 사실이나 원리로서의 결론을 이끌어 내는 연구 방법”이다. 귀납법에 “수학적”이라는 말이 붙으면 수학과 조금이라도 관련이 있는 책이면, 항상 처음으로 다루는 매우 강력한 논리적 증명의 도구가 된다. 그런데 들을 때는 다 맞는 이야기인 것 같은데, 돌아서면 꼭 사기꾼에게 속은 느낌이 든다.
다음 문제를 생각해 보자. 체스 보드는 총 64개의 타일로 되어 있다. 만약 그 중에 하나가 떨어져 나가 구멍이 생겼다고 하자. 그 구멍난 보드를 다음과 같은 조각의 블럭으로 구멍난 보드를 채울 수 있는가 하는 문제를 생각해 보자.(불럭은 회전가능하다)
첫 번째는 가능한가 가능하지 않은가를 결정해야 한다. 또는 구멍의 위치에 따라서 가능여부가 달라진다던가. 여기서 필자의 답은 가능하다는 것이다. 이제 증명해 보이겠다. 먼저 체스 보드를 4 분등 하자. 여기서 개별적인 원리는 4 등분한 작은 체스 보드에 하나의 구멍이 났으면 위에 있는 블럭으로 채울 수 있다는 것이다.
그림1[Figure 1]에서 보는 바와 같이 2번 보드는 구멍 하나가 나 있으니 가정에 의해서 채울 수 있다. 그러면 나머지는 어떻게 채우는가? 그림2에서 보듯이 하나의 블럭을 그림과 같이 놓는다. 그러면 이제 각 보드들은 구멍이 하나씩 있는 셈이 되므로 각 판을 채울 수 있다. 그러므로 64개의 타일로 구성된 체스 보드에 구멍이 하나 있으면 위의 블럭으로 채울 수 있다. 그러면 이런 의문이 떠오른다. 16개의 타일로 된 보드에 하나의 구멍이 있으면 채울 수 있는지 어떻게 확신할 수 있는가? 그럼 작은 보드를 더 작게 만들어 보자.
4개의 타일로 구성된 타일을 생각해 보자. 어디에 구멍이 나 있든지 나머지 보드는 블럭 그 자체이므로 채우는데 아무 문제가 없다. 앞에서 했던 그 방법대로 하나의 블럭을 나머지 세 개 보드들에 하나씩 걸치게 놓으면 된다. 일반화된 결론은 한 면이 2의 거듭제곱인 어떠한 보드에 단 하나의 구멍만 있다면 위의 블럭으로 채울 수 있다는 것이다.
수학적 귀납법이 단지 증명의 도구인 것은 아니다. 만약 사용자로부터 구멍의 위치를 입력받고 체스 보드를 주고 실제로 블럭들로 채우는 프로그램을 짜게 되었다고 하자. 그러면 위의 증명 방식은 바로 프로그램의 뼈대인 알고리즘이 된다. 대부분의 재귀 프로그램(Recursive Program)들은 이러한 원리 위에 있다.
회사에 다닐 때는 거의 재귀 호출 프로그램을 짜는 일이 거의 없었다. 조금은 위험스러운 일이기 때문이다. 무한 루프가 된다거나 에러가 생기면 찾기도 힘들고. 거짓말이 매력적이듯 Induction이 매우 매력적으로 보이는데, 거짓말처럼 들려서 그런지 자주 이해하기가 힘든 것도 사실이다. 참신한 귀납법 예를 만나게 되면 다시 한 번 찾아올 것을 약속하면서 글을 마치고자 한다.
* 알고리즘에 발가락 담그기
* 알고리즘의 Complexity 또는 계산복잡도
* 탐욕 알고리즘(Greedy Algorithm)
* 동적 프로그래밍(Dynamic Programming) – 고급 설계 기법인가?
* Induction과 병합 정렬(Merge Sort) 알고리즘
Induction을 우리나라 말로 하면, “귀납법”인데. 그러면 당장 “연역법”이 생각난다. 야후 국어사전에 따르면 귀납법은 “개별적인 사실이나 원리를 전제로 하여 일반적 사실이나 원리로서의 결론을 이끌어 내는 연구 방법”이다. 귀납법에 “수학적”이라는 말이 붙으면 수학과 조금이라도 관련이 있는 책이면, 항상 처음으로 다루는 매우 강력한 논리적 증명의 도구가 된다. 그런데 들을 때는 다 맞는 이야기인 것 같은데, 돌아서면 꼭 사기꾼에게 속은 느낌이 든다.
다음 문제를 생각해 보자. 체스 보드는 총 64개의 타일로 되어 있다. 만약 그 중에 하나가 떨어져 나가 구멍이 생겼다고 하자. 그 구멍난 보드를 다음과 같은 조각의 블럭으로 구멍난 보드를 채울 수 있는가 하는 문제를 생각해 보자.(불럭은 회전가능하다)
첫 번째는 가능한가 가능하지 않은가를 결정해야 한다. 또는 구멍의 위치에 따라서 가능여부가 달라진다던가. 여기서 필자의 답은 가능하다는 것이다. 이제 증명해 보이겠다. 먼저 체스 보드를 4 분등 하자. 여기서 개별적인 원리는 4 등분한 작은 체스 보드에 하나의 구멍이 났으면 위에 있는 블럭으로 채울 수 있다는 것이다.
그림1[Figure 1]에서 보는 바와 같이 2번 보드는 구멍 하나가 나 있으니 가정에 의해서 채울 수 있다. 그러면 나머지는 어떻게 채우는가? 그림2에서 보듯이 하나의 블럭을 그림과 같이 놓는다. 그러면 이제 각 보드들은 구멍이 하나씩 있는 셈이 되므로 각 판을 채울 수 있다. 그러므로 64개의 타일로 구성된 체스 보드에 구멍이 하나 있으면 위의 블럭으로 채울 수 있다. 그러면 이런 의문이 떠오른다. 16개의 타일로 된 보드에 하나의 구멍이 있으면 채울 수 있는지 어떻게 확신할 수 있는가? 그럼 작은 보드를 더 작게 만들어 보자.
4개의 타일로 구성된 타일을 생각해 보자. 어디에 구멍이 나 있든지 나머지 보드는 블럭 그 자체이므로 채우는데 아무 문제가 없다. 앞에서 했던 그 방법대로 하나의 블럭을 나머지 세 개 보드들에 하나씩 걸치게 놓으면 된다. 일반화된 결론은 한 면이 2의 거듭제곱인 어떠한 보드에 단 하나의 구멍만 있다면 위의 블럭으로 채울 수 있다는 것이다.
수학적 귀납법이 단지 증명의 도구인 것은 아니다. 만약 사용자로부터 구멍의 위치를 입력받고 체스 보드를 주고 실제로 블럭들로 채우는 프로그램을 짜게 되었다고 하자. 그러면 위의 증명 방식은 바로 프로그램의 뼈대인 알고리즘이 된다. 대부분의 재귀 프로그램(Recursive Program)들은 이러한 원리 위에 있다.
회사에 다닐 때는 거의 재귀 호출 프로그램을 짜는 일이 거의 없었다. 조금은 위험스러운 일이기 때문이다. 무한 루프가 된다거나 에러가 생기면 찾기도 힘들고. 거짓말이 매력적이듯 Induction이 매우 매력적으로 보이는데, 거짓말처럼 들려서 그런지 자주 이해하기가 힘든 것도 사실이다. 참신한 귀납법 예를 만나게 되면 다시 한 번 찾아올 것을 약속하면서 글을 마치고자 한다.
TAG :
최신 콘텐츠