코딩 테스트 준비하기

코딩 테스트를 준비하기 전에 반드시 알아야 할 2가지 스킬이 있습니다.

바로 시간 복잡도와 디버깅입니다.

어떤 알고리즘으로 풀어야 될지 선택의 기준이 되는 것이 바로 시간 복잡도이며

어떻게 코드의 논리 오류를 잡을 지 탐색하는 방법이 바로 디버깅입니다.

 

우선적으로 시간 복잡도에 대해 알아보겠습니다.

알고리즘에서 시간 복잡도는 주어지는 문제를 해결하기 위한 연산 횟수를 의미합니다.

일반적으로 파이썬 프로그램에서는 2,000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있습니다.

 

시간 복잡도 표기법 알아보기

시간 복잡도 정의하기

• 빅-오메가: 최선일 때의 연산 횟수를 나타낸 표기법
• 빅-세타: 보통일 때의 연산 횟수를 나타낸 표기법
• 빅-오: 최악일 때의 연산 횟수를 나타낸 표기법

코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋습니다.

 

시간 복잡도 활용하기

000 문제 : 수 정렬하기

https://www.acmicpc.net/problem/2750

 

시간 제한이 1초이므로 이 조건을 만족하려면 2,000만 번 이하의 연산 횟수로 문제를 해결해야 합니다.

• 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 생각합니다.
• (“2천만 회/초”는 C++/Java 기준 대략치라서, Python은 더 낮습니다.)
• 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 합니다.

연산 횟수 계산 방법

• 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

알고리즘 적합성 평가(위 문제에선 N의 범위가 너무 작아 N의 최대 범위를 10,000으로 잡았습니다.)

• 버블 정렬 = (10,000)² = 100,000,000 > 20,000,000 → 부적합 알고리즘
• 병합 정렬 = 10,000log₂(10,000) = 약 132,900 < 20,000,000 → 적합 알고리즘

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

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

# 예제 1: 연산 횟수 = N
N  = 100000
cnt = 1

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

# 예제 2: 연산 횟수 = 3N
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

위 코드를 보면 연산 횟수는 3배의 차이가 납니다.

하지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간복잡도는 O(n)으로 같습니다.

# 예제 3: 연산 횟수 = N²
N  = 100000
cnt = 1

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

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출합니다.

따라서 이 코드에서는 이중 for문이 전체 코드의 시간 복잡도 기준이 됩니다.

추가로 일반 for문이 10개 더 있다 하더라도 시간 복잡도는 N²으로 유지됩니다.

 

디버깅은 왜 중요할까?

디버깅은 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 의미합니다.

• 문법 오류: 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않습니다.
• 논리 오류: 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생합니다.

디버깅의 중요성

많은 사람이 문법을 배우는 과정에서 디버깅을 가볍게 생각하고 넘어갑니다.

하지만 코딩 테스트에서 반드시 필요한 기술이고, 알아 두기만 하면 되는 것이 아니라 문제를 풀 때 반드시 해야 하는 과정입니다.

다음은 코딩 테스트에 떨어진 응시자들이 많이 하는 말들입니다.

※ index 범위 1개 차이로 시험에서 떨어졌어요.

※ 답이 나오지 않아 몇 시간 동안 헤맸는데, 알고보니 예외 처리를 하나 빠트렸네요.

 

디버깅하는 법

1. 코드에서 디버깅하고자 하는 줄에 중단점을 설정한다. 이때 중단점은 여러 개 설정할 수 있다.
2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며,
3. 이 과정에서 추적할 변숫값도 지정할 수 있다. 이 방법으로 변숫값이 자신이 의도한 대로 바뀌는지 파악한다.
4. 변숫값 이외에서 원하는 수식을 입력해 논리 오류를 파악할 수 있다.

코딩 테스트를 진행하면 실수하기 쉬운 4가지 오류 찾아보기

# 결함이 있는 코드 예제
# 배열의 주어진 범위의 합을 2로 나눈 몫을 구하세요.
import random

testcase = int(input())
answer = 0
A = [0] * (100001)

for i in range(0, 100001):
	A[i] = random.randrange(1, 101)
    
for t in range(1, testcase + 1):
	start, end = map(int, input().split())
    
    for i in range(start, end + 1):
    	answer = answer + A[i]
        
   	print(str(testcase) + " " + str(answer / 2))

1. 변수 초기화 오류 찾아보기→ 두 번째 테스트 케이스부터 통과하지 않을 때는 모든 변수가 정상적으로 초기화되고 있는지 확인
2. 반복문에서 인덱스 범위 지정 오류 찾아보기→ 반복 범위, 비교 연산자(<, <= 등), 배열 인덱스는 0부터 시작 
3. 잘못된 변수 사용 오류 찾아보기→ 출력 부분이나 로직 안에서 사용해야 하는 변수를 다른 변수와 혼동하여 잘못 사용하는 경우
4. 파이썬 자동 형 변환 조심하기→ 데이터 계산 도중 다양한 연산이 수행될 때 예상하지 못한 형 변환이 일어날 수 있음

파이썬에서의 나누기는 / 연산자와 // 연산자 두 가지이다!

• / 연산: 나눗셈을 한 결괏값을 float형으로 출력하며 소수점의 결과까지 보여준다.
• // 연산: 나눗셈을 한 결괏값을 int형으로 출력하며 몫의 결만 보여준다.
• % 연산: 나눗셈을 한 후 나눈 나머지 값을 보여준다.