[바킹독의 실전 알고리즘] 0x00 ~ 0x01강

0x00강 - 오리엔테이션

 

- 코딩 테스트에 대한 정보 -

코드의 채점을 진행하는 입력 데이터를 테스트 케이스, TC라고 부른다.

테스트 케이스는 적어도 30개에서 50개는 있어야 한다.

코딩 테스트는 코드가 모든 테스트 케이스를 통과했을 때만 문제를 맞혔다고 처리한다. 

 

- 환경 세팅 -

Visual Studio 2017/2019는 기본적으로 msvc 컴파일러를 사용하지만 거의 모든 채점 서버는 gcc 컴파일러를 사용한다.

msvc에서는 못쓰는데 gcc에서는 할 수 있는 기능이 일부 있다.

예를 들어, msvc에서는 배열을 선언할 때 그 크기로 변수를 이용할 수 없는데, gcc에서는 가능하다(VLA, 가변 길이 배열).

강의 내에서는 msvc, gcc에서 모두 잘 실행되는 코드로 설명한다.

bits 폴더 안에 있는 stdc++.h에는 미리 수많은 헤더들을 다 include 해두어서 헤더들을 하나하나 include 해야 하는 번거로움을 덜어준다. 이 헤더는 gcc에는 있지만 msvc에는 없어서 Visual Studio 2017/2019를 사용한다면 따로 폴더에 넣어줘야 한다.

C++ #include <bits/stdc++.h> 헤더 사용하기 (tistory.com)

하지만 삼성전자 SW 역량 테스트 시험장에서는 해당 헤더를 못 쓰게 제한하니 algorithm, stack, vector등과 같은 대표적인 헤더들은 기억해놔야 한다.

---

0x01강 - 기초 코드 작성 요령 1

 

- 시간 복잡도 -

컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있다.

만약 문제에서 시간제한을 1초로 줬다면, 3-5억 번의 연산 안에서 결과를 내야 한다.

 

예제)

배열 arr를 돌면서 5의 약수의 개수를 반환하는 함수이다.

연산 횟수를 자세하게 따지면 5n+3번의 연산이 수행된다는 것을 알 수 있다.

하지만 이렇게 구체적인 식으로 나타내지 않고 n에 비례한다라는 사실만 알면 된다.

이렇게 입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관관계를 시간 복잡도(Time Complexity)라고 한다.

 

빅오 표기법은 연산 횟수를 계산한 식에서 최고차항만 남기는 표기 방식이다.

보통 시간 복잡도를 표현할 때 빅오 표기법을 사용한다.

예를 들어 5n+3이라는 식에서 빅오 표기법을 적용하면 상수항 3과 계수 5를 모두 떼고 O(n)으로 나타낼 수 있다.

 

시간 복잡도를 그래프로 나타낸 것이다.

그래프를 보면 n이 커짐에 따라 시간 복잡도의 차이가 매우 커지는 것을 알 수 있다.

O(1)을 상수 시간, O(logN)을 로그 시간, O(n)을 선형 시간이라고 부르고, 또 O(logN)부터 O(n^2)과 같이 logN이나 n의 거듭제곱끼리의 곱으로 시간 복잡도가 나타내진 것을 다항 시간이라고 부른다.

O(2^n)은 지수 시간이라고 부르는데, n이 25 이하 정도로 굉장히 작은 게 아니라면 O(n^2)의 시간 복잡도를 갖는 풀이는 시간제한을 통과하기가 어렵다.

O(n!)은 지수 시간보다 더 가파른 그래프를 나타내는데, n이 11 이하가 아니라면 마찬가지로 시간제한을 통과하기 어렵다.

 

문제에서 주어지는 시간제한은 대부분 1에서 5초이다.

입력의 범위를 보고 문제에서 요구하는 시간 복잡도를 계산해볼 수 있다.

예를 들어 주어진 배열을 크기 순으로 정렬하는 문제일 때 n이 1000 이하라면 O(n^2)의 시간 복잡도로도 해결할 수 있지만, n이 100만이라면 O(nlogN)의 시간 복잡도 내로 정렬을 완료해야 한다.

이런 식으로 n의 크기에 따른 허용 시간 복잡도를 표로 나타내면 다음과 같다.

따라서 문제를 보고 떠오른 풀이를 무턱대고 짜는 게 아니라, 풀이가 이 문제를 제한 시간 내에 통과할 수 있는지, 즉 알고리즘의 시간 복잡도가 올바른지 생각해봐야 한다.

 

1부터 N까지 돌면서 3의 배수이거나 5의 배수에 해당하는지 확인하기 때문에 n에 비례, 시간 복잡도 = O(n)

 

(N^2-N)/2의 시간 복잡도를 갖지만 빅오 표기법으로 나타내면 O(N^2)

 

N이 제곱수인지 확인하기 위해 1부터 루트 N까지 반복, 시간 복잡도=O(루트 N)

 

2^1, 2^1, 2^2,... 순으로 2를 곱하며 N보다 크지 않은 2의 거듭 제곱수 중에 최댓값을 찾는다.

곱해지는 수가 N보다 커지면 반복문이 멈추기 때문에 시간 복잡도 = O(logN)

 

- 공간 복잡도 -

공간 복잡도는 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계이다.

예를 들어 크기 N짜리 2차원 배열이 필요하면 O(N^2)이고, 배열이 필요 없으면 O(1)이다.

코딩 테스트에서 공간 복잡도 때문에 문제를 틀리는 경우는 많지 않다.

하지만 메모리 제한이 512MB일 때 int 변수를 대략 1.2억 개 선언할 수 있다는 것을 기억하면 좋다.

int 변수 1개의 크기가 4byte라는 것을 이용해 계산할 수 있다.

만약 int 변수를 5억 개 선언해야 하는 풀이라면 메모리 제한을 만족시키지 못하기 때문에 다른 풀이를 떠올려야 한다.

 

- 정수 자료형 -

정수 자료형에는 char, short, int, long long이 있다.

char 자료형은 1byte, 즉 8bit이므로 2진수(0, 1) 8개가 모여 표현된다.

signed char은 unsigned char과 달리 가장 왼쪽에 있는 1bit는 부호 비트(sign bit)로 사용된다.

따라서 signed char에서는 가장 왼쪽 비트를 -2^7으로, unsigned char에서는 2^7으로 계산한다.

그림에서 signed char 00001001은 2^0 + 2^3 = 9의 값을 갖는다.

 

그림에서와 같이 똑같은 1000011이지만 unsigned char에서는 131, char에서는 -125의 값을 갖는다.

똑같이 8bit이지만 두 자료형은 범위도 다르다.

unsigned char은 0 ~ 255, char은 -128~127의 범위를 갖는다.

 

다른 자료형 short, int, long long의 크기와 범위에서의 최댓값은 위와 같다.

short는 대부분 사용하지 않고 정수를 표현할 때 int와 long long이 많이 쓰인다.

int가 long long보다 연산 속도와 메모리 측면에서 모두 우수하지만, 80번째 피보나치 수를 구하는 것과 같이 int 자료형의 범위를 넘는 숫자를 사용하게 된다면 long long을 사용해야 한다.

 

int가 21억 이상의 값을 저장할 수 없다는 건 알겠는데, 왜 음의 값을 결과로 내는 걸까?

이런 현상을 Integer Overflow라고 한다.

 

이를 설명하려면 이진수끼리의 덧셈을 알아야 한다.

다음과 같이 int 범위의 최댓값인 01111111에 00000001을 더하게 되면 10000000이라는 값을 나타내게 되고,

컴퓨터는 이를 -128로 읽는다.

컴퓨터는 자료형의 범위와 상관없이 시키는 대로 연산을 하기 때문에 자료형의 범위를 고려하지 않으면 이런 Integer Overflow가 발생하게 된다.

 

Integer Overflow 발생 여부를 확인하는 연습을 하기 위해 다음 예제들을 보자.

func1의 경우에는 s가 127이 된 이후 1이 한 번 더 더해졌을 때 128이 아닌 -128의 값을 갖게 되므로 의도한 대로 작동하지 않는다. 이 경우 자료형을 char에서 int로 바꾸면 해결된다.

func3의 경우 a가 10^9일 때 10이 한 번 더 곱해지는 순간 int의 최대 범위를 넘어서게 된다.

이 경우 자료형을 int에서 long long으로 바꾸면 된다.

 

그럴 경우는 희박하지만 만약 문제에서 unsigned long long의 범위를 넘어서는 수를 저장할 것을 요구한다면 string으로 저장해야 한다. 그리고 그 수를 가지고 계산해야 한다면 c++ 보다 python으로 구현하는 것을 추천한다.

 

- 실수 자료형 -

실수 자료형에는 float과 double이 있다.

float과 double은 각각 4byte, 8byte 크기를 갖고 있다.

 

실수를 2진수로 나타낼 땐 0.5, 0.25, 0.125등의 합으로 나타낸다.

따라서 3.75는 2^1 + 2^0 + 2^-1 + 2^-2이기 때문에 2진수로 나타내면 11.11이 된다.

 

한편, 10진수의 무한소수와 같이 2진수에서도 무한소수가 나타난다.

예를 들어 1/3은 2^-2 + 2^-4 + 2^-4 +...로 끝없이 이어지기 때문에 0.01010101... 이 된다.

 

10진수에서 편의를 위해 3561.234를 3.561234 * 10^3으로 나타내는 것처럼 2진수에서도

11101.001를 1.1101001 * 2^4로 나타낼 수 있다. (2진수의 과학적 표기법)

 

실수를 나타낼 때 칸은 sign, exponent, fraction으로 나누어진다.

sign field는 값이 음수인지 양수인지를 저장하는 필드이고, exponent field는 과학적 표기법에서의 지수를 저장하는 필드이고, fraction field는 유효숫자 부분을 저장하는 필드이다.

각 필드의 크기는 float에서 1, 8, 23 byte, 그리고 double에서 1, 11, 52 byte이다.

 

-6.75를 2진수로 나타내 보자.

6.75 = 2^2 + 2^1 + 2^-1 + 2^-2이기 때문에 2진수로 나타내면 -110.11이고,

과학적 표기법을 적용하면 -1.1011 * 2^2이다.

음수이기 때문에 sign field에는 1이 들어간다.

exponent field에는 2의 값을 나타내는 00000010 대신 2에 127을 더한 10000010가 들어간다.

127을 더하는 이유는 그래야 음의 지수 승도 넣을 수 있기 때문이다.

마지막으로 fraction field에는 1.1011에서 1을 뺀 10110000... 이 적힌다.

필드의 첫 번째 자리가 2^-1로 시작해 2^-2, 2^-3.. 을 나타내기 때문이다.

이렇게 실수를 저장하는 방식을 IEEE-754 format이라고 한다.

 

- 꼭 기억해야 하는 실수의 성질 -

1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수밖에 없다.

 

사진에 나와있는 코드를 보면 0.1 + 0.1 + 0.1이 0.3과 다르다는 결과를 출력하고 있다.

float과 double은 모두 유한한 필드를 갖고 있는데 2진수 기준으로 무한소수를 저장하려고 하면 float은 앞에서 23bit, double은 앞에서 52bit까지만 잘라야 하기 때문이다.

2진수 기준 무한소수들은 애초에 오차가 있는 채로 저장이 되며, 오차가 있는 값들을 계속 더하면 더 큰 오차가 발생한다.

 

fraction field를 보고 각 자료형이 어디까지 정확하게 표현할 수 있는지 보면, float은 유효숫자 6자리이고 double은 유효숫자 15자리이다. 

이 말은 곧 float은 상대 오차 10^-6까지 안전하고, double은 상대 오차가 10^-15까지 안전하다는 소리이다.

원래 값이 1이라고 할 때 double은 1-10^-15에서 1+10^-15 사이의 값을 갖는다는 게 보장된다는 얘기와 같다.

 

우리는 오차가 생기는 것 자체는 막을 수 없지만, 오차의 범위는 알 수 있다.

상대 오차의 허용 범위에서 알 수 있듯이 두 자료형 간의 차이가 굉장히 크기 때문에 실수 자료형이 필요하면 꼭 float보다 double을 써야 한다.

float이 메모리를 적게 쓴다는 장점이 있긴 하지만 메모리 문제 때문에 double대신 float을 써야 하는 경우는 거의 없다.

또 실수 자료형이 필요한 문제에서는 보통 오차 범위를 제공하는데, 이런 표현이 없다면 대부분 정수 자료형으로 푸는 문제일 것이다.

 

2. double에 long long 범위의 정수를 함부로 담으면 안 된다.

double은 유효숫자가 15자리인데 long long은 최대 19자리여서 10^18 + 1과 10^18을 구분할 수 없고 같은 값이 저장된다.

즉 double에 long long 범위의 정수를 넣을 경우 오차가 같이 저장될 수 있다.

int는 최대 21억의 값을 갖기 때문에 double에 넣어도 오차가 생기지 않는다.

 

3. 실수를 비교할 때는 등호를 사용하면 안 된다.

실수의 오차 때문에 두 실수를 비교할 때는 두 값의 차이가 아주 작은 값(10^-12, 1e-12) 보다 작으면 동일하다고 처리하는 것이 안전하다.

 

 

🐶 바킹독의 실전 알고리즘 강의를 듣고 정리한 내용을 기록한 글입니다