티스토리 뷰
어젠가 그저껜가, 트위터를 하는데 어떤 개발자가 쓴 트윗 몇 개가 RT로 넘어왔다.
자기가 면접을 본다는 걸로 봐선 꽤 경력이 많은 개발자인 것 같은데 내용을 대충 요약하면 이렇다.
온라인으로 코딩 면접을 보는데 요즘 지원자들 너무 못해서 수준을 낮췄다.
문자열로 큰 정수 두개 주면 덧셈하는 프로그램, 예를 들면 "9999999999999999999" + "1" 의 결과를 리턴하는 프로그램을 짜보라는 문제도 제대로 못 푸는 사람이 많다. 초등학생도 하는 덧셈 알고리즘을 코드로 옮기는 것 뿐인데.
어떤 사람은 "int로 바꿔서 더하면 안되나요?" 라고 묻던데 기가 차더라. 더 쉬운 문제로 바꿔야 하나 싶다.
보자마자 확 짜증이 났는데 이유는...
- 나라는 사람 자체가 스스로 개발자라 칭하는 사람들하곤 다르게 개발도 잘 못/안하고 CP 같은 것에도 관심이 좀처럼 없다보니 그런 쪽 사람들을 보면 일단 열등감이 든다. 이건 고쳐야 할 문제긴 한데 이 주제에 대해선 담에 한번 따로 글 써봐야지.
- 저 정도 문제도 못 푸는게 말이나 되냐는 식으로 깔보는 듯한 어투. 흡사 "이지모드는 초딩까지라구~ 꺄하하" 를 보는 느낌이다.
- 나도 글에서 언급된 사람처럼 문제를 보자마자 "int로 바꿔서 풀면 되지 않나?" 라고 생각했기 때문에......
그렇긴 한데, 짜증이 나는 거랑은 별개로 내가 성장하려면 부족한 부분을 느낄 때마다 채워줘야 하는 것이다. 사실 두번째를 빼면 저 개발자가 아니라 내 문제다. (...)
그러니까 이 문제를 한번 풀어보자.
C언어로 푼다고 치면, 대충 과정은 다음과 같을 것이다.
1) 피연산자 정수들을 넣을 char 배열 두 개, 결과값을 넣을 char 배열을 준비한다.
2) for문을 만든다. 일단 각 피연산자 배열들의 맨 뒷자리에 접근해서 각 자리 숫자를 더한다. carry가 있으면 같이 더한다.
3) 결과가 10이상이면, 즉 carry가 발생하면 따로 저장해주고 나머지 값을 빼낸다.
4) 빼낸 나머지 값을 결과값 배열에 뒷자리부터 채운다.
5) 2~4를 반복하고 for문이 끝나면 결과값 배열을 출력한다.
왜 C언어냐면 자바나 파이썬같은 고급 언어로 가면 굳이 이런 걸 할 필요성이 적기 때문이다.
자바는 당장 생각나는 걸로 BigInteger 클래스를 쓰면 될테고, 파이썬은 그런 것도 필요없이 알아서 큰 수를 잘 처리해준다. 문제 풀고나서 밑에서 얘기해보자.
(저 트윗에 달린 댓글들을 보니 저 트윗 쓴 개발자가 컴파일러 쪽 전공이라던데, 그렇게 로우레벨을 다루는 분야니까 이런 문제가 나오나 싶기도 하고...)
여튼, 위 과정에 충실하게 만들어본 첫 버전의 코드이다.
최근에 코딩이라곤 파이썬밖에 안했더니 C가 너무 낯설어서 이렇게 만드는 데만 해도 시간이 좀 걸렸다...
#include <stdio.h>
int main(){
char num_a[100] = "19283746564738291828374658492190203821743674268423148347343187";
char num_b[100] = "6459673984658736478136478126129038124728952734589374823641782481";
char result[101]; // 결과값은 피연산자들보다 1자리 더 클 수 있으니까
int carry = 0;
int sum = 0;
for (int i=sizeof(num_a)-1; i>=0; i--){
sum = num_a[i] + num_b[i] + carry;
carry = sum / 10;
sum = sum % 10;
result[i+1] = sum;
}
result[0] = carry; // 제일 첫 한자리는 마지막에 남는 carry 자리
printf("%s\n", result);
return 0;
}
제대로 동작하지 않는다. 일단 딱 드는 생각은 자릿수를 맞춰줘야 할 것 같다.
게다가 sizeof(num_a) 는 100인데, 저 숫자의 자릿수가 100자리가 되진 않는다. 나머지 자리엔 알 수 없는 값이 들어갈 것이다.
for문을 저렇게 쓰려면 양쪽 숫자 다 앞에 0을 채워넣어서 (padding) 100자리로 맞춰준 다음 덧셈을 하면 될 것 같다.
0을 어떻게 채워넣을까? 찾아보니 sprintf_s() 라는 함수를 쓰면 된다 한다. 학부시절에 이런건 통 써본 기억이 없다.
sprintf_s는 이렇게 생겼다. printf가 표준 출력창에 결과값을 준다면, sprintf는 char 배열에다 결과값을 줄 수 있다.
int sprintf_s ( char * buffer, size_t size, const char * format, ... );
첫번째 인자는 결과값이 들어갈 char 배열, 두번째는 그 사이즈. 세번째부턴 printf의 그것과 같다.
뒤에 _s 붙은거 말고 그냥 sprintf도 있는데 두번째의 사이즈가 빠진 것이다. 근데 사이즈를 제대로 지정 안해주면 버퍼 오버플로우 문제가 생길 수 있어서 보안 측면에서 심각한 문제가 될 수 있기 때문에 sprintf_s를 만들었고 지금은 이걸 쓰는걸 권장한다고 한다.
세번째 인자로 들어갈 format은 어떻게 설정해줘야 할까?
printf 쓸때 정수 출력엔 %d, 문자열 출력엔 %s, 문자 하나 출력엔 %c를 썼던 건 기억난다.
기초로 돌아가서 저런 거, 그러니까 서식 지정자 쓰는 법을 다시 알아보자.
% [플래그] [폭] [.정밀도] [길이] 서식 지정 문자
대괄호는 옵션이다.
먼저 플래그라는걸 보면, 이 페이지에 따르면 아래와 같은 종류가 있다.
아무 문자나 쓴다고 다 padding 역할이 되는게 아니고, 아래와 같은 지정된 문자만 플래그가 될 수 있는 것 같다.
그 다음 '폭' 이라는게 특정한 길이로 맞춰주는 것이다.
예를 들어서 %10s라고 쓰고 "12345678" 을 출력하면 " 12345678" 이 된다. 부족한 자리는 빈 칸으로 채워진다.
근데 위에서 플래그를 '0' 으로 설정하면, 빈 칸 대신에 0을 채우게 된다.
그러니까 %010s이라고 쓰면 "0012345678" 이 되는 것이다.
이제 어떻게 해야할지 알겠다.
char num_a_[100];
char num_b_[100];
sprintf_s(num_a_, sizeof(num_a_), "%0100s", num_a);
sprintf_s(num_b_, sizeof(num_b_), "%0100s", num_b);
printf("%s\n", num_a_);
printf("%s\n", num_b_);
이러면 num_a_ 에는 num_a에 있었던 정수가 앞에 0이 잔뜩 붙은 채로 100자리 딱 맞춰서 들어갈 것이다...
...라고 생각했는데 안 뜬다. 뭐가 문제인가 싶어서 또 찾아봤다. 마이크로소프트에서 써놓은 레퍼런스 문서에 이렇게 써있다.
The other main difference between sprintf_s and sprintf is that sprintf_s takes a length parameter specifying the size of the output buffer in characters. If the buffer is too small for the formatted text, including the terminating null, then the buffer is set to an empty string by placing a null character at buffer[0], and the invalid parameter handler is invoked.
아, 끝에 널 문자가 붙는다고 한다. 그리고 널 문자 포함해서 문자열 만들었는데 버퍼가 더 작으면 empty로 바뀐다고 한다.
그러면 널 문자 자리까지 생각해서 0 붙은 정수는 99자로 맞춰줘야 할 것 같다. 아님 배열 크기를 101로 늘리던지.
%099s로 바꾸니까 잘 뜬다.
그렇지만 계산 결과는 여전히 뜨지 않는다. 세번째 줄이 계산 결과가 나와야 할 줄인데 이상한 문자 하나만 달랑 있다.
그러면 이제 for문 안으로 들어가서 뭐가 이상한지 한번 더 보자.
배열 이름은 바꿔줬고, 널 문자 고려해서 for문에 있는 i 초기값도 -2로 바꿔줬다.
for (i=sizeof(num_a)-2; i>=0; i--){
sum = num_a_[i] + num_b_[i] + carry;
carry = sum / 10;
sum = sum % 10;
result[i+1] = sum;
}
생각해보면 num_a_[i], num_b_[i] 각각은 char 배열의 원소 하나, 그러니까 char 문자 하나다.
문자끼리 덧셈을 하고 있다. 그렇지만 에러가 나진 않는다.
char에 문자 넣으면 내부적으로 어떤 값으로 처리하더라? 한번 printf("%d", sum) 을 해서 무슨 값이 나오는지 보자.
104, 122, 113, 112, 119, 117....
낯익은 숫자들이다. 맞다! 아스키 코드.
피연산자 숫자 두 개 제일 끝자리가 각각 '7', '1' 인데 각각 아스키 코드표를 보면 55, 49에 해당한다. 둘을 더하면 104다.
그러면 저 아스키 코드값을 우리가 인식하는 한자리 숫자로 바꿔줘야 저대로 계산을 할 수 있을 것 같다.
아스키 코드표에서 '0' 은 48이니까, 48을 빼주던가, 아니면... 문자를 그대로 써줘도 계산 멀쩡히 하니까. - '0' 을 써주면 되겠다.
나중에 result에 계산 결과 넣을 때는 반대로 + '0' 을 해준 다음 넣어주고.
for (i=sizeof(num_a_)-2; i>=0; i--){
sum = (num_a_[i]-'0') + (num_b_[i]-'0') + carry;
carry = sum / 10;
sum = sum % 10;
result[i+1] = sum + '0';
}
result[0] = carry + '0';
계산 결과는 잘 뜨는 것 같다. 그치만 앞에 0이 잔뜩 뜨는게 좀 거슬린다.
앞에 패딩 0은 무시하고 실제 값만 띄우고 싶다.
처음 딱 든 생각은 이거다.
int flag = 0;
for (i=0; i<sizeof(result); i++){
if (result[i] != '0'){
flag = 1;
}
if (flag == 1){
printf("%c", result[i]);
}
}
플래그 변수를 하나 만들어주고 0 말고 다른 숫자가 처음으로 등장하면 플래그를 올려주는 것이다. 그리고 그 다음부터 띄우고.
근데 이거 하나 하는데 코드가 쓸데없이 길지 않나 싶어서 좀 찾아봤더니 역시나 더 좋은 방법이 있었다.
for (i=0; result[i] == '0'; i++);
printf("%s\n", result + i);
C언어에서는 배열 이름이 곧 배열 시작 지점의 주소 (포인터) 값을 가리킨다고 예전에 배웠던 기억이 어렴풋이 난다.
그러니까 배열 이름 + i를 하면 시작 지점에서 i만큼 뒤부터 시작해서 거기부터 출력할 것이다.
다만 이렇게 하려면 int i를 for문 안이 아니라 위에 따로 선언해놔야 한다는 점 주의!
아래는 주석 포함한 전체 코드이다.
#include <stdio.h>
int main(){
char num_a[100] = "19283746564738291828374658492190203821743674268423148347343187";
char num_b[100] = "6459673984658736478136478126129038124728952734589374823641782481";
char num_a_[100];
char num_b_[100];
char result[101] = ""; // 이거 초기화 안해주면 결과 뒤에 이상한게 붙는다
int carry = 0;
int sum = 0;
int i = 0;
// sprintf_s: (대상버퍼, 사이즈, 서식 지정자, 소스버퍼)
// sprintf와의 차이점: 사이즈 지정 (기존 sprintf는 사이즈 지정이 없어 잘못하면 버퍼 오버플로우)
// %099s의 의미: %s (문자열) 로 출력하되 99자가 될때까지 0을 앞에 채운다는 뜻
// %0100s로 하면 화면에 아무것도 안뜸. sprintf의 결과는 끝에 NULL을 채우기 때문에 길이 초과
sprintf_s(num_a_, sizeof(num_a_), "%099s", num_a);
sprintf_s(num_b_, sizeof(num_b_), "%099s", num_b);
printf("%s\n", num_a);
printf("%s\n", num_b);
printf("%s\n", num_a_);
printf("%s\n", num_b_);
for (i=sizeof(num_a_)-2; i>=0; i--){
// 각 자리는 아스키 코드표의 숫자로 처리, '0' 을 빼면 문자로서의 값이 된다
// 다시 결과배열에 넣을때는 반대로 '0' 을 더해줘야 문자가 됨
sum = (num_a_[i]-'0') + (num_b_[i]-'0') + carry;
carry = sum / 10;
sum = sum % 10;
result[i+1] = sum + '0';
}
result[0] = carry + '0';
for (i=0; result[i] == '0'; i++);
printf("%s\n", result + i); // 배열 시작주소 + i칸. 여기서 i를 써먹기 위해서는 i를 위에서 선언
return 0;
}
C언어에서 이런 식으로 큰 수를 계산해야 하는 것은 C언어에서는 int 범위를 초과하는 큰 수를 다룰 수 있는 편리한 방법이 기본적으로 제공되지 않기 때문일 것이다.
(속도 때문이라는 얘기도 있던데 for문 도는건 안 느린가? 잘 모르겠다...)
자바에서는 BigInteger라는 클래스가 제공된다. 생성자에서 파라미터를 문자열로 받는 걸로 봐선 내부적으로는 위와 같은 방식으로 처리하는 걸지도 모르겠다. 위에서 계산했던 값을 자바 BigInteger 클래스로 똑같이 계산해본 코드는 다음과 같다.
import java.math.BigInteger;
public class Java_BigIntadd
{
public static void main(String[] args) {
BigInteger num_a = new BigInteger("19283746564738291828374658492190203821743674268423148347343187");
BigInteger num_b = new BigInteger("6459673984658736478136478126129038124728952734589374823641782481");
BigInteger result = num_a.add(num_b);
System.out.println(result);
}
}
파이썬은 더 간단하다. 파이썬은 동적 타입 언어라서 변수를 만들 때 int 같은 타입을 선언하지 않는다.
그냥 변수에 큰 숫자를 던져주면 알아서 내부적으로 잘 처리해준다.
(당연하지만 따옴표를 넣어서 문자열로 주면 + 연산자가 문자열 합치는 걸로 인식이 된다)
a = 19283746564738291828374658492190203821743674268423148347343187
b = 6459673984658736478136478126129038124728952734589374823641782481
c = a+b
print(c)
그렇다고 파이썬이 무조건 킹갓엠페러 마제스틱 언어라는 얘기는 아니다. 속도가 중요한 분야에선 C를 쓰게 될테니까. 그러고보니 마침 이런거 만들었으니까 한번 비교해보고 싶어졌다. C가 빠르다 빠르다 말은 자주 들었지만 얼마나 빠를까?
5만자리 숫자 두개를 더하는 프로그램을 파이썬이랑 C로 각각 돌려봤다.
파이썬은 6초가 걸렸고 C는... 굳이 시간 측정하는 코드를 집어넣을 필요도 없었다. F5를 누르자마자 바로 떴기 때문에.
C가 빠르다는 얘기만 맨날 들었지 어느 정도인지는 막연했는데 이렇게 보니까 진짜 확 체감이 된다. 왜 로우레벨 하는 사람이 이런 걸 시켰는지도 알 것 같고.
또 다른 트윗에서 봤던 내용 중에, 파이썬 라이브러리 중에 gmpy라는걸 쓰면 파이썬에서도 빠르게 큰 수를 계산할 수 있다는 얘기가 있었다.
근데 직접 해봤더니, (위 실험보다 숫자를 더 불려서 460줄 정도를 숫자로만 채우고 실험했다) 파이썬 기본 연산자를 쓰면 38초, gmpy로 했더니 35초. 별로 큰 차이가 안나더라... 내가 gmpy를 잘못 썼나?
여튼 오늘의 결론은 속도가 아주 중요한 분야에서는 역시 C를 써야겠고, C가 빠르긴 하지만 다른 고급 언어들보다 언어 자체에서 지원하는 기능이나 라이브러리가 부족한 만큼 그쪽 분야에서는 그런 기능들을 직접 구현하는 능력도 필요하겠구나... 라는 것. 내가 그쪽 분야에서 일하게 될지 어떨진 잘 모르겠지만.
그 하나의 예로 큰 수 덧셈을 살펴봤다.
찾다보니 덧셈 말고 다른 사칙연산 구현 문제도 있었고, 덧셈도 이 방법 말고 더 스마트하게 구현하는 방법이 있는 모양이더라.
생각나면 더 알아보자.