그레이 코드 Gray code?

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

즉, 수가 증가할 때, 언제가 1개 비트만 바뀐다고 보면 된다. 

 

	이진	그레이
0	000	000
1	001	001
2	010	011
3	011	010
4	100	110
5	101	111
6	110	101
7	111	100

그레이 코드를 만드는 방법은 다음과 같다.

우선 1비트 그레이 코드를 쓴다.

0

1

 

그리고 그 아래 역순으로 다시 1비트 그레이 코드를 쓴다.

 

0

1

1

0

 

제순으로 쓴 비트 앞에는 0을, 역순으로 쓴 비트 앞에는 1을 붙여준다.

 

00

01

11

10

 

이렇게 n비트 그레이 코드를 이용하여 n+1비트 그레이 코드를 만들 수 있다.

쉽게 정리하자면 n비트 그레이 코드를 적고 앞에 0을 붙인 것과, n비트 그레이 코드를 역순으로 적고 앞에 1을 붙인 것을 이으면 n+1비트 그레이 코드가 된다.

 

코드는 아직 이해 못하겠다ㅠ

 

#include <stdio.h>
void print_gray_reverse(int code[], int n, int index);
 // 그레이 코드 : 연속된 수를 한 비트만 다르게 인코딩 하는 방법.
//즉, 다음 수로 넘어갈 때 언제나 1개 비트만 바뀐다!!

//n을 입력 받아서 n비트 그레이 코드를 출력하는 프로그램.

void print_code(int code[], int len) {
	for (int i = 0; i < len; i++) {
		printf("%d", code[i]);
	}
	printf("\n");
}

void print_gray(int* code, int n, int index) {
	if (n == index) { //목표치에 도달하면 코드 출력
		print_code(code, n);
		return;
	}
	//0비트 자리 수 부터 시작!
	code[index] = 0;
	print_gray(code, n, index + 1);
	code[index] = 1;
	print_gray_reverse(code, n, index + 1);

}

void print_gray_reverse(int code[], int n, int index) {
	if (index == n) {
		print_code(code, n);
		return;
	}

	code[index] = 1;
	print_gray(code, n, index + 1);
	code[index] = 0;
	print_gray_reverse(code, n, index + 1);

}


int main(void) {
	int code[20], n;
	scanf("%d", &n); //n자리수(비트)

	print_gray(code, n, 0);
}

 

---

Reference

https://johngrib.github.io/wiki/gray-code/

문제로 풀어보는 알고리즘(황인욱, 김용혁)