백준 알고리즘 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;
}

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