[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

 

안녕하세요, 바킹독입니다. 이번 단원에서는 기초 코드 작성 요령을 익혀보려고 합니다. 목차를 보셨으면 알겠지만 기초 코드 작성 요령이 두 강으로 나눠져있는데 앞으로 코드를 잘 짜기 위해서 알고있어야 하는 지식이 굉장히 많아서 그렇습니다. 

 

미리 예고를 드리자면 기초가 Elementary보다는 Primary에 더 가까워서, 그러니까 쉬워서 기초가 아니라 꼭 필요해서 기초인거라 난이도가 꽤 있습니다. 앞으로 배울 한 5개 단원 중에서 이번 단원이 제일 어려울 것입니다. 힘들 수도 있지만 어려워도 포기마시고 잘 해봅시다.

 

일단 기초 코드 작성 요령 두 파트 중에서 첫 파트에서는 이론적인 얘기를 많이 할 것입니다. 이 중에서 이미 알고 계신 내용이 있다면 알아서 건너뛰셔도 됩니다.

 

첫 번째로 다룰 주제는 시간복잡도와 공간복잡도입니다. 이건 이전 단원에서 소개했던 문제인데, 당시에는 시간 제한과 메모리 제한에 대해 정확하게 짚고 넘어가지 않았습니다. 이번에 제대로 짚고 넘어가겠습니다.

 

일단 시간 제한부터 생각해보면 시간 제한이 1초라고 되어 있는데, 컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있습니다. 단, 연산이 비트 AND, OR, 비교, 덧셈과 같은 단순한 연산인지,  아니면 나눗셈, 곱셈, 대입, 함수 호출과 같은 복잡한 연산인지에 따라 횟수에 좀 차이가 날 수 있어서 3-5억이라는 것은 어림을 잡은 값인건 주의하셔야 합니다.

 이 문제에서 정답을 받은 코드를 다시 생각해보면 이 코드는 연산을 몇 번 할지 생각해봅시다. 일단 05번째 줄에서 두 변수를 입력받을 때 , 06번째 줄에서 두 수를 더하고 출력할 때 연산이 필요하게 되니 대충 3, 4번의 연산이 필요할 것입니다.  그러니까 1초 내로는 충분히 프로그램이 모든 명령을 수행한 후에 종료되고, 엄밀히 말하면 진짜 0.000001초도 안 걸릴 것입니다.

그러면 이제 시간 제한이 우리에게 어떤걸 알려주는지 조금 감이 올 것입니다. 예를 들어 시간 제한이 1초라고 하면, 이건 "당신의 프로그램은 3-5억 번의 연산 안에 답을 내고 종료되어야 한다"라는걸 알려주는 것입니다.

 

그런데 3-5억 번의 연산이 필요하다고만 하면 솔직히 좀 난해할 것 같습니다. 일단 주어진 코드를 봅시다. 코드 내의 함수가 뭘 하는 함수인지 알겠나요?

 

해당 함수는 arr[0]부터 arr[n-1]까지 돌면서 5로 나눈 나머지가 0이면, 즉 5의 배수이면 cnt 변수의 값을 1 증가시킵니다. 그러니까 n은 arr 배열의 크기이고, arr[0]부터 arr[n-1]안의 5의 배수의 갯수를 반환하는 함수입니다.

 

이제 이 함수가 몇 번의 연산을 수행하는지 같이 한 번 보겠습니다. 

 

일단 02번째 줄에서 cnt 변수를 선언하고 0을 넣는 과정에서 1번, 그리고 03번째 줄에서 i에 초기 값으로 0을 대입할 때 1번, 그 다음에는 n번에 걸쳐 반복되는 일인데 03번째 줄을 계속 보면 i가 n보다 작은지 확인하고 작을 경우 1 증가시키니 연산 2번, 04번째 줄에서 5로 나눈 나머지를 계산하고 그게 0과 일치하는지 확인할 때 연산 2번, 5의 배수라고 치면 cnt를 1 증가시켜야 하니 연산 1번, 이후 마지막으로 cnt를 반환할 때 연산 1번이 추가로 필요합니다. 

 

이렇게 뜯어서 보면 이 함수는 5n + 3번의 연산이 필요하다는걸 알 수 있습니다. n이 100만 정도였으면 대충 500만 번의 연산이 필요하니 1초 안에 충분히 돌거고 n이 10억이었으면 대충 50억 번의 연산이 필요하니 1초 안에 다 돌 수가 없습니다.

 

그런데 저희가 무슨 인간 컴파일러도 아니고 코드를 매 실행 단위로 이렇게 하나하나 뜯어보는건 너무 심각한 노가다입니다. 그래서 이렇게 고생스럽게 뜯어보지 말고 상수는 떼고 적당히 n번의 연산이 필요하다, 좀 더 고상하게 말하면 n에 비례한다고 퉁쳐서 얘기를 합니다.

 

이 사실을 어떻게 빠르게 캐치할 수 있냐면 결국 이 코드는 n개의 수를 훑어보며 5로 나눈 나머지를 계산해보게 됩니다. 그러면 03, 04, 05번째 줄의 for문에서 n번에 걸쳐 5로 나눈 나머지를 확인하고 0과 일치하면 cnt를 증가시키는 행위를 하게 되니 굳이 아까처럼 하나하나 뜯어보며 5n + 3이라는 것을 알아내지 않더라도 n에 비례하겠거니 하고 충분히 생각할 수 있습니다.

 

나름대로 친절하게 설명하려고 했는데 시간복잡도가 처음 접하면 난해할 내용이어서 지금 뭐 5n+3이니 n에 비례하니 하는 소리가 잘 이해가 안 갈 수도 있을 것 같습니다. 너무 고통받지 마시고 다음 슬라이드에는 코드를 배제한 설명을 할거여서 그걸 보면 되니까 지금 잘 이해가 안갔더라도 괜찮습니다.

 

비록 지금 실전 알고리즘 강의를 듣고 있지만 잠시 자기 자신에게 최면을 걸어서 재미있는 수학 퍼즐을 푼다고 생각해보겠습니다.

 

문제를 다 읽으셨나요? 얼마만큼의 시간이 필요할까요? 답을 생각해보겠습니다.

 

크게 어렵지는 않은 문제같은데 어떤가요? 맨 앞으로 나간 후에 사자후를 질러서 한 번에 찾는다 이런 넌센스 답을 제외하면 방법은 굉장히 뻔합니다. 그냥 맨 앞부터 한 명 한 명 붙잡고 '가나다'씨가 맞는지 물어보면 됩니다. 운이 좋으면 물어보자마자 바로 찾을테니 1초이고, 최악의 경우는 '가나다'씨가 맨 뒤에 있을 경우 모든 사람에게 다 물어봐야 하니 N초이고, 평균적으로는 대충 절반쯤 물어보면 '가나다'씨를 찾을 수 있을테니 N/2초입니다.

 

그리고 이렇게 걸리는 시간은 N에 비례한다는걸 알 수 있습니다. 사람이 100명이면 대충 50초 정도 걸릴거고, 사람이 10배 늘어나면 걸리는 시간도 10배 늘어나서 500초 정도 걸리게 될 것입니다.

 

이번에는 두 번째 문제입니다. 앞의 것이랑 거의 비슷한데 사람들이 이름 순으로 서있다는 조건 1개가 추가됐습니다. 이건 얼마만큼의 시간이 필요할까요?

 

아주 조금 낯설 수도 있지만 술자리에서 업다운 게임을 떠올리면 도움이 될 것 같습니다. 마치 1에서 50 사이의 수에서 처음 하는 사람이 25를 부르는 것과 같이 N명의 사람들 중에서 가운데 있는 사람의 이름을 물었을 때 그 이름이 '바킹독'이어서 '가나다'보다 뒤에 있어야 하는 이름이면 '가나다'는 앞쪽 그룹에 있음을 알 수 있고 '가고일'과 같이 '가나다'보다 앞에 있어야 하는 이름이면 '가나다'는 뒤쪽 그룹에 있음을 알 수가 있으니까 어찌됐든 후보군을 절반으로 줄일 수 있습니다. 

 

최선의 경우에는 맨 처음 물어본 사람이 바로 '가나다'인 경우이고 이렇게 되면 1초 만에 '가나다'를 찾아낼 수 있습니다. 최악의 경우에는 한 명이 남을 때 까지 절반으로 계속 쪼개지는 상황이니, 그러니까 원래 100명이었다 치면 앞에서 설명한 것 처럼 가운데 있는 사람의 이름을 물어봐서 50명을 남기고, 50명에서 또 가운데 있는 사람의 이름을 물어봐서 25명을 남기고 이렇게 25명, 12명, 6명, 3명, 1명까지 도달하면 '가나다'를 찾을 수 있습니다.

 

사람이 16명이면 4번, 32명이면 5번, 64명이면 6번 뭐 이런식으로 시간이 걸리니 lg N에 비례한다는게 이해가 갈 것입니다. 만약 로그를 배운지 오래되서 lg N이란게 무슨 소리인지 모르겠다 하시는 분이 있으면 일단 이 강의를 들을 때 고등 수학에 나오는 정도의 로그는 필요가 없고 어차피 다 밑이 2인 로그만 나오기 때문에 로그는 해당 수가 2의 몇 거듭제곱인지를 의미하고 lg 2 = 1, lg 4 = 2, lg 8 = 3, lg 16 = 4, lg 32 = 5 뭐 이정도만 이해하고 가셔도 당장 이해하는데는 큰 문제가 없습니다. 그래도 길게 봤을 때 개발자로 일하면서 고등학교 수학 정도는 알고 있는게 좋을 것 같으니 다음에 꼭 따로 공부를 하도록 합시다.

 

그리고 최선의 경우 1초, 최악의 경우 lg N초인건 알겠는데 왜 평균적으로 lg N인지는 이해가 안갈 수도 있을 것 같습니다. 사실 엄밀하게는 수학적으로 기댓값을 계산해보면 (1-1/N)lg N인데 1/N은 N이 커지면 커질수록 사실상 0에 가까운 값이니 그냥 lg N초로 작성했습니다. 이런 엄밀함을 좋아하시는 분이면 기댓값이라는 단어를 보자마자 계산식이 머릿속에 떠올랐을 것 같습니다. 만약 깐깐하고 엄밀하게 확인을 하는 것에 관심이 없다면 지금 평균적으로 lg N 어쩌구 하면서 하는 논의는 전혀 안 중요한 내용이니까 그냥 최악의 경우 lg N이고 평균적으로도 lg N초가 걸리나보다 하고 받아들이면서 넘어가면 됩니다.

 

이 두 문제를 통해 저희는 시간복잡도라는 개념을 자연스럽게 익힐 수 있게 됐습니다.

 

시간복잡도의 정의는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미합니다. 정의가 좀 딱딱해서 와닿지 않을 수 있는데, 첫 번째 문제에서 사람이 N명일 때 최악의 경우 N초가 걸렸고, 두 번째 문제에서는 lg N초가 걸렸던 것을 기억하나요? 이 N초, lg N초가 각 문제의 시간복잡도입니다.

 

그리고 빅오표기법이라는 개념도 묶여서 나오는데 짚고 넘어가겠습니다. 빅오표기법은 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법을 의미합니다. 엄밀하게는 빅오표기법을 수학의 입실론 델타라는 것을 이용해 정의하고 또 빅오 말고도 스몰오, 빅/스몰 세타, 빅/스몰 오메가라는 개념이 더 있는데 코딩테스트에는 필요하지 않기 때문에 전부 건너뛰고 빅오표기법에만 집중하겠습니다.

 

원래는 수학적으로 엄밀한 정의를 통해 표현되는 용어를 말로 풀어쓰니 좀 난해해지는 경향이 있는데, 우리가 앞에서 "걸리는 시간이 N에 비례한다", "lg N에 비례한다"라고 표현한게 바로 빅오표기법에서 하는 일입니다.

 

일단 5N+3을 보면 누가 봐도 N이 커지면 커질수록 3보다는 5N이 훨씬 크겠죠. 그래서 3을 버리고 5N만 냅두는데, 5N에서 상수 5도 떼고 O(N)으로 나타냅니다.

 

2N+10lgN에서도 N이 커지면 커질수록 10lgN보다는 2N이 훨씬 클테니  2N만 냅두고, 상수 2를 떼서 O(N)으로 나타냅니다.

 

N²+2N+4에서는 N²이 2N과 4보다 훨씬 크니 O(N²)이 됩니다.

 

NlgN과 N을 비교하면 아무래도 그냥 N보다는 lgN이 곱해진 NlgN이 더 클 것입니다. 그래서 NlgN + 30N + 10은 O(NlgN)이 됩니다.

 

마지막으로 값이 그냥 상수일 때에는 O(1)이라고 부릅니다.

 

보통 시간복잡도를 표기할 때 빅오표기법의 형태로 나타냅니다. 예를 들어 맨 처음 코드로 제시했던 주어진 배열에서 5의 배수인 원소의 갯수를 찾는 문제는 시간복잡도가 O(N)이고, 사람들이 마음대로 서있는 대회장에서 '가나다'를 찾는 문제도 시간복잡도가 O(N)이고, 사람들이 이름순으로 서있는 대회장에서 '가나다'를 찾는 문제는 시간복잡도가 O(lg N)이다 뭐 이런식입니다.

 

이제 여러 대표적인 시간복잡도를 그래프로 나타낸 것을 한번 확인해보겠습니다. 그래프만 봐도 N이 점점 커짐에 따라 시간복잡도의 차이가 수행 시간에 아주 큰 영향을 준다는 것을 알 수 있습니다.

 

상수 시간인 O(1)이 가장 좋고, 그 다음으로는 O(lg N)이고, 이후로 O(N), O(NlgN), O(N²) 등이 있습니다. O(lg N)은 로그 시간, O(N)은 선형 시간으로 부르고 또 O(lg N)부터 O(N²)까지와 같이 lg N 혹은 N의 거듭제곱끼리의 곱으로 시간복잡도가 나타내어지면 이를 다항 시간이라고 합니다.

 

O(2^N)은 지수 시간이고, N이 25 이하 정도로 굉장히 작은게 아니면 O(2^N)이 필요한 풀이는 시간 제한을 통과하기 힘들 것입니다. O(N!)에서 N!은 1부터 N까지 곱한 값으로, N 팩토리얼이라고도 부릅니다. 예를 들어 3!은 1 × 2 × 3 = 6입니다.

팩토리얼은 지수 시간보다 훨씬 더 가파르게 올라갑니다. 당장 12!만 해도 거의 5억이라 O(N!)이 필요한 알고리즘도 지수 시간과 비슷하게 N이 11 이하 정도로 굉장히 작은게 아니면 시간 제한을 통과하기 힘듭니다.

 

문제에서 주어지는 시간 제한은 대부분 1초에서 5초 사이 정도니까 입력의 범위를 보고 문제에서 요구하는 시간복잡도가 어느 정도인지를 알 수 있습니다.

 

예를 들어 주어진 배열을 크기 순으로 정렬하는 문제를 생각해보면 이 문제는 O(NlgN)으로도 해결할 수 있고 O(N²)의 방법도 있습니다. N이 1000 이하라면 둘 중 어느 것을 쓰더라도 눈 깜빡할 사이에 정렬이 완료되지만 N이 100만이라면 O(NlgN)은 1초 내로 정렬이 완료되는데 O(N²)은 정렬이 완료될 때 까지 거의 1시간 가까이 걸릴 것입니다.

 

이런 식으로 N의 크기에 따른 허용 시간복잡도를 표로 나타낸 게 본문에 있는 표입니다. 물론 이 기준이 절대적인건 아닙니다. N이 10,000인데도 O(N²)이 통과될 수 있고, 반대로 복잡한 연산이 많은 경우 N이 1,000,000인데도 O(NlgN)이 통과되지 않을 수도 있습니다. 그냥 표를 통해 대략적인 느낌만 가져가시면 됩니다.

 

그러면 이제 우리가 문제를 풀 때 해야 할 일을 하나 더 알게 됐는데 주어진 문제를 보고 풀이를 떠올린 후에 무턱대고 바로 그걸 짜는게 아니라 내 풀이가 이 문제를 제한 시간 내로 통과할 수 있는지, 즉 내 알고리즘의 시간복잡도가 올바른지를 꼭 생각해봐야 합니다.

 

예를 들어 N이 500인데 O(2^N) 풀이를 생각했다면 그 풀이는 절대 시간 제한 내로 답을 낼 수 없기 때문에 잘못된 풀이입니다. 시간복잡도 개념을 생각하지 않은채 무턱대고 구현을 해버리면 한 1시간 걸려서 실컷 다 짜고 제출을 한 후에야 시간초과가 난다는 것을 깨닫고 절망에 빠지게 됩니다.

 

 

(앞으로 나올 4개의 함수는 여기서 테스트해볼 수 있습니다.)

 

그러면 내 풀이의 시간복잡도를 어떻게 알 수 있느냐라고 했을 때 이게 어떻게 보면 쉽고, 어떻게 보면 어렵습니다. 뭐 대충 1부터 N까지의 수를 다 돌아야하면 O(N), 우리가 구구단을 구현하던 것 처럼 이중 for문으로 돌면 O(N²) 이런식으로 느낌은 잡을 수도 있지만, 확실히 초보 단계에서 풀이나 코드의 시간복잡도를 알아내는게 꽤 어려웠다는 얘기를 많이 들어서 여러 예시들을 통해 같이 익혀보겠습니다.

 

일단 문제를 한 번 봅시다. N 이하의 수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수를 한번 구현해봅시다. 예를 들어 N이 16이면 3+5+6+9+10+12+15=60을 반환하면 됩니다. N이 34567, 27639일 때의 값도 드렸으니 다 짠 후에 확인보면 되겠습니다.

 

지금 한 번 짜보는 시간을 가져보겠습니다. 시간복잡도도 생각해봅시다.

 

다 짜셨나요? 저는 그냥 1부터 N까지 돌면서 3의 배수이거나 5의 배수인 것을 더하는 방식으로 구현했습니다. 제 코드를 한 번 확인해봅시다.

 

구현이 크게 어렵지는 않을 것 같습니다. 그러면 이 코드의 시간복잡도는 얼마일까요? 시간복잡도도 크게 어렵지 않게 알아낼 수 있을 것 같은데, for문에서 i가 1부터 N까지 돌며 3으로 나누어지는지, 5로 나누어지는지 확인합니다. 그러니까 시간복잡도는 O(N)입니다.

 

참고로 이 문제를 O(N)이 아닌 O(1)에 해결할 수 있는 방법이 있습니다. 본인이 수학을 좀 잘한다고 생각하시면 어떻게 O(1)에 구할 수 있을지 한 번 고민해보는 것도 좋을 것 같습니다.

그 다음 문제는 합이 100인 서로 다른 위치의 두 원소가 존재하는지 판단하는 문제입니다. 이것도 구현한 후에 제 코드를 같이 확인하겠습니다. 시간복잡도도 생각해봅시다.

 

 

 

제일 무난한 방법은 이중 for문으로 모든 두 개의 쌍에 대해 합이 100인지 확인하는 방법일 것입니다. 이 방식의 시간복잡도는 얼마일까요?

i가 0일 때 N-1개의 수에 대해 합을 100과 비교하고, i가 1일 때 N-2개의 수에 대해 합을 100과 비교하고, 이런식으로 쭉쭉쭉 가다가 i가 N-2일 때 1개의 수에 대해 합을 100과 비교하니 다 더하면 연산은 (N²-N)/2번 일어나고, 이걸 빅오표기법으로 나타내기 위해 상수 떼고 더 낮은 항을 없애고나면 O(N²)인걸 알 수 있습니다.

 

혹시 나는 O(N) 짜리 풀이를 짰는데 이 사람은 왜이리 비효율적으로 짰지? 라고 생각하시는 분 있으신가요? 있으시다면 아주 칭찬합니다. 사실 이 문제는 딱 봤을 때 O(N²) 풀이가 먼저 떠오르지만 O(N)짜리 풀이가 존재합니다. 하지만 지금 짚고 넘어가지는 않고 0x03강에서 배열에 대해 배울 때 알려드리겠습니다. 지금은 여기 슬라이드에 있는 코드만 이해하시고 또 이 코드가 O(N²)라는 것만 이해해도 충분합니다.

 

이 문제는 N이 제곱수인지 아닌지 판단하는 문제입니다. 조금 까다로울 수 있지만 화이팅입니다. 

 

앞의 두개와 달리 이 문제는 어떻게 해야할지 감이 안 올 수도 있을 것 같습니다. 너무 상처받지 마시고 배워가면 되니 제 코드를 한 번 확인해봅시다.

 

어떻게 구현을 했냐면, i가 1부터 올라가면서 1의 제곱이 N과 일치하는지 확인하고 2의 제곱이 N과 일치하는지 확인하고 계속 가다가 N과 일치하는 순간이 있으면 N이 제곱수이니 1을 반환하고, 일치하는 순간이 없이 i의 제곱이 N보다 커져 for문을 탈출하게 되었다면 제곱수가 아니니 0을 반환하면 됩니다.

 

이 방식의 시간복잡도는 얼마일까요? 생각해보면 i가 1부터 2, 3 이렇게 가다가 최대 √N까지 올라갈테니 시간복잡도는 O(√N)이 됩니다. 이렇게 시간복잡도에 루트가 들어갈 수도 있습니다.

 

참고로 문제 3을 O(lg N)에 해결할 수 있는 방법이 있습니다. 당장은 방법을 떠올리기 힘들겠지만 강의를 완강한 후에는 어떻게 O(lg N)에 해결가능한지 알 수 있을테니 기억해뒀다가 완강한 후 문제를 다시 확인해보세요.

 

지금까지 한 내용들이 이해가 잘 가나요? 내용이 따라갈만하면 좋겠습니다.

 

이제 마지막 문제입니다. 마지막 문제는 N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 문제입니다. 예를 들어 N이 5라고 할 때 5이하의 수 중에서 2의 거듭제곱수는 1, 2, 4가 있는데 셋 중에서 4가 가장 크니 4를 반환하게 됩니다.

 

이 문제도 조금 어려울 수 있지만 한번 짜보겠습니다. 다 짠 후에는 코드를 확인해봅시다.

 

코드에서 val은 2의 거듭제곱이 저장되는 변수입니다. 맨 처음에는 1로 시작해서 2, 4, 8, ··· 이렇게 커지다가 val을 2배했을 때 N보다 커지게 되는 순간에 while문을 탈출해서 val을 반환하면 문제에서 요구하는 답을 구할 수 있게 됩니다.

 

이 방식의 시간복잡도는 얼마일까요? N이 2^k 이상 2^k+1 미만이라고 할 때 while문 안에서 val은 최대 k번만 2배로 커집니다. 그러고나면 val은 2^k가 되고, 이후 2*val <= N이 거짓이 되기 때문입니다. 그러니까 N이 2^k 이상 2^k+1 미만이라고 할 때 시간복잡도가 O(k)이고 로그의 정의에 입각해서 생각할 때 k는 lgN이니 결국 시간복잡도는 O(lgN)이 됩니다.

이렇게 다양한 문제들에 대한 시간복잡도를 알아봤습니다. 일단 이정도만 익혀둬도 앞으로 강의 중에 시간복잡도를 언급했을 때 큰 어려움없이 넘어갈 수 있을 것입니다.

 

시간복잡도를 이해했다면 공간복잡도도 큰 어려움 없이 이해할 수 있습니다. 공간복잡도는 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계를 의미합니다.

 

예를 들어 크기 N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)이 됩니다. 그런데 코딩테스트에서 대부분의 경우 공간복잡도의 문제보다는 시간복잡도 때문에 문제를 많이 틀리게 됩니다. 그래서 공간복잡도는 크게 신경을 안써도 됩니다.

 

대신 문제를 풀 때 어떤 것 하나를 기억해두는게 좋냐면 메모리 제한이 512MB일 때 int 변수를 대략 1.2억개 정도 선언할 수 있다는 것을 기억해두시는게 좋습니다. 이건 int 1개가 4바이트라는 것을 이용해 계산할 수 있습니다.

 

이걸 기억해두면 만약 떠올린 풀이가 크기가 5억인 배열을 필요로 할 때 해당 풀이는 주어진 메모리 제한을 만족하지 못하므로 틀린 풀이라는 것을 빠르게 깨닫고 다른 풀이를 고민할 수 있습니다. 실컷 다 짠 후에야 알아차리면 너무 억울합니다.

 

드디어 아주 길고 길었던 시간, 공간복잡도 챕터가 끝났습니다. 기지개 한번 펴시고 정수 자료형에 대한 설명을 이어서 해보겠습니다.

C언어를 배울 때 char 자료형은 1 byte이다 라는 표현을 들어본 적이 있을 것입니다. 혹시 그 의미에 대해서도 명확하게 알고 있나요? 1 byte는 8 bit이니까 char 자료형의 값은 8개의 0 혹은 1이 들어가는 칸을 이용해 표현된다는 의미입니다. 이 8 bit에 2진수 표기로 값이 들어가게 됩니다.

 

오른쪽부터 2⁰, 2¹, 2², ··· 2⁶을 나타내는 칸인데, unsigned char에서는 제일 왼쪽이 자연스럽게 2⁷이지만 char에서는 제일 왼쪽이 독특하게 -2⁷입니다. 왜 이렇게 두는지는 전공생이시라면 논리회로 과목에서 배웠을 것입니다. 이 부분이 잘 이해가 안가면 2's complement라는 개념을 찾아보셔도 되고, 굳이 이해를 하지 않고 넘어가셔도 상관은 없습니다.

 

지금 이건 unsigned char와 char로 수를 표현하는 예시입니다. 10000011을 unsigned char로 읽으면 131이고 char로 읽으면 -125가 되는 것을 확인할 수 있습니다. 

 

unsigned char로 표현할 수 있는 수의 최솟값과 최댓값을 고민해보면 최솟값은 00000000일 때 0일거고, 최댓값은 11111111일 때 255입니다.

char에 대해서도 똑같이 표현할 수 있는 최솟값과 최댓값이 얼마일지 생각해보면 최솟값은 10000000일 때 -128일거고, 최댓값은 01111111일 때 127입니다.

 

정수 자료형에는 char 말고도 short, int, long long 자료형이 있습니다. 각각은 2 byte, 4 byte, 8 byte입니다.

 

char의 크기를 계산한 것과 비슷하게 각각이 표현할 수 있는 수의 최댓값을 확인하면 각각 32767, 대략 2.1×10⁹(21억), 9.2×10¹⁸까지 표현할 수 있습니다.

 

저와 동년배들은 저 int의 최댓값인 21억이 살짝 익숙할텐데 요즘은 패치가 됐지만 옛날엔 메이플 최대 메소가 2³¹-1인 2147483647이었습니다.

 

아무튼 short는 딱히 쓸 일이 없고 정수를 표현할 때 주로 int나 long long을 쓰는데 int가 long long보다 연산 속도와 메모리 모두 우수하지만 80번째 피보나치 수를 구하는 문제와 같이 int 자료형이 표현할 수 있는 범위를 넘어서는 수를 저장해야 하면 반드시 long long 자료형을 사용해야 합니다.

 

그 다음으로는 Integer Overflow를 알아볼 것입니다. 아마 다들 코딩을 하다가 한 번 쯤은 이런 현상을 겪어보셨을 것입니다. int가 대충 21억까지 표시할 수 있다고 했으니 20억에 2를 곱한 40억을 저장할 수 없는건 알겠는데 -294967296은 대체 어디서 나온 값인지 너무 뜬금없습니다.

 

이런 현상이 바로 Integer Overflow입니다. 왜 Integer Overflow가 생기는지 정확하게 이해를 하지 않고 그냥 각 자료형의 범위 안에서만 써야겠다 하고 넘어가도 상관은 없지만, 원리를 알고 나면 코드의 오류를 조금 더 빠르게 찾을 수 있고 엄청 어렵지도 않아서 이유를 이해하고 넘어가겠습니다.

 

딱 한 줄로 요약하면 컴퓨터는 그냥 시킨대로 계산을 하기 때문입니다. 관찰을 위해 두 char 자료형의 수를 더해보겠습니다.

 

9 + 21 = 30인건 당연하고, 그냥 이진수의 덧셈으로 생각을 해도 1001과 10101을 더하면 11110이 된다는걸 알 수 있습니다.

 

음수가 섞인 덧셈도 크게 고민할 것 없이 그냥 이진수의 덧셈으로 해결할 수 있습니다. -119를 char에 나타내면 10001001인데, -119+5는 -114이고 이진수의 덧셈으로 생각해도 10001001+101는 10001110이라 연산이 아주 정확하게 잘 됩니다.

 

그런데 127에 1을 더하면 어떻게 될까요? 컴퓨터는 아무 고민도 하지 않고 시킨대로 계산을 합니다. 01111111에 1을 더하면 10000000이 됩니다.

 

그리고 제일 앞의 칸은 -2⁷의 칸이니 10000000은 -128이 됐습니다. 이렇게 char에서 127+1 = -128이 되는 기적을 같이 목도했습니다. 이게 Integer Overflow의 전부입니다. 컴퓨터는 명령받은 대로 이진수 계산을 했을 뿐인데 다만 그 결과가 옳지 않게 된 것입니다.

 

Integer Overflow를 막는 방법은 아주 쉽습니다. 각 자료형의 범위에 맞는 값을 가지게끔 연산을 시키면 됩니다. 하지만 실제 코드를 짜다보면 Integer Overflow는 아주 빈번하게 일어나고, 또 찾기도 정말 힘듭니다.

 

제가 3가지 함수를 보여드릴테니 Integer Overflow가 발생할 수 있는 함수가 무엇인지, 어느 부분에서 발생하는지를 찾아보겠습니다.3개의 함수 중에서 Integer Overflow로 인해 의도한대로 동작하지 않는 함수는 func1과 func3입니다. 우선 func1의 경우에는 s가 127이 된 후에 1이 더해질 때 127에서 1이 더해지면 -128이기 때문에 의도한대로 동작하지 않고 무한루프에 빠집니다. 이를 해결하려면 s의 자료형을 char에서 int로 바꿔야 합니다.

 

func3에서는 a가 10⁹일 때 여기서 10이 곱해지는 순간 int의 최대 범위를 넘어서서 Integer Overflow가 발생합니다. 이걸 막으려면 a의 자료형을 long long으로 바꾸거나, 07번 줄에서 10 대신 10ll 혹은 (long long)10으로 강제 형변환을 시키면 해결할 수 있습니다.

 

앞으로도 머리로는 Integer Overflow를 익혔지만 분명 실제로 문제를 풀 때 이 실수를 여러 번 저지르게 될 것입니다. 왜 이걸 확신할 수 있냐면 당장 저도 잊을만하면 한 번씩 저지르기 때문입니다. 그래도 이 실수로 시간을 엄청 버리고 나면 그 다음엔 실수를 덜하게 될 것입니다.

 

좋은 코딩 습관은 아니긴 한데, 이런거 저런거 다 신경쓰기 싫다 하면 아예 int를 쓰지 않고 전부 long long을 쓰는 것도 하나의 방법이긴 합니다. 만약 문제에서 unsigned long long 범위를 넘어서는 수를 저장할 것을 요구한다면 string을 활용해서 저장해야 합니다. 그리고 그 수로 연산을 해야 하는 문제는 코딩테스트에 안나오는게 정상이긴 한데, 만에 하나 나왔다 치면 그냥 Python을 쓰는게 C++로 꾸역꾸역 구현하는 것 보다 훨씬 편합니다.

 

정수 자료형의 개념이 어려우셨나요? 실수 자료형은 더 어렵습니다ㅠㅠ 꺼이꺼이..

 

실수도 정수처럼 원리를 알고 있어야 정확하게 쓸 수 있어서 원리를 좀 알아보겠습니다. 일단 실수 자료형으로는 float과 double이 있습니다. float은 4 byte이고 double은 8 byte입니다. 정수 자료형과 비슷하게 생각해보면 0 혹은 1이 들어가는 32칸 혹은 64칸으로 실수를 나타낸다는 건데 대체 어떻게 실수를 표현하는걸까요?

 

컴퓨터가 실수를 어떻게 저장하는지 알려면 우선 2진수를 실수로 확장하는 것을 이해해야 합니다.

 

일단 3을 2진수로 나타내려고 한다면 3은 2¹ + 2⁰이니까 2진수로 11이 됩니다. 이걸 실수로 확장해서 3.75를 2진수로 나타내고 싶습니다. 어떻게 할까요?

 

정수를 2진수로 바꿀 때 1, 2, 4, 8 등등의 합으로 나타낸 것 처럼 실수를 2진수로 바꿀 땐 0.5, 0.25, 0.125 등등의 합으로 나타내면 됩니다. 3.75는 2+1+0.5+0.25이고 이건 곧 2¹+2⁰+2^-1+2^-2니까 3.75는 2진수로 11.11이 됩니다. 이와 같이 2의 음수 거듭제곱을 이용해 임의의 실수를 2진수로 나타낼 수 있습니다.

 

한편, 10진수의 무한소수와 같이 2진수에서도 무한소수가 나타납니다. 예를 들어 1/3은 2^-2+2^-4+2^-6+… 이런 식으로 끝없이 이어지기 때문에 2진수로 나타내면 0.010101… 이 됩니다.

 

그 다음으로는 2진수에서의 과학적 표기법을 이해해야 합니다. 저희가 10진수에서 편의를 위해 3561.234 = 3.561234 × 10³ 으로 나타내는 것 처럼 2진수에서도 11101.001₍₂₎ = 1.1101001₍₂₎  × 2⁴ 으로 나타낼 수 있습니다.

 

드디어 실수를 32칸 혹은 64칸에 저장하기 위한 모든 준비가 끝났습니다. 실수를 나타낼 때 칸은 sign, exponent, fraction field로 나누어집니다. sign field는 해당 수가 음수인지 양수인지 저장하는 필드이고, exponent field는 과학적 표기법에서의 지수를 저장하는 필드이고, fraction field는 유효숫자 부분을 저장하는 필드입니다. 각 필드의 크기가 float은 1, 8, 23 bit이고 double은 1, 11, 52 bit입니다.

 

-6.75로 예를 들어 설명드리면, 일단 -6.75는 -1.1011₍₂₎ × 2²입니다. -6.75의 부호가 음수여서 sign은 1이고 또 2의 2승이 곱해지니 지수는 2인데, float에서는 여기에 127을 더한 129를 exponent field에 기록합니다. 참고로 129는 2진수로 10000001이니까 10000001이 기록됩니다. 왜 127을 더하냐면 이렇게 해줘야 음수 지수승도 exponent field 안에 잘 넣을 수 있기 때문입니다. double에서는 exponent field가 11칸이기 때문에 1023을 더합니다.

 

마지막으로 fraction field에는 현재 1.1011인데 여기서 맨 앞의 1은 뺀 1011이 적힙니다. 맨 왼쪽부터 2^-1, 2^-2자리인 셈이라 필드에 1011000…00이 적히게 됩니다. 그러니까 제일 왼쪽부터 채우는거죠.

 

이렇게 실수를 저장하는 방식을 IEEE-754 format이라고 부르니까 지금 제 설명이 잘 이해가 가지 않는다면 추가적으로 검색을 해보셔도 좋습니다. 도저히 이해가 안가면 지금 당장 이해를 못해도 상관없지만, 지금부터 설명할 실수의 성질들은 꼭 기억을 하셔야 합니다.

 

첫 번째로, 실수의 저장과 연산 과정에서 반드시 오차가 발생할 수 밖에 없습니다. 아주 대표적인 예가 이 코드인데, 충격적이게도 0.1+0.1+0.1이 0.3과 다르다고 합니다.

 

이게 왜 그런거냐면 유효숫자가 들어가는 fraction field가 유한하기 때문에 2진수 기준으로 무한소수인걸 저장하려고 할 때에는 어쩔 수 없이 float은 앞 23 bit, double은 앞 52 bit까지만 잘라서 저장할 수 밖에 없습니다.

 

0.1은 이진수로 나타내면 무한소수여서 애초에 오차가 있는 채로 저장이 됐고 그걸 3번 더하다보니 오차가 더 커져서 위의 코드처럼 말도 안되는 일이 벌어졌습니다.

 

fraction field를 가지고 각 자료형이 어디까지 정확하게 표현할 수 있는지 보면 float은 유효숫자가 6자리이고 double은 유효숫자가 15자리입니다. 이 말은 곧 float은 상대 오차 10^-6까지 안전하고 double은 10^-15까지 안전하다는 소리입니다.

 

상대 오차가 10^-15까지 안전하다는 표현을 정확하게 이해할 필요가 있는데, 원래 참값이 1이라고 할 때, 1-10^-15 에서 1+10^-15 사이의 값을 가진다는게 보장된다는 의미입니다. 즉 오차가 생기는 것 자체는 막을 수가 없지만 오차가 어느 정도인지는 알 수 있습니다.

 

상대 오차의 허용 범위에서 볼 수 있듯 두 자료형끼리 차이가 굉장히 크기 때문에 실수 자료형이 필요하면 꼭 float 대신 double을 써야합니다. float이 메모리를 적게 쓴다는 장점이 있으니까 메모리가 정말 소중하면 필요할 수도 있긴 하지만 적어도 저는 지금까지 알고리즘 문제를 풀면서 double 대신 float을 써야 하는 상황을 경험해본 적이 없습니다.

 

또 실수 자료형은 필연적으로 오차가 있으니까 실수 자료형이 필요한 문제면 보통 문제에서 절대/상대 오차를 허용한다는 단서를 줍니다. 그런데 만약 이런 표현이 없다면 열에 아홉은 실수를 안쓰고 모든 연산을 정수에서 해결할 수 있는 문제일 것입니다.

 

두 번째로, double에 long long 범위의 정수를 함부로 담으면 안됩니다. double은 유효숫자가 15자리인데 long long은 최대 19자리니까 10¹⁸+1과 10¹⁸을 구분할 수가 없고 그냥 같은 값이 저장됩니다. 즉, double에 long long 범위의 정수를 담을 경우 오차가 섞인 값이 저장될 수 있습니다.

 

다만 int는 최대 21억이기 때문에 double에 담아도 오차가 생기지 않습니다.

 

마지막으로 실수를 비교할 때는 등호를 사용하면 안됩니다. 이건 0.1+0.1+0.1과 0.3이 일치하지 않았던걸로 이미 보셨을텐데, 오차 때문에 두 실수가 같은지 알고 싶을 때에는 둘의 차이가 아주 작은 값, 대략 10^-12 이하면 동일하다고 처리를 하는게 안전합니다.

 

5번째 줄의 1e-12가 처음 보는 표현일 수 있을 것 같은데 저게 바로 10^-12입니다. 비슷하게 만약 10⁹ 가 필요하면 1000000000이라고 써도 되긴 한데 아무래도 이렇게 쓰면 0 갯수를 세는 것도 힘들고 하니까 대신에 1e9라고 써도 됩니다.

 

거듭 말하지만 sign field니 exponent field니 하는 IEEE-754 소수 표현법은 많이 헷갈리면 이해를 미뤄도 됩니다. 하지만 지금 이 실수 자료형의 3가지 성질은 꼭 알고 가셔야 나중에 "컴퓨터가 미쳤어!"라고 하며 샷건을 칠 일이 없어집니다.

 

긴 시간 진짜 고생 많으셨습니다. 도입부에도 말했지만 이번 내용이 앞으로 한 5강 정도에서 배울 내용 중에 가장 어려운 내용입니다.

 

이해가 잘 안가는 부분이 있다면 너무 낙담하지 마시고 조금 쉬다가 다시 보시면 아까는 이해가 안가던게 잘 이해가 갈 수도 있습니다.

 

내용이 빡셌지만 이론이 탄탄하게 있어야 앞으로 배울 때 수월해서 일부러 이렇게 배치를 한거니 이해해주시고, 다음 단원부터 다시 힘내봅시다.

 

다음 강의는 훨씬 쉽습니다. 그럼 복습하시고 다음 단원에서 만나요~~