코딩테스트에서 시간복잡도 계산

😎 코딩테스트에선 어떤 시간 복잡도 유형을 사용해야 할까?

코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다. 또한 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 계산하는 것이 좋다.
응시자가 작성한 프로그램으로 모든 케이스를 통과해야만 합격으로 판단하므로 "최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다. 그러므로 시간 복잡도를 판단할 때는 최악일 때(worst case)를 염두에 둬야 한다.

😓 시간 복잡도 활용하기

• 알고리즘 선택의 기준으로 사용하기
  

버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n²), O(nlogn)이라고 알고 있다고 가정하자.
시간 제한이 2초이므로 이 조건을 만족하려면 4,000만 번 이하의 연산 횟수로 문제를 해결해야 한다.

따라서 문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지를 판단할 수 있다.

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출이라는 공식을 대입해 각 알고리즘이 이 문제에 적합한지 판단해 보겠다.

• 버블 정렬 = (1,000,000)² = 1,000,000,000,000 > 40,000,000 → 부적합 알고리즘
• 병합 정렬 - 1,000,000log₂(1,000,000) = 약 20,000,000 < 40,000,000 → 적합 알고리즘

문제에 주어진 시간 제한이 2초이므로 연산 횟수 4,000만 번 안에 원하는 답을 구해야 한다. 버블 정렬은 약 1조 번의 연산 횟수가 필요한 반면, 병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 병합 정렬이 적합한 알고리즘이라고 판단할 수 있다.

이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다. 즉, 데이터의 크기(N)를 단서로 사용해야하는 알고리즘을 추측해 볼 수 있다.

👻 시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다. 시간 복잡도를 도출하려면 다음 2가지 기준을 고려해야 한다.
1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

예제1

N = 100000
cnt = 1

for i in range(N):
	print("연산 횟수" + str(cnt))
    cnt += 1

예제2

N = 100000
cnt = 1

for i in range(N):
	print("연산 횟수" + str(cnt))
    cnt += 1

for i in range(N):
	print("연산 횟수" + str(cnt))
    cnt += 1

for i in range(N):
	print("연산 횟수" + str(cnt))
    cnt += 1

예제 1의 연산 횟수는 N번이고, 예제 2의 연산 횟수는 3N번으로 3배의 차이가 난다. 언뜻 생각하면 큰 차이인 것 같지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다.

예제3

N = 100000
cnt = 1

for i in range(N):
	for j in range(N):
		print("연산 횟수" + str(cnt))
    	cnt += 1

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서 이중 for 문이 전체 코드의 시간 복잡도 기준이 된다. 만약 일반 for 문이 10개가 더 있다 하더라도 도출 원리의 기준 '2'에 따라 시간 복잡도의 변화 없이 N²으로 유지된다.

이와 같이 자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다.

논리 오류를 찾을 수 있는 가장 최선의 방법, 디버깅

👻 디버깅은 왜 중요할까?

프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅이라고 한다. 문법 오류는 컴파일러가 자동으로 찾아주므로 테스트할 때 문제가 되지 않는다. 논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생한다.

디버깅의 중요성

코딩 테스트에 떨어진 응시자와 만나 이야기하다 보면 이런 말을 많이 한다.
"아! index 범위 1개 차이로 이번 시험에 떨어졌어요. 너무 아쉬워요."
"계속 답이 나오지 않아 몇 시간 동안 헤맸는데, 알고 보니 예외 처리 하나를 빠트렸네요."
두 학생이 디버깅을 제대로 했다면 아마 코딩 테스트에 통과했을 것이다.
디버깅은 코딩테스트에 필요한 기술이고, 그냥 알아 두기만 하면 되는 것이 아니라 문제를 풀면서 반드시 해야 하는 과정이다. 반드시 디버깅을 익힌 후에 코딩 테스트에 응시하기 바란다.

디버깅 하는 법

[디버깅 레퍼런스](드림코딩 - 코딩의 시작과 끝, 디버깅 | 실력있는 개발자의 필수 무기)

코테를 진행하며 실수하기 쉬운 4가지 오류

1. 변수 초기화 오류 찾아보기
   실제 코딩 테스트의 두 번째 테스트 케이스부터 통과되지 않을 때는 모든 변수가 정상적으로 초기화되고 있는지 디버깅을 이용해 확인해 보자.

2. 반복문에서 인덱스 범위 지정 오류 찾아보기
   반복문을 사용할 때마다 범위와 시작 인덱스를 꼼꼼하게 확인하고, 혹시 모를 입력 실수를 대비해 디버깅하는 습관을 들이자.(디버깅을 통해 의도와 다른 값이 있는 부분이 있는지 확인하기)

3. 잘못된 변수 사용 오류 찾아보기
   출력 부분이나 반복문에서 사용해야 하는 변수를 다른 변수와 혼동하여 잘못 사용하는 경우도 있다.

4. 파이썬 자동 형 변환 조심하기
   e.g. / 연산자(float)와 // 연산자(int)