백준 10829 - 이진수 변환

문제링크

• 백준 10829

문제 접근

• 첫번째 접근 방법으로는 자연수 n을 몫이 1이 될때까지 2로 나누면서 나머지를 스택 자료구조로 저장한 후 LIFO(Last-In-First-Out) 방식으로 하나하나 꺼내어 출력하는 방법을 선택했다. 하지만, 메모리초과 문제로 오류를 범했다.
  • 메모리 초과가 났던 이유는 char형 stack 변수에 2bytes 크기의 데이터를 할당하였기 때문이었다. 아래 다른 풀이를 통해 메모리 초과 없이 통과할 수 있다.
• 두번째 접근 방법으로는 첫번째 시도에서 십진수에서 이진수로 변환하는 방법과는 다른 방법을 선택했다. “내림차순 2제곱승과 뺄셈” 방법으로 자연수 n보다 크지않은 2의 제곱수를 배열에 저장한다. 반복문을 통해 오름차순으로 2의 제곱수를 대입했으므로 이진수 변환 과정을 구현할 때 배열의 끝에서부터 접근해야함에 주의했다.
• 2의 제곱수에 내림차순으로 접근하여 자연수 n이 제곱수값보다 크다면 1을 출력하고 자연수 n = n - (현재 제곱수값) 으로 값을 변경한다. 제곱수값보다 작다면 0을 출력하고 그 다음 제곱수값과 비교한다. 자세한 설명은 십진수를 이진수로 바꾸는법 방법2에서 찾아볼 수 있다.
• 마지막 방법은 재귀(recursion)를 이용한 구현이다. 두줄로도 구현이 가능할정도로 정말 간단하다. 워낙 구글링해도 잘 나오는 방법이라 이번 풀이에서는 선택하지 않았다.

의사코드(pseudo-code)

- cin >> n
- vector<unsigned long long> power_two
- power_two.push_back(1)
- val = 2
- while val <= n:
	- power_two.push_back(val)
	- val = val*2
- len = power_two.size()
- tmp = n
- for i=len-1 downto 0:
	- if tmp >= power_two[i]:
		- printf("1")
		- tmp = tmp - power_two[i]
	- else: printf("0") 

소스코드 및 분석

전체 코드

#include <iostream>
#include <vector>

int main()
{
	unsigned long long n;
	std::cin >> n;
	std::vector<unsigned long long> power_two;
	power_two.push_back(1);
	unsigned long long val = 2;
	while (val <= n) {
		power_two.push_back(val);
		val *= 2;
	}
	int len = power_two.size();
	unsigned long long tmp = n;
	for (int i = len - 1; i >= 0; i--) {
		if (tmp >= power_two[i]) {
			printf("1"); tmp -= power_two[i];
		}
		else printf("0");
	}
}

• 입력으로 들어오는 데이터에 맞춰 데이터타입을 설정해주었다.
• 벡터컨테이너로 2의 제곱수값을 입력된 자연수 크기에 따라 저장한다. 이때 앞에서부터 오름차순으로 반복문을 통해 데이터를 대입하고 있으므로 이진수 변환부분을 구현할 때 배열의 뒤에서부터 접근하도록 유의한다.
• 변수 tmp 를 이용해 자연수를 필요시 갱신할 수 있도록한다.

다른 풀이

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	long long N;
	cin >> N;

	stack<int> binary;
	while (true) {
		if (N / 2 == 0) {
			binary.push(1);
			break;
		}
		binary.push(N % 2);
		N /= 2;
	}
	while (!binary.empty()) {
		printf("%d", binary.top());
		binary.pop();
	}
	return 0;
}