1. 어떤 알고리즘으로 풀어야 할까?
알고리즘 선택의 기준은 시간 복잡도입니다.
1-1. 시간 복잡도 표기법
- 빅-오메가($\Omega(n)$): 최선일 때(Best Case)의 연산 횟수
- 빅-세타($\Theta(n)$): 보통일 때(Average Case)의 연산 횟수
- 빅-오($O(n)$): 최악일 때(Worst Case)의 연산 횟수 (코딩 테스트의 기준)
1-2. 시간 복잡도 활용 가이드
- 상수는 제외: $O(2N)$은 $O(N)$으로 취급합니다.
- 최대 차수 기준: 가장 많이 중첩된 반복문의 수행 횟수가 전체 시간 복잡도를 결정합니다.
2. 디버깅: 논리 오류를 잡는 필수 과정
디버깅은 문법 오류뿐만 아니라, 결과가 예상과 다르게 나오는 논리 오류를 찾는 과정입니다.
- 중단점(Breakpoint) 설정: 코드 실행을 멈추고 싶은 지점에 설정합니다.
- 한 줄씩 실행(Step Over): 변숫값이 의도대로 바뀌는지 실시간으로 추적합니다.
- 수식 확인: 변수 외에도 특정 수식의 결과값을 미리 계산해 보며 논리를 검증합니다.
3. 실전 코딩 테스트 오답 노트 & 꿀팁
3-1. 시간 초과 해결 (빠른 입출력)
파이썬의 기본 input()은 속도가 느려 시간 초과가 발생할 수 있습니다. sys.stdin.readline을 생활화합시다.
import sys
# 일반적인 방식보다 훨씬 빠른 입력
N = int(sys.stdin.readline())
sys.stdout.write(str(N) + '\n')
3-2. 인덱스에 의미를 부여하는 '계수 정렬'
인덱스에 해싱 개념을 적용하면 별도의 정렬 알고리즘 없이도 데이터를 정리할 수 있습니다.
import sys
# 0~1000 범위의 숫자를 정렬할 때 유용
N = int(sys.stdin.readline())
count = [0] * 1001
numbers = list(map(int, sys.stdin.readline().split()))
for number in numbers:
count[number] += 1
for i in range(1001):
if count[i] != 0:
for _ in range(count[i]):
sys.stdout.write(str(i) + ' ')
3-3. 나머지 연산($\%$)의 분배 법칙
결과값이 너무 커질 경우, 계산 중간중간 나머지 연산을 수행해도 결과는 동일합니다. (단, 나눗셈은 제외)
- $(A + B) \pmod C = (A \pmod C + B \pmod C) \pmod C$
- $(A \times B) \pmod C = (A \pmod C \times B \pmod C) \pmod C$
3-4. 정렬(Sorting) 기법
| 방식 | 코드 | 특징 |
| 오름차순 (원본 변경) | A.sort() | 리스트 자체가 정렬됨 |
| 오름차순 (새 리스트) | B = sorted(A) | 원본은 유지하고 정렬된 리스트 반환 |
| 내림차순 | A.sort(reverse=True) | 큰 값부터 정렬 |
| 부호 반전 | A = [-x for x in A] | 숫자의 부호를 바꿔 오름차순 정렬 후 다시 반전 |
3-5. 다중 조건 정렬 (Lambda 활용)
여러 기준으로 정렬해야 할 때는 튜플이나 딕셔너리를 활용합니다.
# 영어 점수는 내림차순, 수학 점수는 내림차순
scores.sort(key=lambda x: (-x[0], -x[1]))
4. 이차원 리스트 & 그래프 다루기
이차원 리스트는 그래프 알고리즘(DFS, BFS 등)의 핵심 구조입니다.
선언과 초기화
N = 3
graph = [[] for _ in range(N + 1)] # 빈 리스트로 초기화
데이터 저장 및 조회
# s: 시작 노드, e: 끝 노드, w: 가중치
for _ in range(E):
s, e, w = map(int, sys.stdin.readline().split())
graph[s].append((e, w))
# 1번 노드와 연결된 노드들 확인
for next_node, weight in graph[1]:
print(f"Next: {next_node}, Weight: {weight}")