코딩 테스트를 준비하기 위한 기초 개념 (시간복잡도, 디버깅) - 시간복잡도

기초 개념을 다시 연습하는 이유

코테 준비를 하면서, 오류와 실수를 범하는 일이 많아지고, 

그러면서 자연스럽게 문제도 시간내에 풀지못하는 일이 많이 발생하였습니다.

 

문제를 푸는 과정을 회상해 보니,

1. 처음 부터 문제를 잘못 읽음 (제대로 안 읽음)

2. 반복문 범위를 잘 못 설정함.

3. 변수 이름을 이상하게 만들어서 변수 사용하는게 헷갈림

등등 여러 많은 문제들...

 

논리적인 오류보다는 이런 잡다한 실수들이 많다는 것을 알게 되었습니다.

이런 실수들이 지금 보기에는 별거 아닌거 같지만,

점점 쌓이다보면 코테 탈락에 치명적인 요소로 적용한다는 것을 몸소 체감하였기에,

기초를 바로잡아야 한다고 생각하였습니다.

 

그래서 가장 기본기인 시간복잡도 부터 포스팅 하려고 합니다.

 

---

시간복잡도

코테 문제를 풀기 위해서는 시간 복잡도 고려가 필수적입니다.

주어진 데이터의 크기를 고려하여 주어진 시간내에 문제를 해결해야 하기 때문에

 

그 문제에 적절한 시간복잡도를 가진 알고리즘을 선택하여 문제에 접근해야 합니다.

처음부터 잘못된 알고리즘을 선택해서 문제를 풀기 시작하면 큰일나니까요 하하

 

코테에서 시간 복잡도란,

 

주어진 문제를 해결하기 위해서 필요한 연산 횟수를 의미합니다.

 

일반적으로 언어는 1초에 2000만번~1억번의 연산을 수행가능합니다.

 

빅-오메가 : best case (최선) 연산 횟수

빅-세타 : average case (평균) 연산 횟수

빅-오 : worst case (최악) 연산 횟수

 

우리가 보통 사용하는 시간복잡도는 빅-오 입니다.

 

많은 분들도 아시겠지만, 최악의 경우(빅-오)를 고려하는 것이 코테에서 유리합니다.

 

코테에서는 여러가지 테스트 케이스를 통과해야 1문제를 해결하는 것이기 때문에,

최악의 경우를 고려하여 문제를 풀어야 합니다.

 

아래 그래프는 유명하죠?

데이터의 크기(n)이 증가할때 마다 시간복잡도. 즉, 성능(수행속도)가 안 좋아 지는 것을 확실히 알 수 있습니다.

(여기서, log의 밑은 보통 2를 의미하는데, 빅-오 표기법에서 log의 밑은 크게 영향을 주지 않으므로 신경쓰지 않아도 됩니다)

 

빅-오 O(n)의 시간복잡도

 

빅-오 시간복잡도를 사용하여 어떤 알고리즘을 선택할지 예시를 들어 고민해봅시다!

 

문제	정렬문제라고 가정하겠습니다.
제한시간	2초
입력 크기 (N)	1<= N <= 1,000,000

 

사용할 정렬	버블 정렬	병합 정렬
시간 복잡도	O(n^2)	O(nlogn)

 

연산 횟수는 1초에 대략 2000천만번이라고 생각한다면, 

버블 정렬은 (1,000,000)^2 = 1조 > 4천만

병합 정렬은 (1,000,000)log(1,000,000) = 2천만 < 4천만

이므로 우리는 병합정렬을 사용해야 한다는 근거를 빅-오 표기법을 통해 얻을 수 있습니다!!

 

 

시간복잡도를 통해서 코드의 효율성 높이기

N = 10000

# 1. 연산 횟수 N
for i in range(N):
	print("wow")
    
# 2. 연산 횟수 3N
for i in range(3N):
	print("wow")
    
# 3. 연산 횟수 N^2
for i in range(N):
	for j in range(N):
    	print("wow")

 

 

보통 시간복잡도를 반복문을 기준으로 측정하는 경우가 많습니다.

위의 코드에서도 볼 수 있듯이, 각 반복문 마다 연산횟수를 계산할 수 있습니다.

 

하지만 시간복잡도는 아래의 원칙을 따르며, 연산횟수와는 조금 차이가 있습니다.

 

1. 상수는 무시한다

2. 반복문의 수행횟수가 가장 큰 것이 시간복잡도의 기준이 됩니다.

 

1번 원칙에 따라, 위의 코드에서 1번/2번 케이스의 시간 복잡도는 O(n)

3번 케이스의 시간 복잡도는 O(n^2)이라고 볼 수 있지만, 

 

결국 2번 원칙에 따라 위 코드의 시간 복잡도는 O(n^2)입니다.

(N과 3N은 언뜻보면 큰 차이가 있는 것 같지만, 시간복잡도에서는 큰 차이가 없기 때문에 무시해도 됩니다. 그래서 상수는 무시!)

 

간단하지만, 이처럼 시간복잡도를 내가 알아낼 수 있다면

실제 코테에서 시간초과 문제가 발생하였을때,

문제가 되는 부분을 찾고, 코드 로직 효율성을 개선할 수 있을 겁니다!