9896번 - Gray
이진수는 2진법으로 표현된 수이며, 각 자릿수 또는 비트는 2의 거듭제곱의 가중치를 가집니다. 예를 들어, 십진수 23은 이진수로 10111로 표현됩니다:
(1 × 24) + (0 × 23) + (1 × 22) + (1 × 21) + (1 × 20) = (1 × 16) + (1 × 4) + (1 × 2) + (1 × 1) = 23
Gray 코드 수열은 이진수 값들의 수열로, 각 값은 바로 이전 값과 단 하나의 비트만 다릅니다. 다음 예시는 3비트 이진수의 표준 Gray 코드 수열을 보여줍니다.
이진수를 표준 Gray 코드 값으로 변환하는 매우 간단한 알고리즘이 있습니다. 예를 들어, 이진수 011을 변환하려면 첫 번째 비트를 복사하는 것으로 시작합니다:
0 1 1 v 0
두 번째 비트를 얻기 위해, 주어진 이진수의 첫 번째와 두 번째 비트를 더해 합 0 + 1 = 1을 얻습니다:
0 + 1 1 v 0 1
세 번째 비트를 얻기 위해, 두 번째와 세 번째 비트를 더해 합 1 + 1 = 10(이진수)을 얻지만, 올림수는 버리고 합의 가장 오른쪽 비트인 0만 취합니다:
0 1 + 1 v 0 1 0
따라서 우리의 답은 010입니다.
일반적으로, 첫 번째 비트를 제외하고, 표준 Gray 코드의 k번째 비트는 주어진 이진수의 (k-1)번째 비트와 k번째 비트를 더하고 올림수를 버림으로써 얻습니다. 올림수를 버리는 덧셈 연산은 다음과 같이 완전히 설명될 수 있습니다:
0 0 1 1 + 0 + 1 + 0 + 1 --- --- --- --- 0 1 1 0 --- --- --- ---
다른 예로, 5비트 이진수 10101은 위의 알고리즘을 적용하여 표준 Gray 코드 값 11111로 변환됩니다. 아래 표는 몇 가지 더 예시를 보여줍니다.
당신은 n비트 이진수를 해당하는 n비트 표준 Gray 코드 값으로 변환하는 프로그램을 작성해야 합니다. 여기서 1 ≤ n ≤ 20 입니다.
입력은 두 줄로 구성되며, 각 줄은 하나의 정수를 포함합니다.
출력은 주어진 n비트 이진수에 해당하는 표준 Gray 코드를 나타내는 길이 n의 비트 문자열을 포함합니다.
3 011
010
댓글을 작성하려면 로그인해야 합니다.
hanzch 1년 전
Gray 코드
문제
이진수는 2진법으로 표현된 수이며, 각 자릿수 또는 비트는 2의 거듭제곱의 가중치를 가집니다. 예를 들어, 십진수 23은 이진수로 10111로 표현됩니다:
(1 × 24) + (0 × 23) + (1 × 22) + (1 × 21) + (1 × 20) = (1 × 16) + (1 × 4) + (1 × 2) + (1 × 1) = 23
Gray 코드 수열은 이진수 값들의 수열로, 각 값은 바로 이전 값과 단 하나의 비트만 다릅니다. 다음 예시는 3비트 이진수의 표준 Gray 코드 수열을 보여줍니다.
이진수를 표준 Gray 코드 값으로 변환하는 매우 간단한 알고리즘이 있습니다. 예를 들어, 이진수 011을 변환하려면 첫 번째 비트를 복사하는 것으로 시작합니다:
두 번째 비트를 얻기 위해, 주어진 이진수의 첫 번째와 두 번째 비트를 더해 합 0 + 1 = 1을 얻습니다:
0 + 1 1 v 0 1세 번째 비트를 얻기 위해, 두 번째와 세 번째 비트를 더해 합 1 + 1 = 10(이진수)을 얻지만, 올림수는 버리고 합의 가장 오른쪽 비트인 0만 취합니다:
0 1 + 1 v 0 1 0따라서 우리의 답은 010입니다.
일반적으로, 첫 번째 비트를 제외하고, 표준 Gray 코드의 k번째 비트는 주어진 이진수의 (k-1)번째 비트와 k번째 비트를 더하고 올림수를 버림으로써 얻습니다. 올림수를 버리는 덧셈 연산은 다음과 같이 완전히 설명될 수 있습니다:
다른 예로, 5비트 이진수 10101은 위의 알고리즘을 적용하여 표준 Gray 코드 값 11111로 변환됩니다. 아래 표는 몇 가지 더 예시를 보여줍니다.
당신은 n비트 이진수를 해당하는 n비트 표준 Gray 코드 값으로 변환하는 프로그램을 작성해야 합니다. 여기서 1 ≤ n ≤ 20 입니다.
입력
입력은 두 줄로 구성되며, 각 줄은 하나의 정수를 포함합니다.
출력
출력은 주어진 n비트 이진수에 해당하는 표준 Gray 코드를 나타내는 길이 n의 비트 문자열을 포함합니다.
예제 입력 1
예제 출력 1