42. 그레이 코드 알고리즘 (재귀 프로그래밍)

1. 개요

그레이 코드 알고리즘은 순서만 주의하면 쉬움.

그레이 코드란?

5개의 스위치가 있다.

총 스위치로 만들 수 있는 경우는 2^5승이다.

각각의 스위치를 켜고 끄고를 반복하여 2^5승, 즉 32가지 상태를 점검한다.

그러면 하나의 상태를 확인하기 위해 스위치를 여러번 조작해야한다.

왜냐하면 00000 상태에서 11111상태를 바꾸기 위해선 2가지 상태를 확인하는 것이지만 총 스위치 조작은 5번이다.

즉, 점검해야 할 32가지 경우이지만 이를 확인하기 위해 스위치를 조작하는 횟수는 32가지를 초월한다.

하지만 32번의 스위치 조작으로 32가지의 상태를 확인할 수 있다면?

이것을 가능케하는 것이 그레이 코드다.

그레이 코드는 연속된 수를 한 비트만 다르게 인코딩하는 방법.

연속적으로 변하는 양을 나타낼 때, 변화폭이 작아 오류를 줄일 수 있어 데이터 전송에서 많이 쓰임.

그레이 코드 만드는 방법

현재의 비트를 역순으로 적고

현재의 비트 앞엔 0을, 역순으로 적은 비트 앞엔 1을 붙인다.

예)

3비트 그레이 코드 만드는 법

1비트)

0

1

2비트)

0        00

1        01 

1        11

0        10

3비트)

00        000 

01        001

11        011

10        010

10        110

11        111

01        101

00        100

위에서 아래로 1비트 씩만 변하는 것을 확인할 수 있다.

이 방법 이외에도 XOR 연산을 통해 그레이 코드를 작성할 수 있다.

먼저 맨 앞은 이진 코드를 똑같이 쓰고

현재 이진코드와 다음 이진코드의 XOR 값이 다음 그레이 코드의 값이 된다.

이진 코드 0 1 1 0을 그레이 코드로 바꾸면

0 (똑같이 쓰고)

1 (0과1의 XOR 값)

0 (1과 1의 XOR 값)

1 (1과 0의 XOR 값)

즉, 이진 코드 0 1 1 0의 그레이 코드는 0 1 0 1 이다.

그레이 코드를 작성하기 위해선 엇갈린 재귀 방식이 쓰인다.

엇갈린 재귀란 2개 이상의 재귀 함수가 번갈아서 실행되는 것을 말함.

그러므로 순서에 유의.

또한 재귀에서 문자열 출력을 하려면

필요한 재료는 문자열을 저장할 공간과 그 길이 변수.

항상 재귀의 끝에서 출력해야 한다는 것을 잊지말자.

2. 문제

n을 입력받아서 n비트 그레이 코드를 출력하는 프로그램을 작성하라. (재귀 호출을 통해서)

3. 코드

3-1) 그레이 코드

3-2) 출력

4. 정리

재귀 프로그래밍이 점점 머리속에 깃든다.

이렇게 쉬웠던 걸까.

재귀프로그래밍에서 각 경우를 출력하려면 별도의 메모리 공간이 필요하다는 것.

그리고 출력은 항상 재귀의 끝에서 한다는 것.

끝으로 엇갈리는 경우라면 재귀 함수가 2개 필요하다는 것을 기억.

-> 매개변수를 하나 더 써서 잘 코드를 작성한다면 하나의 재귀 함수로도 그레이 코드를 작성할 수 있다고 한다.

하지만 엇갈린 재귀라도 하나의 매개변수를 더 넣어서 조절하면

하나의 재귀 함수로도 충분히 이 그레이 코드를 작성할 수 있음.