설명
- 그레이 코드라는 것이 있음
- 0000..000으로 시작해서 한군데만 바꿔가면서 나열함. 중복 안됨, 모든 숫자나와야함, 끝은 시작과 연결되어야함
- 서로 인접하는 조건이 주어짐(최대 두개). 조건을 만족하는 그레이코드 구하기
접근
- 일단 아무 그레이코드를 만든다
- 재귀적으로 생각해본다
- {.....}의 그레이코드를 만들었으면 가장 앞자리에 "1"을 붙이면 <.....>가 만들어진다고 치면
- <.....>는 자체적으로도 그레이코드이면서 {.....}와는 다름
- {.....}의 가장 끝에서 역순으로 <.....>를 만들고 서로 붙이면 새로운 거대한 그레이코드가 만들어짐
- ex) {......, 10001} ==> <"1"10001, "1".....>
- 잘 생각해보면 이미 만들어진 그레이코드를 이용할 수 있는 방법과 이유를 깨닫게 됨
- 이렇게 만든 그레이코드의 특징
- 가장 많은 변화가 생기는 부분은 가장 낮은 자리
- 가장 적은 변화가 생기는 부분은 가장 높은 자리
- 조건을 분석한다
- 두 숫자가 주어질텐데, 바뀌는 비트가 1개보다 크면 못만듬
- 바뀌는 비트가 어느 자리인지 살펴봄 : 0번째인지, 1번째인지...
- 그레이코드를 적절히 변경한다
- 그레이코드에 나온 비트의 자리를 서로 바꾸어도 여전히 그레이코드임(예를들어 모든 그레이코드에서 1번자리와 5번자리를 바꾼 새로운 코드도 그레이코드)
- 그레이코드에 임의의 X를 xor시켜도 여전히 그레이코드임(인접한 두 비트는 달라지는 빼고는 동일한 xor 결과를 내보낼것이므로)
- 조건 분석에서 살펴본 바뀌는 비트 부분이 각각 0번째, 1번째 자리로 가도록 비트의 순서를 바꿈
- 바뀌는 비트 부분이 동일하거나, 0번째 1번째인 경우는 알아서 예외처리
- 비트가 가장 높은 자리이면 답이 나올수 있는데도 못찾음...결국 많이 바뀌는 부분으로 치환하고 여러 경우의 수를 찾는 것이 유리했음
- 이 부분은 언제나 항상 옳은 답이 나오는지 명확하게 증명은 못했지만, 대략 모든 숫자를 그레이코드로 표현하려면 많이 바뀌는 부분과 적게 바뀌는 부분이 나올 것 같고(1,2,4,8,..) 모든 숫자로 변환되 될 것 같고.... 대략적으로 그럴 것 같은 추측이 든다
- 그레이코드를 완전탐색하면서 조건이 적용될 수 있는지 살펴본다
- 일단 조건에서 바뀌는 비트가 가장 많이 바뀌는 곳으로 치환한 상태이고
- 조건에 나온 숫자를 그레이코드중에 하나로 변환한다고 치면... 이때 적절한 X로 xor를 하면 변환이 된다고 보면
- 그레이코드에 X로 xor 변환을 하고
- 조건들이 서로 인접해있는지 확인하면 답인지 아닌지 알 수 있음
- index 배열 + 적절한 xor이면 인덱스를 바로 알 수 있음
- 이런식으로 모든 그레이코드 요소에대해서 완전탐색을 해봄
newbieski