5ubin's Blog

  그레이 부호(Gray codes)   하노이의 탑 문제는 단순히 재귀를 설명하기 위해서 만든 문제가 아닙니다. 숫자나 개별 물체들을 생성하는데 아주 밀접한 관계를 가지고 있죠. 그레이 부호를 알아봅시다.   극작가 사뮈엘 베케트는, <고도를 기다리며>로 유명한 극작가입니다. <쿼드>라는 희곡은 재미있는 특성이 있는데요. 빈 무대에서 시작해 등장 인물들이 입장하고 퇴장합니다. 이 때 단 한 명만 입장하거나, 퇴장합니다. 이런 규칙을 통해서, 무대 위에 있는 등장 인물들이 이룰 수 있는 모든 조합이 단 한 번씩만 나타나게 구성되어 있죠. 베케트는 어떻게 이런 구성을 만들 수 있었을까요? 다음 그림을 참고해보세요.   n개의 각기 다른 요소들의 부분집합을 표현하는 방법 중 하나는, n개의 비트를 이용하는 것입니다. 베케트의 문제에서, 값이  1이면 무대에 있음을 의미하는  4-비트열을 이용해 문제를 해결해볼 수 있습니다. 우측부터 첫번째 등장 인물이며, 예를 들어 0101이면 첫번째 등장 인물과 세번째 등장인물이 무대에 올라서 있음을 의미합니다. 이 표현법을 통해 다음 사실을 증명할 수 있는데요. 원소의 개수가 n개인 집합의 부분집합은 2^n개라는 사실입니다. <쿼드>는 4명의 등장 인물들이 등장하므로, 16개의 장면들이 존재함을 알 수 있죠.   n-비트 그레이 부호는 2^n개로 이루어진 서로 다른 n-비트 이진수 목록입니다. 아주 중요한 특징이 있는데, 연속된 수가 단 하나의 비트만 다르다는 점입니다. 베케트의 문제와 그레이 부호는 동일하죠. 단 한 명의 등장인물이 입장하거나 퇴장하는 것은, 곧 그레이 부호에서 비트 하나만 바뀌는 것과 동일한 개념이기 때문입니다.   어떻게 그레이 부호를 생성해낼 수 있을까요? 하노이의 탑에서 우리가 사용했던 것처럼, 재귀적인 방법을 통해서 아주 효과적으로 이 문제를 해결할 수 있습니다. n-비트 이진수로 표현된 그레이 부호는 재귀적으로 다음과 같이 정의될 수 있습니다. (n-1)비트 부호 앞

재귀   우리는 이제껏 한 함수에서 다른 함수를 호출해왔습니다. 만약 어떤 함수가, 자기 자신을 호출하는 건 어떨까요? 자바를 비롯한 대부분의 현대 프로그래밍 언어들은 이런 메커니즘을 제공하고 있습니다. 바로 재귀(recursion)입니다. 이번 절에서 우리는 다양한 문제를 세련되고 효율적으로 해결하는, 재귀에 대해 알아볼 것입니다.   재귀를 사용하면, 더 간편하고 쉽게 이해할 수 있는 프로그램을 만들 수 있습니다. 재귀에 익숙하여 코드에 일상적으로 재귀를 사용할 수 있는 프로그래머들은 사실 흔치 않습니다. 하지만 재귀로 어떤 문제를 우아하게 해결해내는 경험은, 많은 프로그래머들과 심지어 여러분들에게도 귀중한 경험입니다. 재귀 나무   재귀라 함은 꼭 프로그래밍 기법만은 아닙니다. 자연 세계에서도 이는 손쉽게 찾아볼 수 있죠. 재귀 나무는 보다시피 실제 나무를 닮았습니다. 수많은 자연 현상들은 재귀로 표현될 수 있습니다. 다시 말해 재귀를 통한다면, 현실의 수많은 문제들을 해결할 수 있습니다.   이는 재귀를 이용해야 하는 중요한 이유 중에 하나입니다. 굉장히 어려운 수학 문제도, 재귀를 이용하면 직관적이고 쉽게 풀리는 경우가 있습니다. 바로 수학적 귀납법(mathematical induction)에 대한 이야기입니다. 수학 공부 시간이 아니니, 수학적으로 자세히 다루진 않겠지만 재귀는 이 때 굉장히 강력한 힘을 발휘한다는 사실을 기억하세요. 첫 재귀 프로그램   재귀의 <HelloWorld>는 바로 팩토리얼 함수입니다. N!은 N부터 1까지의 곱입니다. N!을 어떻게 계산할 수 있을까요? 우리는 for문을 이용해 쉽게 계산할 수 있을 것입니다. 하지만 이번 시간에는 재귀로 이를 해결해보죠. public static long factorial ( int N ) { if ( N == 1 ) return 1 ; return N * factorial ( N - 1 ); }   이 정적 메소드는 자기 자신을 호출합니다.