그레이 코드란 무엇인가?
그레이 코드(Gray Code)는 인접한 두 값이 오직 한 비트만 다른 특징을 가지는 이진수 체계입니다. 디지털 회로나 엔코더 등에서 오류를 최소화하기 위해 널리 사용되는 코드 방식입니다.
문제의 조건은 다음과 같습니다. 비트의 총 개수를 나타내는 음이 아닌 정수 n이 주어졌을 때, 그레이 코드 시퀀스 전체를 출력해야 하며, 시퀀스는 반드시 0으로 시작해야 합니다.
예를 들어 입력이 2라면 결과는 [0, 1, 3, 2]가 됩니다. 이유는 다음과 같습니다.
- 0의 그레이 코드 → 00
- 1의 그레이 코드 → 01
- 2의 그레이 코드 → 11
- 3의 그레이 코드 → 10
순서대로 보면 인접한 값끼리 정확히 한 비트씩만 달라지는 것을 확인할 수 있습니다.
문제 해결 접근 방법
이 문제는 의외로 간단한 비트 연산 공식 하나로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.
- 결과를 저장할 배열
ans를 생성합니다. - 0부터 2ⁿ−1까지 각 숫자에 대해 그레이 코드를 계산하여 배열에 추가합니다.
- 그레이 코드 변환 공식: 숫자를 1비트 오른쪽으로 시프트한 값과 원래 숫자를 XOR 연산합니다.
즉, 정수 i의 그레이 코드는 다음 식으로 계산됩니다.
gray(i) = i ^ (i >> 1)
이 공식이 성립하는 이유는, 어떤 이진수를 자기 자신과 1비트 시프트한 값으로 XOR하면 상위 비트들이 하나씩 밀려나면서 인접한 결과값 간에 항상 한 비트의 차이만 발생하기 때문입니다.
C++ 구현 예제
아래 예제 코드를 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> grayCode(int n) {
vector <int> ans;
for(int i =0; i<1<<n; i++){
ans.push_back(i^(i>>1));
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.grayCode(4));
}입력
4
출력
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
출력 결과 분석
n = 4인 경우 2⁴ = 16개의 그레이 코드가 생성됩니다. 각 값을 4비트 이진수로 표현하면 다음과 같습니다.
- 0(0000) → 1(0001) → 3(0011) → 2(0010)
- → 6(0110) → 7(0111) → 5(0101) → 4(0100)
- → 12(1100) → 13(1101) → 15(1111) → 14(1110)
- → 10(1010) → 11(1011) → 9(1001) → 8(1000)
모든 인접한 값 사이에서 정확히 한 비트만 변경되는 것을 확인할 수 있습니다. 이처럼 그레이 코드는 단순한 XOR·시프트 연산만으로 O(2ⁿ) 시간 안에 효율적으로 생성할 수 있습니다.