본문 바로가기
코딩과 알고리즘

백준 알고리즘 3460. 이진수

반응형

오늘의 백준 알고리즘 문제 풀이는 3460번입니다.

오늘도 미래의 기술 코딩과 연관된 알고리즘을 공부하시는 분들에게도 도움이 되고자 글 올리는군요 :)

2진수는 컴퓨터가 좋아하는 숫자이지요.

백준 알고리즘에서 제시하는 문제 살펴볼까요?

문제

양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 106)

출력

각 테스트 케이스에 대해서, 1의 위치를 공백으로 구분해서 줄 하나에 출력한다. 위치가 낮은 것부터 출력한다.

예제 입력

1

13

예제출력

0 2 3

해설

2진수를 처음 접하시는 분에게는 어려운 문제일 수도 있는데요.

2진수란, 이렇게 생각하시면 됩니다.

발굽이 2개인 똑똑한 피그가 있다고 칩시다.

10진법을 쓰는 사람이

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

이렇게 세듯이

똑똑한 피그는 0과 1밖에 셀수가 없고, 1 다음 숫자는 한자리 올려서 10을 세기 때문에

2진법을 쓰는 피그는

0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, ...

이렇게 숫자를 세는 것이지요.

이 것이 바로 2진수입니다.

만일 10진수로 열 한번째 숫자는 10이지만,

2진수로 열 한번째 숫자는 1010 입니다.

하지만 10진수든 2진수든 표현하는 수치만 다르지 동일한 숫자값이지요.

그걸 구하는 프로그램을 짜는 것인데 사실 컴퓨터는 2진수를 좋아하고

원래부터 2진수를 기본으로 가져가기 때문에 해당 기능을 활용하면

광속(?)으로 풀이가 가능합니다.

우선 T는 몇번의 입력이 주어지는가에 대한 테스트 케이스 횟수를 입력받는 것이니

단순히 아래와 같이 횟수를 입력받고

입력된 t의 횟수만큼 루프를 돌려주면 됩니다.

 

int t;
scanf("%d", &t);
for (long i = 0; i < t; ++i){
      :
}

그 다음에 주의하실 부분이 있는데요.

입력되는 숫자값이 10의 6승이라고 합니다.

10의 6승이면 0을 6개붙여서 1000000 의 숫자가 입력된다고 하는데요.

다음과 같이 쓰면 분명 오류가 납니다.

초심자분들이 많이 실수하시는 부분인데요.

 

int n;
scanf("%d", &n);

왜냐구요? int 로 선언된 변수는 -32768 ~ 32767까지의 범위값만을 가지기 때문이지요.

1000000 이란 숫자를 입력하자마자 범위 초과로 런타임 오류가 나버립니다.

그러니까 다음과 같이 써주시면 됩니다.

long n;
scanf("%ld", &n);	// 1000000

long 으로 선언된 변수는 -2147483648 ~ 2147483647 이란 숫자값의 범위를 가집니다. 1000000 숫자를 충분히 담을 수 있는 범위이지요.

그리고 long 형태의 변수를 scanf 로 읽으실때는 반드시 %d 가 아닌 %ld로 읽어주셔야 합니다.

그 다음 문제에 제시된대로 최하위 비트부터 출력을 할 차례인데요.

최하위 비트란 2진수 1000111001100 이란 숫자가 있다고 할 때. 빨간색으로 표시된 부분을 말합니다. 10진법으로 1의 자리와도 같지요.

최하위 비트부터 출력하려면 어떻게 해야 할까요?

2진수 1, 10, 100, 1000, ... 등 한자리씩 자릿수를 올려가며 그 해당 자릿수의 숫자 1이 있는 경우 순서대로 출력하면 됩니다.

'최하위 비트의 위치는 0이다'라고 주어졌기 때문에 제일 아랫자리에 1이 있는 경우 0을 출력해주면 됩니다.

그러려면 1, 10, 100을 셀 변수가 있어야 겠지요?

아래 소스에서 chk 가 바로 그 변수입니다.

 

int bit = 0;
for (long chk = 1; chk<=n; chk<<=1)
{
         :
    bit++;
}

chk <<=1 이라고 써진 부분은 chk 를 컴퓨터가 알아서 2진수 10을 곱해서 올려준다고 생각하시면 됩니다.

그러면 for 문이 반복됨에 따라 chk 값은 2진수 1, 10, 100, 1000, 의 숫자값을 가지게 되는데 10진수로는 1, 2, 4, 8, .. 로 2배의 숫자값을 의미합니다.

bit 라는 변수가 하나 더 있는데, 단순히 몇번째 자릿수인지를 세는 용도입니다.

이제 해당 자릿수에 숫자가 있는지 없는지애 따라 몇번째 1이 있는지 출력해야 하는데요.

10진수라면 좀 번거로운 과정을 거쳐야겠지만, 2진수는 그럴 필요가 없습니다.

관련된 기능이 있거든요. 바로 비트 연산입니다.

 

if (n & chk)printf("%d ", bit);

n & chk 는 n값과 chk 값의 2진수간의 비트연산 AND 값을 수행해서 결과를 내줍니다.

이를 테면 n값이 7이고 chk값이 2라면,

2진수로 n값은 111, chk 값은 10 이 됩니다.

2진수 AND 연산은 다음과 같이 생각하시면 됩니다.

양쪽을 똑같이 자릿수를 맞춰놓고,

111

010

위 아래가 똑같이 1인 경우에만 결과값 1을 내놓고, 그 외에는 0을 내놓습니다.

결과 -> 010

그리고 if (n & chk) 비교문의 경우 0이 아닌 경우는 모두 참(true) 로 판단해서 if문 내부의 명령을 실행합니다.

만일 제시된 숫자값이 200 이라면 다음과 같은 결과가 실행됩니다.

200은 2진수로 128 + 64 + 8 이므로 11001000 입니다.

이 숫자값은 for 문이 반복됨에 따라 다음과 같은 비교과정을 거치게 됩니다.

n : 11001000

chk : 00000001

AND연산 : 00000000

bit : 0 / 아무것도 출력안함

n : 11001000

chk : 00000010

AND연산 : 00000000

bit : 1 / 아무것도 출력안함

n : 11001000

chk : 00000100

AND연산 : 00000000

bit : 2 / 아무것도 출력안함

n : 11001000

chk : 00001000

AND연산 : 00001000

bit : 3 / "3" 출력

n : 11001000

chk : 00010000

AND연산 : 00000000

bit : 4 / 아무것도 출력안함

n : 11001000

chk : 00100000

AND연산 : 00000000

bit : 5 / 아무것도 출력안함

n : 11001000

chk : 01000000

AND연산 : 01000000

bit : 6 / "6" 출력

n : 11001000

chk : 10000000

AND연산 : 10000000

bit : 7 / "7" 출력

최종 출력결과는 "3 6 7" 입니다.

마무리로 반복문을 끝낸다음 개행문자를 출력하며 끝냅니다.

printf("\n");

설명이 좀 부족할 수도 있을지 모르는 점 양해 부탁드리며

자세히 알고 싶으신 분 계시면 문의 주세요.

전체 소스 게제합니다.

여기까지 읽어 주셔서 감사합니다 :)

#include <iostream>
#include <cstring>
#include <string>
using namespace std; 

// 이진수
void Result()
{
	int t;
	scanf("%d", &t);
	for (long i = 0; i < t; ++i)
	{
		long n;
		scanf("%ld", &n);	// 1000000
		int bit = 0;
		for (long chk = 1; chk<=n; chk<<=1)
		{
			if (n & chk)printf("%d ", bit);
			bit++;
		}
		printf("\n");
	}

}

int main()
{
	Result();
	return 0;
}

백준사이트에서 크레이의 등수놀이는 계속됩니다 :)

반응형