[알고리즘][문제풀이][C++] 두 이진수 더하기

 

 

문제

원소가 n개인 두 배열 A, B에 저장된 두 개의 n비트 이진수를 더하고 원소가 n+1개인 배열 C에 저장해 그 결과를 출력하라.

---

설계

1. 배열 A, B에 이진수를 저장하고 그 값을 더해 배열 C에 그림과 같이 저장한다. 

 

2. 배열 C의 $ 2^{0} $ 자리부터 받아올림을 시작한다. 이때, 배열 C의 원소에 가능한 수는 0, 1, 2, 3 뿐이다.

    2-1. 배열 C의 원소가 0, 1이면 continue

    2-2. 배열 C의 원소가 2면 해당 인덱스의 원소값을 0으로 바꾸고, 다음 자리 + 1

    2-3. 배열 C의 원소가 3이면 해당 인덱스의 원소값을 1로 바꾸고, 다음 자리 + 1

---

코드

두 이진수를 더한 값을 배열 C에 저장하는 코드는 다음과 같다.

for(int i=0;i<N;i++){
	C[i+1] = A[i] + B[i];
}
C[0] = 0;

 

이후 배열 C에서 받아올림을 하는 코드는 다음과 같다.

for(int i=N;i>=0;i--){
	if(C[i] == 0 || C[i] == 1) continue;
	else if(C[i] == 2){		// 2면 0으로 바꾸고 다음 자릿수 +1
		C[i] = 0; C[i-1] += 1;
	}
	else{		// 3이면 1로 바꾸고 다음 자릿수 +1
		C[i] = 1; C[i-1] += 1;
	}
}

---

실행 결과

main함수에 이것저것 추가해주고 코드를 돌려보면 다음과 같이 잘 작동하는 것을 볼 수 있다.