[코딩 테스트 합격자 되기 C++ 스터디] STEP 1. 시간 복잡도

인프런 강의 링크: https://inf.run/DuvN7

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

1주차

스터디 일자: (1주차: 2024. 07. 07(일) ~ 2024. 07. 13(토))

시작에 앞서

평소 Java로 코딩 테스트 준비를 하며 많은 문제를 풀었다. 그러나 코딩 테스트의 문제를 해결할 때 항상 새롭고 어렵게 느껴져 이번엔 C++을 통해 도전해 볼까 생각했다. 강의와 함께 스터디를 진행한다는 알람을 받고, 주변 사람들과 공유하며 참여하게 되었다. C++ 언어 기초부터 알고리즘에 대해 다시 되짚어보는 시간을 가져보려 한다.

1. 시간 복잡도

1.1 알고리즘이란?

알고리즘은 다음의 조건을 만족해야 한다

- 정밀성: 변하지 않는 명확한 작업 단계를 가져야 한다

- 유일성: 각 단계마다 명확한 다음 단계를 가져야 한다

- 타당성: 구현할 수 있고, 실용적이어야 한다 << 알고리즘의 성능

- 입력: 정의된 입력을 받아들일 수 있어야 한다

- 출력: 답으로 출력을 내보낼 수 있어야 한다

- 유한성: 특정 수의 작업 이후에 정지해야 한다

- 일반성: 정의된 입력들에 일반적으로 적용할 수 있어야 한다

 

내가 생각한 알고리즘은

문제를 입력했을 때 최적의 값을 출력하는 로직이었다

 

컴퓨터의 입장에서는

해당 문제를 입력할 때 최적 값을 출력하도록 만들어진 코드 정도가 되지 않을까?

Input이 주어지면 거기에 맞는 최적의 Output을 제공할 수 있어야 한다

또한 타당성 측면에서 최적의 시간과 최적의 메모리 사용을 통해 자원을 절약할 수 있어야 진짜 알고리즘일 듯하다

알고리즘은 해당 작업이 끝나면 종료되어야 하며, 엣지케이스 코너케이스 등에서도 모두 작동해야 한다

 

이러한 문제를 해결하는 절차들의 모음과 종료까지가 알고리즘이라 볼 수 있다

 

그렇다면 알고리즘에서 우리는 다음과 같은 부분을 고려해야 할 것이다

1. 시간복잡도(종료 - 답을 찾을 때 - 까지 걸리는 시간 정도...?)

2. 메모리 사용

3. 엣지 / 코너 케이스

4. 기본 중의 기본은 예시 케이스에 대한 답안 출력

 

1.2 알고리즘 성능 측정법 및 시간 복잡도 개념

성능은 어떻게 측정해야 할까?

알고리즘은 입력과 출력으로 이루어져 있으며, 그 사이에는 우리가 구현한 코드가 존재한다

우리 코드가 동작하고 완료되는데 걸리는 총시간이 곧 알고리즘의 성능이 될 것이다

시간 측정 방식에는 절대 시간 측정과 연산 횟수 측정이 있다

 

1. 절대 시간 측정

앞서 말한 것처럼 입력부터 종료까지의 시간을 측정하는 방식이다

그러나 만일 컴퓨터의 하드웨어적 문제나 운영체제 등의 문제로 시간이 더 소요된다면?

환경의 제약으로 억울하게 알고리즘이 느려지는 경우가 생길 수 있다

알고리즘의 성능은 환경의 제약을 받지 않아야 한다

 

백준 온라인 저지, 프로그래머스 등은 우리의 로컬이 아닌, 해당 사이트가 가진 성능을 토대로 우리의 알고리즘을 평가한다

아마 환경의 제약 문제를 해결하기 위한 방법이지 않을까? 생각해 본다

 

2. 연산 횟수 측정

PC 성능이 아닌, 코드에 따른 시간 측정 방식이다

환경과 무관하게 코드 자체의 연산 횟수를 기준으로 한다

그러나 입력 값이 달라진다면? 그 기준이 애매해진다

 

그래서 우리는 코딩 테스트에 최악의 조건을 기준으로 삼는다

예를 들어 최대 N이 10,000인 경우에 1초 내 연산이 필요한 경우는 N^2까지 연산이 가능하다

(보통 우리 컴퓨터는 100_000_000(1억) 연산을 처리하는데 1초가 소요된다고 본다)

 

물론 Brute Force(보통 완탐이라 부르는) 알고리즘의 경우이고, 백트래킹의 가지치기나 이분 탐색 등을 사용한다면

더 많은 수의 연산까지 가능할 것이다

 

따라서 우리 알고리즘이 최악의 경우를 만족한다면, 다른 경우는 항상 만족할 것이기 때문에 우리는 코딩 문제를 풀 때

최악의 경우를 고려하며 문제 해결을 해야 한다

 

시간 복잡도란 입력값에 따른 연산 횟수를 측정해 알고리즘의 성능을 나타내는 지표다

우리는 시간 복잡도를 기준으로 N^2 연산, logN 연산 등이 가능할지를 판단해야 하며,

판단을 기준으로 자료구조와 연산 방식(알고리즘)을 택한다(이분 탐색, 완전 탐색 등)

1.3 시간 복잡도를 빅오 표기법으로 표기하기

시간 복잡도는 점근적 표기법을 기준으로 한다

코딩 테스트에서는 정밀한 연산 횟수를 요구하지 않는다, 다만 추이를 요구한다

따라서 이 N이라는 수를 무한으로 생각했을 때, 상수항은 무시된다

 

예를 들어 N + 5와 같은 경우 N이 무한으로 커진다면? 5는 무시되고 O(N)이 남는다

만약 N^2 + 3N + 5인 경우라면 3N + 5는 N^2에 비해 작으므로 무시되고, O(N^2)만 남는다

 

방법을 정리하자면

1. 다항식에서 가장 많이 영향을 미치는 항을 남기고 제거

   → N^2 + 3N + 5에서 3N + 5는 제거된다

2. 마지막 남은 항의 계수를 제거

  → 3N + 5의 시간 복잡도 또한 O(N)으로 작성할 수 있다

 

식	이름
y = x!	팩토리얼 함수
y = 2^x	지수 함수
y = x^2	다항 함수
y = xlogx	로그 함수 + 다항 함수
y = x	다항 함수
y = logx	로그 함수
y = 1	상수

 

시간 복잡도는 위에서 아래 순으로 효율이 높아진다

아래로 갈 수록 큰 범위의 연산이 가능하다는 의미

 

팩토리얼 함수는 보통 11! 까지 사용이 가능하다

11! = 39,916,800

12! = 479,001,600

12팩만 되어도 벌써 5억 가까이 된다

 

지수 함수는 2^26 ~ 2^27까지 사용 가능하다

2^26 = 67,108,864

2^27 = 134,217,728

 

이런 식으로 x에 따른 연산 횟수를 고려하며 문제를 해결해야 한다

 

1차원 배열 탐색은 O(N)

2차원 배열 탐색은 O(N * M)

 

이진 탐색 트리에서는 트리의 높이에 따라 O(logN)이 나온다

이진 탐색 트리는 높이 k인 경우 탐색 소요가 1 + 2 + 2^2 + 2^3... 2^k = N이 된다

(N은 탐색할 수!)

공비(r) = 2

초항(a) = 1로

등비수열의 합 공식

여기 n은 항의 수이다

여기에 대입하면

 

여기서 k-1인 이유는, 2^0부터 시작하기 때문!

이 값은 2^(k-1) -1 = N이 된다

k-1의 -1과 뒤의 -1은 모두 제거 가능하다(매우 큰 값을 생각할 때 의미가 없는 값이다)

따라서 2^k = N

값이 나온다

여기서 2도 제거하여 K = logN이라는 최종 시간 복잡도가 나온다

1.4 코딩 테스트에서 꼭 알아둬야 할 시간 복잡도

따라서 테스트케이스의 최댓값을 보고 시간 복잡도를 계산하여 알고리즘을 선택해야 한다

초당 1억 번의 연산을 진행할 수 있지만, 여유 있는 값을 기준으로 작성된 내용 같다

보통 나는 계산할 때 N^2은 10,000까지 사용할 수 있다고 판단했으니 말이다

추후 알고리즘을 풀 때 테스트 범위를 여유롭게 고려하여 문제를 풀어보아야겠다

(성능을 배제하고 문제의 요구를 만족해야 하기 때문이다)

시간 복잡도	최대 연산 횟수	대표 알고리즘
O(N!)	10	순열, 외판원 문제
O(2^N)	20 ~ 25	미개선 피보나치, 부분 집합 생성
O(N^3)	200 ~ 300	삼중 반복문, 플로이드-워셜, 행렬 곱셈
O(N^2)	3,000 ~ 5,000	이중 반복문, 버블/삽입/선택 정렬
O(NlogN)	100만	퀵/병합/힙 정렬, 고속 푸리에(?)
O(N)	1,000 ~ 2,000만	반복문, 카운팅 정렬
O(logN)	10억	이진 트리, 이진 탐색
O(1)		Hash table, stack/queue 삽입 삭제 조회

 

1.5 실전 예시

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

프로그래머스 짝지어 제거하기 문제

주어진 문자열 최대 길이는 1,000,000 즉, 100만이다

따라서 우리는 NlogN 이하의 시간 복잡도를 가진 알고리즘을 사용해야 한다

당시 내가 사용한 해결 방식은 Stack을 사용해 선형 시간으로 해결하였다(O(N))

 

 

 

마무리

시간 복잡도에 대해 깊게 고민하는 시간을 가져본 적이 없었다

대략 2중 반복문은 10,000 정도, 3중 반복문은 100 정도에서 해결하고 대부분은 감으로 해결하고 있었다

 

스터디를 통해 시간 복잡도에 대해 제대로 정리하고 문제 해결에 앞서 고려하는 풀이를 진행해야겠다