미리 보는 코딩 테스트 오답 노트

시간 초과의 원인을 찾아 해결하기

코딩 테스트에서 자주 마주치는 문제는 바로 시간 초과입니다.

이럴 때는 입력과 출력 방식부터 최적화할 수 있는지 점검해 보는 것이 좋습니다.

 

시간 초과가 발생했을 때 점검할 2가지

1. 풀이 로직의 시간 복잡도를 점검합니다.
2. 입출력 방식의 최적화를 고려해야 합니다.

• input() → sys.stdin.readline()
• print() → sys.stdout.write()

input()은 호출될 때마다 한 줄을 읽어 끝의 개행 문자를 제거한 문자열을 반환하며, 숫자 변환 등 추가 파싱은 호출자가 직접 처리해야 함

print()는 기본적으로 출력 내용을 버퍼에 모았다가 상황에 따라 비우지만, 반복 호출이 많으면 작은 단위의 잦은 쓰기로 인해 성능이 저하됨

 

sys.stdin.readline()은 입력 버퍼에서 한 줄 전체를 그대로 읽어 대량 입력에서 더 빠른 성능을 낼 수 있음

sys.stdout.write()는 개행 문자를 자동으로 붙이지 않으므로, 여러 출력을 모아 한 번에 출력하면 속도를 크게 향상시킬 수 있음

 

# 일반적인 입출력 방식
a = int(input())
print(a)

# 빠른 입출력 방식
import sys

b = int(sys.stdin.readline())
sys.stdout.write(str(b) + '\n')	# sys.stdout.write()는 문자열만 출력할 수 있어서 정수는 str()로 변환 후 출력

인덱스에 의미 부여하여 풀어보기

코딩 테스트에서 가장 기본적으로 사용하는 파이썬 자료구조는 List 입니다.

보통 List를 사용할 때는 인덱스로 데이터에 접근합니다.

인덱스는 일반적으로 '몇 번째 데이터인지' 나타내는 역할을 합니다.

하지만 상황에 따라 인덱스에 해싱 개념을 적용하여 단순한 위치가 아니라 특정한 의미를 지닌 값으로 활용할 수 있습니다.

 

A[1]의 의미

1. 몇 번째 데이터인지 순서를 의미하는 경우 → 첫 번째 데이터를 저장합니다.
2. 숫자값으로 의미를 부여한 경우 → 1 이라는 값이 몇 개 있는지를 저장합니다.

인덱스에 숫자값으로 의미를 부여할 때 유리한 경우

ex) 1000보다 작은 자연수 10,000,000개를 1초 안에 정렬해야 하는 상황

(데이터의 양이 많아서 일반적인 방법으로는 1초 안에 정렬하기가 어려움)

→ 인덱스 값 자체로 활용하면 계수 정렬과 같은 방식으로 제한 시간 내에 정렬할 수 있음

# 인덱스에 의미를 부여한 대표 사례 - 계수 정렬
import sys

N = int(sys.stdin.readline())
count = [0] * 1000
numbers = list(map(int, sys.stdin.readline().split()))

for number in numbers:
	count[number] += 1	# 인덱스에 숫자값으로 의미를 부여하여 데이터를 저장
    
for i in range(1000):
	if count[i] != 0:
    		for _ in range(count[i]):
        		sys.stdout.write(str(i) + ' ')

 

나머지 연산의 중요성 알아보기

코딩 테스트 문제에서는 정답을 나머지 값으로 요구하는 경우가 있습니다.

이 문제에는 단순한 출력형식의 지시가 아니라 큰 수의 연산을 효율적으로 처리하고, 나머지 연산의 수학적 성질을 활용할 수 있는지 확인하려는 의도가 담겨 있습니다.

 

나머지 연산의 분배 법칙

나머지 연산은 나눗셈을 제외하고 다음과 같이 덧셈, 뺄셈, 곱셈의 분배 법칙이 성립합니다.

# 예시 값: A = 8, B = 3, C = 5

# 덧셈의 분배 법칙 성립 → (A + B) % C = (A % C + B % C) % C
(8 + 3) % 5 = 11 % 5 = 1
(8 % 5 + 3 % 5) % 5 = (3 + 3) % 5 = 1

# 뺄셈의 분배 법칙 성립 → (A - B) % C = (A % C - B % C) % C
(8 - 3) % 5 = 5 % 5 = 0
(8 % 5 - 3 % 5) % 5 = (3 - 3) % 5 = 0

# 곱셈의 분배 법칙 성립 → (A * B) % C = (A % C * B % C) % C
(8 * 3) % 5 = 24 % 5 = 4
(8 % 5 * 3 % 5) % 5 = (3 * 3) % 5 = 4

# 나눗셈의 분배 법칙은 성립하지 않음 → (A / B) % C != (A % C) / (B % C) % C
(8 / 3) % 5 = 2.666 % 5 = 2.666
(8 % 5) / (3 % 5) % 5 = (3 / 3) % 5 = 1

파이썬에선 int형이 자동으로 확장되므로 정수 오버플로는 발생하지 않습니다.

하지만 숫자가 매우 커지면 계산 속도가 급격히 느려지고 시간 초과에 걸릴 수 있습니다.

즉, 마지막에만 % 연산을 적용해도 정답은 계산할 수 있지만, 채점 서버에서는 시간 초과로 처리되어 오답이 될 수 있습니다.

→ 중간 과정마다 나머지 연산을 적용하는 습관이 중요합니다.

 

ex) 1부터 100,000까지 곱한 값을 1,000,000,007로 나눈 나머지를 구하시오.

1. 모든 값을 곱한 뒤 마지막에 나머지 연산을 한번 적용하는 코드 (수행 시간: 2.818791초)

# 1부터 100000까지 곱한 값을 1000000007로 나눈 나머지 구하기
import time

answer = 1
start = time.time()

for i in range(1, 100001):
	answer *= i
    
result = answer % 1000000007	# 곱한 값을 1000000007로 나눈 나머지 연산을 수행하는 로직
end = time.time()

print("결과:",result)
print("수행 시간: {:.6f}초".format(end-start))

 

2. 곱셈을 수행할 때마다 나머지 연산을 적용하는 코드 - 수정본 (수행 시간: 0.008505초)

# 1부터 100000까지 곱한 값을 1000000007로 나눈 나머지 구하기
import time

MOD = 1000000007
answer = 1
start = time.time()

for i in range(1, 100001):
	answer = (answer * i) % MOD	# 곱셈을 수행할 때마다 나머지 연산을 수행하는 로직
    
end = time.time()

print("결과:",result)
print("수행 시간: {:.6f}초".format(end-start))

곱셈, 덧셈 등 중간 계산을 할 때마다 나머지 연산을 적용하는 습관이 필수입니다.

정렬 기초 다지기

코딩 테스트는 기본적으로 다양한 데이터를 효과적으로 다루는 것에서 시작합니다.

데이터를 효과적으로 다루는 방법 중에서 특히 정렬은 거의 모든 알고리즘 문제의 출발점이자 기반이 되는 핵심 요소입니다.

• 이진 탐색과 같은 특정 알고리즘은 정렬된 데이터에만 적용할 수 있음
• 정렬은 그리디 알고리즘과 투 포인터, 우선순위 큐 문제에서도 전처리할 때 반드시 등장함

오름차순 정렬: 데이터를 가장 작은 값부터 시작하여 점차 큰 값으로 나열하는 과정을 의미

• sort(): 리스트 객체 자체를 정렬하며 반환값은 None(원본 유지 X)
• sorted(): 정렬된 복사본을 반환(원본 유지 O)

내림차순 정렬: 데이터를 가장 큰 값부터 시작하여 점차 작은 값으로 나열하는 과정을 의미

• sort(reverse=True): reverse=True 옵션을 사용하여 리스트 객체 자체를 정렬하며 반환값은 None(원본 유지 X)
• sorted(reverse=True): reverse=True 옵션을 사용하여 정렬된 복사본을 반환(원본 유지 O)

코딩 테스트에서는 때때로 정렬 함수를 직접 제어할 수 없는 경우도 있습니다.

→ 부호를 일시적으로 반전시키는 방법이 유용합니다.

# 내림차순 정렬
A = [5, 3, 2, 4, 1]

# 부호를 반전시키고 오름차순으로 정렬한 후, 다시 부호 되돌리기
A = [-x for x in A]	# 부호 반전
A.sort()
A = [-x for x in A]	# 부호 반전

print("부호 반전 방식 내림차순:", A)

 

다중 조건 정렬 익히기

코딩 테스트 문제를 다루다 보면 데이터를 여러 기준에 따라 정렬해야 하는 상황이 자주 발생합니다.

ex) 성적을 정렬할 때 먼저 영어 점수를 기준으로 하되, 영어 점수가 같을 경우에는 수학 점수를 기준으로 하고싶은 상황

→ 다중 조건 정렬을 사용하면 여러 조건을 동시에 적용하여 원하는 순서대로 데이터를 정렬할 수 있습니다.

파이썬에는 대표적으로 튜플 기반 정렬과 딕셔너리 기반 정렬이 있습니다.

 

튜플 기반 정렬: 단순 입력 처리에 최적의 정렬 방식이며, 가장 자주 사용하는 방식은 데이터를 (기준1, 기준2, •••) 형태의 튜플로 구성한 뒤, sort(), sorted() 함수의 key 인자에 lambda를 사용해 정렬 기준을 지정하는 것입니다.

# 튜플 기반 다중 조건 정렬
# 영어, 수학 순서로 튜플 데이터 저장
scores = [
	(80, 100),
    	(100, 50),
    	(70, 100),
    	(80, 90)
]

# 영어 점수로 내림차순 정렬, 영어 점수가 같으면 수학 점수로 내림차순 정렬
scores.sort(key=lambda x: (-x[0], -x[1]))

for s in scores:
	print(f"english={s[0]}, math={s[1]}")

 

딕셔너리 기반 정렬: 필드명이 있는 복잡한 데이터 처리에 적합한 정렬 방식입니다.

# 딕셔너리 기반 다중 조건 정렬
scores = [
	{'english': 80, 'math': 100},
    	{'english': 100, 'math': 50},
    	{'english': 70, 'math': 100},
    	{'english': 80, 'math': 90}
]

# 수학 점수로 내림차순 정렬, 수학 점수가 같으면 영어 점수로 내림차순 정렬
scores.sort(key=lambda x: (-x['math'], -x['english']))

for s in scores:
	print(s)

코딩 테스트에서는 빠른 처리를 위해 튜플 기반 정렬을 자주 사용하지만,

복잡한 데이터일수록 딕셔너리 기반 정렬도 유용하게 활용합니다. 

이차원 리스트 제대로 다루기

코딩 테스트 문제에서는 그래프와 관련된 알고리즘이 자주 등장합니다.

이때 그래프의 구조를 표현하는 데 많이 사용하는 것이 이차원 리스트입니다.

특히 인접 리스트 방식으로 그래프를 표현할 때, 이차원 리스트의 선언과 데이터 저장, 활용 방법을 잘 알고 있어햐 합니다.

 

이차원 리스트를 이용한 그래프 구현

1. 이차원 리스트 선언과 초기화: 파이썬에서는 리스트 안에 또 다른 리스트를 넣는 방식으로 이차원 리스트를 구성

(보통 노드 번호는 1번부터 시작하므로, 인덱스 0은 사용하지 않고 N+1 크기로 리스트를 초기화합니다.)

# 정점이 3개 있다고 가정 (1 ~ 3번 사용)
N = 3
graph = [[] for _ in range(N + 1)]

2. 그래프 데이터 저장하기

(보통 이런 그래프는 코딩 테스트에서 다음과 같은 입력값으로 주어집니다.)

3 4	# 노드가 3개, 엣지가 4개인 그래프
1 2 4	# 1번 노드에서 2번 노드로 가는 가중치 4의 엣지가 있음
2 1 10
1 3 7
3 2 6

# 정점 수와 간선 수 입력
N, E = map(int, input().split())

# 간선 정보를 입력받아 저장
for _ in range(E):		# 저장할 엣지의 개수만큼 반복
	s, e, w = map(int, input().split())
    	graph[s].append((e, w))	# 이차원 리스트에 그래프 데이터 저장

3. 그래프 데이터 가져오기

# 1번 노드에서 시작되는 엣지 데이터를 가져오는 코드
for nextNode, weight in graph[1]:
	print(f"next Node {nextNode}, weight = {weight}")