[실전 알고리즘] 0x01강 - 시간복잡도와 기초 코드 작성 요령_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I, [실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II 에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

이번 시간에 다룰 주제는 시간복잡도와 기초 코드 작성 요령입니다. 이것만 하고 나면 이제 다음 강의부터는 실제 각종 자료구조와 알고리즘을 다루기 시작할테니 이번 강의로 기초를 탄탄하게 쌓아봅시다.

 

목차는 위와 같습니다.

 

저번 시간에 했던 얘기를 기억하시나요? 코딩 테스트는 PS, CP와 같이 주어진 문제를 정해진 시간 제한과 메모리 제한 내로 해결할 수 있는 능력을 측정하는 테스트입니다. 모든 문제에는 시간 제한과 메모리 제한이 있습니다. 설령 명시되어있지 않더라도 컴퓨터 성능을 무한정 제공할 수 없기 때문에 합리적인 수준의 제한이 있을 것입니다. 보통 명시되어있지 않으면 시간 제한은 1-5초, 메모리 제한은 128-512MB 정도라고 생각하면 됩니다.

 

 

시간복잡도는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계입니다. 정의를 보면 좀 딱딱해서 안와닿는데 아래의 문제를 한번 읽어보고 답을 고민한 후 다음 슬라이드로 넘어가보세요.

 

상식적으로 생각했을 때 한 명 한 명 붙잡고 이름을 물어봐야하니 필요한 시간은 대회장에 있는 사람의 수인 $N$에 비례할 것입니다.

 

그 다음 문제는 조건이 하나 추가되었습니다. 대회장에 $N$명의 사람이 이름 순으로 서있을 때 마찬가지로 '가나다'라는 사람을 찾기 위해 얼마만큼의 시간이 필요할까요? 답을 고민하고 다음 슬라이드로 넘어갑시다.

 

술자리에서 소주병뚜껑에 있는 수를 가지고 업 다운을 해봤다면 이 답이 더 이해가 잘 갈 것입니다. 1부터 50까지의 수 중에서 왜 대부분의 사람들은 항상 1이나 50을 부르는게 아니라 처음에 25를 부를까요? 25를 부름으로 인해 가능한 경우의 수를 절반으로 줄일 수 있기 때문입니다. 마찬가지 논리로 접근하면 $N$명이 있을 때 '가나다'를 찾기 위해 필요한 시간은 $lg N$에 비례함을 알 수 있습니다. 만약 로그가 익숙하지 않다면 강의를 잠시 멈춰두고 빠르게 네이버 검색을 하고 옵시다.

 

이제 이렇게 문제를 해결하는데 걸리는 시간이 $N$에 비례한다, 혹은 $lg N$에 비례한다라고 하는 것을 점근표기법으로 나타낼 수 있습니다. 점근표기법은 시간복잡도에서 가장 큰 지수승만 남겨서 나타내는 방법으로, 낮은 지수승과 계수를 모두 무시합니다. $N^3$에 비해 $N^2$은 $N$이 커지면 커질수록 거의 아무런 영향을 주지 못하므로 그냥 없다고 퉁쳐버리는 것이지요.

 

엄밀한 정의는 수학의 극한을 이용해야 하지만 넘어갑시다. 당장 점근표기법과 시간복잡도가 잘 와닿지 않더라도 직접 예시를 통해 이 개념을 다시 설명할 일이 여러 번 있기 때문에 걱정하지 않으셔도 됩니다. 이제 다시 앞의 문제를 살펴보겠습니다. 

 

첫 번째 문제, $N$명의 사람이 일렬로 서있을 때 '가나다'를 찾는 문제는 $N$에 비례한 시간이 필요하고 이를 "시간복잡도가 $O(N)$이다" 라고 고상하게 말을 할 수 있습니다. 

 

첫 번째 문제, $N$명의 사람이 이름순으로 정렬되어 일렬로 서있을 때 '가나다'를 찾는 문제는 $lg N$에 비례한 시간이 필요하고 이를 "시간복잡도가 $O(lg N)$이다" 라고 고상하게 말을 할 수 있습니다. 

 

그 다음에 살펴볼 개념은 공간복잡도입니다. 공간복잡도는 입력의 크기와 필요한 공간의 상관관계입니다. 보통 공간복잡도로 인해 문제가 생기기 전에 이미 시간복잡도에서 문제가 생겨있는 경우가 대다수이기 때문에 공간복잡도는 크게 고민할 필요가 없습니다. 공간복잡도라는 개념 보다는 512MB에 int 변수가 대략 1.2억개 정도 들어갈 수 있다는 개념으로 접근하는 것이 더 좋습니다.

 

이제 위의 3개 함수에 대한 시간복잡도를 예측해보세요. 만약 위의 코드의 흐름을 전혀 따라갈 수 없다면 포인터와 함수 인자 부분을 복습하고 오시길 추천드립니다. 예측을 끝내고 다음 슬라이드로 넘어가봅시다.

 

첫 번째와 두 번째 함수는 배열의 모든 원소를 단 한 번씩 보며 연산을 하니 $O(N)$이고 세 번째 함수는 $(N-1)+(N-2)+...+1$번 연산을 하니 $O(N^2)$입니다.

 

컴퓨터는 1초에 대략 1-3억개의 연산을 수행할 수 있습니다. 엄밀히 말해서 비트연산 혹은 비교와 같은 단순한 연산은 좀 더 많이, 나눗셈/곱셈/대입/함수 호출 등의 복잡한 연산은 좀 더 적게 할 수 있지만 어림잡아 생각합시다.

 

그렇기에 문제에서 주어진 input의 범위를 보고 어느 정도의 시간복잡도까지 통과될 수 있는지를 잘 파악해야 합니다.

 

$N$의 크기에 따른 허용 시간복잡도는 이렇습니다. 이 기준이 절대적인건 아닙니다. 예를 들어 $N=10,000$인데도 $O(N^2)$이 통과될 수 있고, 반대로 복잡한 연산이 많은 경우 $N=1,000,000$인데도 $O(NlgN)$이 통과되지 않을 수도 있습니다. 표를 통해서 대략적인 느낌만 가져가면 됩니다.

 

이번 장에서 살펴볼 내용은 표준 입출력입니다. 코딩 테스트에서 입력과 출력은 표준 입출력을 사용합니다. 표준 입출력을 쉽게 말해 콘솔에서의 입력과 출력을 의미한다고 생각하면 됩니다. C stream을 사용하는 scanf/printf를 사용해도 되고, C++ stream을 사용하는 cin/cout을 사용해도 됩니다.

 

단 scanf/printf로는 C++ string 자료형을 처리할 수 없습니다.

 

C++ string이 C에서 char*로 문자열을 다루는 것 보다 월등히 편하기 때문에 scanf/printf를 사용하면서도 C++ string이 필요한 상황이 있을 수 있는데, c_str 메소드를 사용하면 형 변환을 쉽게 할 수 있습니다.

 

scanf와 cin 모두 공백을 포함한 문자열을 입력받을 때 굉장히 껄끄럽습니다. C stream에서는 공백을 포함한 문자열을 받기 위해 C++11 이전 버전에서만 쓸 수 있는 gets 함수를 쓰거나, fgets 혹은 scanf의 %[^\n] 형식 지정자를 사용한 후 번거로운 처리를 해줘야 합니다.

 

반면 C++ stream에서는 getline(cin, S)라는 명령 하나로 처리가 가능하기 때문에 공백이 포함된 한 줄의 문자열은 마음 편하게 C++ stream에서 입력받는 것을 추천드립니다. 그리고 char*로 굳이 변환을 하고 싶으면 이전에 설명한 것과 같이 c_str() 메소드를 사용하면 됩니다.

 

scanf/printf와는 다르게 cin/cout에서는 입출력으로 인한 시간초과를 방지하기 위해 반드시 ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 합니다. 두 명령을 실행시키지 않으면 입/출력의 양이 많을 때 시간초과가 발생할 수 있습니다.

 

첫 번째로 ios::sync_with_stdio(0)은 C++ stream과 C stream의 sync를 끄는 명령입니다. 기본적으로는 C++ stream과 C stream 간의 출력 순서를 유지할 수 있도록 sync를 유지하고 있으나, cout만 사용할 경우 sync를 유지할 필요가 없으므로 시간을 절약하기 위해 sync를 꺼야 합니다. 반대로 말하면, 해당 명령을 실행한 이후에는 반드시 printf를 쓰지 말고 cout만 사용해야 합니다. 아래의 예시의 오른쪽을 보면 sync를 끄고 난 이후 순서가 뒤죽박죽이 됨을 알 수 있습니다.

 

cin.tie(0)은 cin과 cout이 번갈아 나올 때 마다 flush를 하지 않도록 하는 명령입니다. 채점 환경에서는 input buffer와 output buffer가 분리되어 있기 때문에 flush를 해줄 필요가 없습니다. 비슷한 이유로 줄바꿈을 endl로 하는 경우가 있는데, endl은 줄을 바꾸고(즉 '\n'을 출력하고) flush를 하라는 명령이므로 endl을 사용하면 불필요한 flush 명령이 지속적으로 발생해 시간초과가 발생할 수 있습니다.

 

지금부터 할 내용은 앞으로 강의를 들을 때 기초 지식으로 가지고 있으면 좋겠다 싶을 내용입니다. 쉽다는 의미의 기초가 아니라 반드시 필요하다는 의미의 기초이기 때문에 내용이 어렵다고 낙담하시지 마시고 열심히 해봅시다. char 자료형이 1 byte란 얘기를 아마 C언어 공부를 하면서 들어본 적 있을 것입니다. 혹시 그게 무엇을 나타내는지도 명확하게 이해를 하고 있나요?

 

1 byte는 8 bit로, char 자료형의 값을 8개의 0 혹은 1이 들어가는 칸을 이용해 표현한다는 얘기입니다. 이 8 bit에 2진수 표기로 값이 들어가는데, unsigned char에서는 최상위 비트가 $2^7$이지만 char에서는 $-2^7$임에 유의해야 합니다. 이렇게 두는 까닭은 전공생이라면 논리회로 과목에서 배웠을 것입니다. 이 부분이 잘 이해가 안가면 2's complement라는 개념을 찾아보셔도 되고, 굳이 이해를 하지 않고 넘어가셔도 괜찮습니다.

 

unsigned char와 char로 수를 표현한 예시입니다. 예시를 통해 생각해보면 char 자료형은 10000000일 때 최솟값인 -128을 가지고 01111111일 때 최댓값인 127을 가짐을 알 수 있습니다. unsigned char는 00000000일 때 최솟값인 0을 가지고 11111111일 때 최댓값인 255를 가집니다.

 

short, int, long long 자료형 또한 char와 마찬가지 방식으로 표현할 수 있는 범위를 계산할 수 있습니다. 정수를 표현할 때 주로 int와 long long을 사용하는데, int가 long long보다 연산 속도와 메모리 모두 우수하지만 80번째 피보나치 수를 구하는 문제와 같이 int 자료형이 표현할 수 있는 범위를 넘어서는 수를 저장해야 하면 반드시 long long 자료형을 사용해야 합니다.

 

이제 Integer overflow를 알아보겠습니다. 아마 한 번쯤은 이런 현상을 겪여봤을 것입니다. 위에서 설명한 것과 같이 int가 최대 21억 정도까지 표현 가능하므로 40억이 담기는건 불가능하겠지만 왜 뜬금없이 음수가 나올까요? 이 부분을 명확하게 이해하지 않고 각 자료형의 범위 안에서만 써야겠다고 생각하고 넘어가도 무방하지만, 원리를 알고 나면 코드의 오류를 조금 더 빠르게 찾을 수 있고 또 그다지 어려운 내용이 아니므로 짚고 넘어가겠습니다.

 

컴퓨터는 멍청합니다. 그래서 Integer overflow가 일어납니다. 관찰을 위해 두 char 자료형의 수를 더해봅시다. 9와 21을 더하면 30이 되고, 오른쪽의 수를 무시하고 두 이진수의 덧셈이라고 생각해도 결과는 동일합니다.

 

음수의 덧셈 또한 잘 동작합니다. -119와 5를 더하면 -114가 되고, 이진수의 덧셈에서도 마찬가지 결과를 냅니다.

 

그런데 127에 1을 더하면 어떻게 될까요?

 

컴퓨터는 멍청해서 그냥 시킨대로 계산을 합니다. 받아올림이 계속 생겨 이진수로 10000000, 즉 -128이 되어버렸네요. 이것이 Integer overflow의 전부입니다. 컴퓨터는 명령받은 대로 이진수 상의 계산을 했을 뿐입니다. 다만 그 결과가 올바르지 않게 된 것 뿐이죠.

 

Integer overflow는 생각보다 빈번하게 일어나고, 또 찾기 힘든 버그입니다. 이 3가지 함수 중에 Integer overflow가 발생할 수 있는 함수들이 무엇인지, 어느 부분에서 발생하는지를 찾아보세요.

 

정답은 이렇습니다. func1, func3 모두 제가 저질러봤던 실수입니다. 찾기 쉬웠나요?

 

그러면 이 버그는 어떻게 해결할 수 있을까요? 고민을 해봅시다.

 

func1은 s의 자료형을 다른 것으로 바꾸면 되겠네요. 그리고 func3은 a를 long long으로 두거나 10을 long long으로 강제 형변환을 시키면 됩니다. 어차피 mod로 나눈 나머지는 확실히 int 범위 안에 들어오니까요. 이 때 만약 10과 int a는 그대로 냅두고 mod만 long long으로 바꾸면 어떻게 될까요? 직접 고민하고, 돌려서 결과를 확인해보세요.

 

이렇게 이론적으로 Integer overflow를 알게 됐지만 분명 문제를 풀 때 실수를 여러 번 하게 될 겁니다. 그렇지만 맞왜틀로 인해 마음 고생을 심하게 하다 보면 그 뒤에는 실수를 하지 않을 것입니다. 아예 하지 않게 되는건 아니고 빈도가 좀 줄긴 하겠네요. 좋은 코딩 습관은 아니지만, 아예 int를 무조건 쓰지 않고 다 long long으로 대체하는 것도 하나의 방법입니다.

 

만약 unsigned long long의 범위를 넘는 매우 큰 수를 저장해야 하면 string을 활용해야 합니다. 그 수로 연산을 해야하는 문제는 코딩테스트에서 나오지 않는게 정상이지만 그런 문제가 나오면 Python으로 풉시다. 굳이 C++로 unsigned long long의 범위를 넘는 수의 연산을 해야 한다면 GCC의 __int128 자료형을 이용하거나 직접 큰 수의 연산 클래스를 만들어야 합니다. 이 부분은 넘어가겠습니다.

 

정수 자료형의 개념이 어려우셨나요? 실수 자료형의 개념은 더 어렵습니다ㅠㅠ 실수도 마찬가지로 원리를 알고 있어야 정확하게 쓸 수 있습니다. float은 4 byte, double은 8 byte인데 이 0과 1이 들어갈 수 있는 32칸 혹은 64칸을 가지고 어떻게 실수를 표현하는지 알아봅시다.

 

우선 2진수를 실수로 확장한다는 개념을 이해해야 합니다. 3.75를 11.11(2) 로 나타내는 것을 말이죠. 그리고 2진수에도 무한소수가 나타납니다.

 

그 다음에 알아야하는 부분은 2진수에서의 과학적 표기법입니다.

 

과학적 표기법까지 이해가 갔으면 이제 다 됐습니다. 실수를 나타낼 때 32, 혹은 64칸은 sign, exponent, fraction field로 나누어집니다. sign field는 해당 수가 음수인지 양수인지 저장하는 필드이고, exponent 필드는 과학적 표기법에서의 지수승을 저장하는 필드이고, fraction 필드는 유효숫자 부분을 저장하는 필드입니다. 예를 들어 설명을 해보겠습니다.

 

-6.75을 float에 저장하는 예는 위와 같습니다. 음수이기 때문에 sign은 1이고, exponent field에는 음의 지수승까지 처리하기 위해 원래의 지수승인 2에 127을 더한 129를 8 bit 공간에 기록하고, fraction field에는 11011을 적습니다. exponent field에 더해지는 127을 bias라고 부르고 이 bias 덕분에 $2^{-127}$에서부터 $2^$까지 적을 수 있게 됩니다. double도 똑같은 방식으로 저장을 하되 bias가 1023입니다.

 

만약 이해가 잘 가지 않는다면 IEEE 754 format으로 검색을 하면 정보를 많이 찾을 수 있습니다. 도저히 이해가 가지 않는다면 이해를 나중으로 미루시되 지금부터 설명할 성질들은 꼭 기억을 하셔야 합니다. 그리고 double이 float보다 메모리를 2배 더 차지하지만 더 정확하므로 모든 실수 관련 문제에 double을 쓰면 됩니다.

 

첫 번째 성질입니다. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없습니다. fraction field는 유한한데 2진수 기준 무한소수를 저장하려고 하면 앞의 일부분만 잘라서 저장을 하기 때문에 오차는 필연적으로 발생합니다.

 

fraction field의 길이로부터 float은 유효숫자가 6자리, double은 유효숫자가 15자리임을 알 수 있습니다. 만약 문제에 절대/상대 오차를 허용한다는 단서가 있으면 실수 연산을 해도 되지만 그렇지 않다면 모든 연산을 정수에서 해결할 수 있도록 해야합니다. 그렇지 않을 경우 오차로 인해 오답이 발생할 수 있습니다.

 

두 번째로 double에 long long 범위의 정수를 함부로 담으면 안됩니다. double의 유효숫자는 15자리이기 때문에 double은 $10^+1$과 $10^$을 구분할 수 없습니다. int 범위의 정수는 double에 담아도 되지만 long long 범위의 정수를 담으면 오차가 발생합니다.

 

마지막으로 실수를 비교할 때는 등호를 사용하면 안됩니다. 0.1+0.1+0.1과 0.3이 같지 않은게 대표적인 예시입니다. 그렇기에 둘의 차이가 극도로 작은 값, 대략 $10^{-12}$ 이하면 동일하다고 처리를 하는 것이 안전합니다.

 

이외에도 실수의 뺄셈은 상대오차가 보장되지 않는다, 여러 개의 수를 더할 때 작은 수끼리 먼저 더하고 이후 큰 수를 더해야 한다는 주의사항 등이 있지만 너무 지엽적인 내용이라 넘어가겠습니다. 더 알아보고 싶으면 zlzmsrhak님이 작성하신 글(링크)를 참고하시면 됩니다.

 

 

변수의 지역성은 굳이 설명을 하지 않겠습니다. 실무에서는 전역변수가 메모리를 계속 점유하고 있기 때문에 사용하지 않는 것을 권장하지만 코딩테스트에서는 마음껏 써서 굳이 함수 인자로 넘기고 받는 것에 타이핑을 낭비할 필요가 없습니다. 지역 변수는 0으로 초기화되지 않지만 전역 변수는 0으로 초기화됩니다.

 

코딩테스트에서의 채점에 대해 알아보겠습니다. 코딩테스트에서는 공개된 예제 말고도 비공개된 다양한 예제들로 주어진 코드를 채점합니다. 하나의 테스트 케이스에서라도 틀리면 오답으로 처리되는게 일반적이나 맞은 TC의 갯수만큼 부분점수를 주는 경우도 있습니다.

 

코딩테스트에 따라 채점 결과를 매번 알려주는 경우도 있고 그렇지 않은 경우도 있습니다. 삼성 역량테스트는 후자에 속합니다. 이제 저희가 주로 코딩테스트 훈련을 진행할 BOJ에서의 채점 결과에 대해 알려드리겠습니다.

 

이 정보들은 BOJ 홈페이지의 채점 도움말에서도 확인할 수 있습니다. 천천히 읽어보세요. 

 

초보 분들의 질문을 보면 런타임 에러가 났는데 이유를 모르겠다는 질문이 많습니다. 런타임 에러는 말 그대로 실행중(run time)에 프로그램이 비정상적으로 종료되었다는 의미이고 주로 발생하는 이유는 main 함수에 return 1과 같이 다른 값을 반환하도록 둔 경우, 0으로 나눈 경우, 배열에서 잘못된 인덱스 값에 접근한 경우 등이 있습니다.

 

컴파일 에러는 로컬의 환경과 채점 서버의 환경이 다를 때 겪을 수 있는 에러로, 당황하지 말고 '컴파일 에러'라고 적힌 곳을 클릭해 에러 메시지를 확인하면 됩니다.

 

아직 알고리즘을 많이 접하지 않아서 정말 간단한 코드 작성 요령만 짚고 넘어가겠습니다. 코딩테스트는 남과 협업을 하는 프로젝트가 아니기에, 코드를 일목요연하고 가독성있게 짜느라 시험 시간을 깎아먹으면 안됩니다. 내가 알아볼 수 있는 선에서 최대한 짧고 군더더기 없는 코드를 만들어내는 것이 중요합니다. 저는 이런 템플릿을 쓰고 있긴 한데, 객관적으로 좋은 코딩 습관은 아닌 것 같습니다.

 

그렇지만 어느 정도 틀을 만들어두는게 도움이 되긴 합니다. 그리고 헤더는 bits/stdc++.h를 쓰도록 합시다. 해당 헤더 안에 모든 표준 라이브러리가 포함되어 있기 때문에 header를 include하느라 타이핑을 낭비할 필요가 없습니다. 단 MSVC에는 해당 헤더가 존재하지 않는데 직접 경로에 헤더파일을 추가해놓으면 됩니다.

 

마지막으로 공부 방법에 대한 개인적인 의견을 전달해드리겠습니다. 각자 생각이 다를 수 있는 부분이니 맹신하지 말되 참고만 하시면 됩니다. 초반에는 문제를 맞았다고 하더라도 if / else문을 한가득 채워 굉장히 비효율적인 코드를 남발하기 쉽습니다. 그렇기 때문에 다른 사람의 코드를 문제를 푼 뒤 다른 사람의 코드를 보며 다른 사람은 어떻게 접근했는지 이해해보고 좋은 코딩 스킬들을 습득하는 것도 좋은 습관입니다. 단, 너무 길이가 짧은 코드는 도리어 도움이 되지 않으니 적당한 길이의 코드를 보세요. 대충 1페이지 중반쯤부터 보면 됩니다.

 

아직 이론을 많이 모르고 구현력을 늘리는 것이 시급한 초보 단계에서는 한 문제를 너무 오랜 시간 고민하는 것이 별로라고 생각합니다. 학창시절에 공부를 할 때야 모든 문제가 교과과정 안의 내용으로 풀 수 있음이 보장되니 "풀이를 보면 실력이 늘지 않는다, 직접 고민해서 풀어봐야한다" 는 말이 일리가 있지만 알고리즘 공부에서는 지금 이 문제가 반드시 현재까지 내가 알고 있는 지식으로 풀 수 있다는 보장이 없기 때문입니다. 그러므로 길어야 30분-1시간 정도 고민한 후에도 전혀 실마리가 보이지 않으면 빠르게 풀이를 참고하는 것이 좋다고 생각합니다. 풀이 방법은 알겠는데 도저히 코드를 어떻게 짜야할지를 모르겠을 때에도 마찬가지로 풀이를 보거나 질문을 통해 방향을 잡는 것이 좋습니다.

 

만약 풀이를 봤는데 너무 생소한 개념이거나, 아는 개념을 이용했지만 도저히 이해가 가지 않으면 너무 고통받지 말고 과감히 다음으로 미룬 채 다른 문제로 넘어가는 것도 괜찮습니다. 어차피 풀어야 할 문제는 산더미니까요.

 

드디어 길고 긴 이번 강의가 끝났습니다. 이번 강의를 통해 시간/공간 복잡도와 다양한 컴퓨터과학의 기초 지식, 입출력 요령등을 익히게 되었습니다. 이전에 접해본 적 없다면 어려운 내용들이 많으니 복습 열심히 하시고 다음 강의에서 만나요! BOJ 그룹에 문제집을 올려두었으니 온라인저지가 익숙하지 않으면 풀어보세요.