코딩 테스트 접근법

코딩 테스트에서 시간이 부족해지는 이유는 대개 설계 없이 코드부터 쓰다가 중간에 방향을 잃기 때문이다. 아래는 문제를 풀 때 따르는 순서와 자주 쓰는 실전 팁이다.

문제 풀이 순서

1. 비어 있는 조건을 확정한다. 문제는 일부러 덜 정해져 있는 경우가 많다. 중복 값이 있는가, 입력이 늘 유효한가, 문자 집합과 대소문자 구분은 어떤가, 끝점이 맞닿은 구간은 겹친 것인가, 시간·공간 제약이 있는가를 묻거나 가정으로 적어 둔다.
2. 주석으로 먼저 설계한다. 풀이 단계를 한국어 주석으로 적고, 그 아래에 코드를 채운다.
3. 떠오르는 테스트 케이스(TC)를 적어 둔다. 특히 경계 조건(최솟값, 최댓값, 빈 입력, 정답이 없는 경우)을 미리 적는다. 입력 유형별 목록은 아래 「놓치기 쉬운 경계 사례」에 있다.
4. 주석을 읽으며 코딩한다. 설계와 구현을 분리하면 실수가 줄고 막혔을 때 어디서 막혔는지 바로 보인다.
5. 감정도 적는다. "여기 헷갈림", "시간 초과 걱정" 같은 메모가 나중에 복습할 때 약점을 알려 준다.
6. 다 풀면 정리한다. 불필요한 디버깅 코드는 지우고 TC와 핵심 아이디어만 남긴다. 면접처럼 시간이 정해진 자리에서 일부러 단순하게 처리한 부분(정규식 대신 split 등)이 있으면, 제약이 없을 때 어떻게 바꿀지 말로 덧붙인다.

# 1. 입력: N(≤ 100,000), 수열 A
# 2. 아이디어: 정렬 후 투 포인터 → O(N log N)
# 3. TC: N=1, 모두 같은 값, 정답이 없는 경우
# 4. 출력: 조건을 만족하는 쌍의 개수

출제 유형과 우선순위

기업 코딩 테스트에 자주 나오는 알고리즘·자료구조를 출제 빈도 순으로 묶었다. 「반드시」부터 개념을 익힌 뒤 유형별 문제로 연습하고 범위를 넓힌다.

연습 방법

1. 쉬운 단계(프로그래머스 1레벨)로 언어 문법부터 손에 붙인다. 문법이 막히면 알고리즘을 떠올려도 못 쓴다.
2. 유형별 문제집(프로그래머스 고득점 Kit, 백준 단계별·solved.ac 태그)으로 위 표를 차례로 훑는다.
3. 문제를 읽으면 제한 조건의 입력 크기로 허용 복잡도를 먼저 계산해 후보 알고리즘을 좁힌다(아래 표).
4. 맞혀도 다른 사람의 풀이를 반드시 본다. 더 짧고 빠른 방법을 배운다.

막혔을 때 풀이를 볼 시점을 미리 정해 두면 시간을 버리지 않는다.

자기기만 피하기

위 기준표에는 함정이 있다. 「n분 동안 풀어 보고 안 되면 풀이를 본다」가 실제로는 「n분 동안 푸는 척하다가 풀이를 본다」가 되기 쉽다. 어차피 곧 풀이를 볼 테니 흔한 접근 몇 개를 건드려 볼 뿐 문제에 온전히 몰두하지 않는다. 겉으로는 매일 꾸준히 연습하는 것과 구별되지 않아서 남도, 나 자신도 알아채기 어렵다. 실력이 늘지 않는 가장 큰 원인이 이런 자기기만(self-deception)인 경우가 많다.

좋은 연습법은 자기를 속일 수 없게 만드는 합리적인 방법이면 무엇이든 된다. 문제 자체에 대한 흥미가 깊으면 거의 어떤 방법도 이 조건을 만족하고, 흥미 없이 취업 같은 외부 동기만 있으면 거의 어떤 방법도 만족하지 못한다. 풀이를 보는 것 자체가 나쁜 것은 아니다. 다만 한동안 풀이 없이 끝까지 풀어 보면 아이디어를 떠올리는 일이 생각보다 가능하다는 것을 알게 된다.

목표 난이도는 회사마다 다르다. 대체로 대형 IT 기업은 프로그래머스 3레벨, 대기업 SI는 2레벨 수준을 기준으로 잡는다. 연습 사이트는 국내 기업 대비로 백준·프로그래머스, 삼성 대비로 SW Expert Academy, 해외 기업 대비로 LeetCode·Codeforces가 대표적이다.

코딩 테스트는 입구일 뿐이다. 프로젝트와 CS 기초 공부를 함께 가져간다.

반례 찾기: 랜덤 비교 테스트

예제도 통과하고 알려진 반례도 통과하는데 틀렸다면, 작은 입력을 무작위로 만들어 확실히 맞는 풀이와 결과를 비교한다. 스트레스 테스트(stress test)라고도 부른다.

from random import randint
 
def gen():
    k = randint(1, 5)
    return [randint(1, 20) for _ in range(k)], randint(1, 10)
 
for _ in range(10_000):                 # 재귀 대신 반복문: 깊이 제한에 걸리지 않는다
    lines, n = gen()
    expected, got = brute(lines, n), solve(lines, n)
    if expected != got:
        print(lines, n, "정답:", expected, "내 답:", got)
        break

• 반례가 나오면 그 입력을 고정해 두고 디버깅한다. 이분 탐색의 경계(> vs >=, 시작값 0 vs 1), 0으로 나누기, 정수 오버플로 같은 실수가 주로 걸린다.
• C·C++ 풀이도 같은 방식으로 비교할 수 있다. 셸 스크립트로 생성기·두 실행 파일을 돌려 출력 파일을 diff하면 언어와 무관하게 쓸 수 있다.
• 시간 초과는 이 방법으로 못 찾는다. 최대 크기 입력을 따로 만들어 실행 시간을 잰다.

입력 크기로 풀이 방향 정하기

문제를 읽으면 먼저 N의 범위를 보고 허용되는 시간 복잡도를 정한다. 1초에 C/C++은 약 10⁸번, 파이썬은 약 10⁷번의 단순 연산을 한다고 어림잡는다(경험칙).

자주 하는 선택

• 최단 거리 / 최소 횟수, 가중치 없음 → BFS
• 최단 거리, 가중치 있음(음수 없음) → 다익스트라
• 모든 경우를 봐야 함 → DFS / 백트래킹, 경우의 수부터 계산
• 최적값 + 같은 하위 문제가 반복 → DP
• 정렬 후 매 순간 최선의 선택이 정당함 → 그리디
• 정렬된 데이터에서 찾기, "최댓값/최솟값을 구하라" → 이분 탐색, 파라메트릭 서치
• 구간 합 쿼리가 많음 → 누적 합
• 조회가 느림 → 해시 맵. 면접 문제에서 가장 자주 쓰는 자료구조다(해시 테이블)
• 개체 사이의 관계로 주어진 데이터 → 그래프로 모델링(그래프). 선후 관계면 위상 정렬(위상 정렬)
• 괄호·수식처럼 중첩된 문자열 파싱 → 스택
• 우선순위에 따른 스케줄링, 상위·하위 K개, 중앙값 → 힙
• 문자열 집합의 접두사 검색 → 트라이(기초 자료구조)
• 연속 구간, 정렬된 배열의 쌍 → 투 포인터·슬라이딩 윈도우(투 포인터와 슬라이딩 윈도우), 뒤에서부터 순회
• 거듭제곱·제곱근·나눗셈을 O(n)보다 빠르게 → 지수를 반씩 줄이는 반복 제곱, 답을 반씩 좁히는 이분 탐색
• 같은 함수가 여러 번 호출됨(서버 API 등) → 입력을 한 번 전처리(정렬, 해시, 트라이, 접두사 합)해 두고 호출마다 재사용
• 연산마다 O(1)이 필요함 → 자료구조를 조합한다. LRU 캐시는 해시 맵 + 이중 연결 리스트로 조회·갱신이 모두 O(1)이다

놓치기 쉬운 경계 사례

정답 코드가 틀리는 입력은 대개 정해져 있다. 입력 유형을 보고 아래 경우를 TC에 넣는다.

고정 폭 정수 언어(C·C++·Java)에서는 오버플로를 처리하거나 적어도 가능성을 언급한다. 정수 문자열·리스트를 이어 붙이는 코드는 타입이 섞이지 않았는지도 본다.

막혔을 때 바꿔 보는 관점

풀이가 떠오르지 않으면 문제를 다른 모양으로 바꿔 본다.

풀이 최적화: 더 빠르게, 더 작게

동작하는 풀이를 찾은 뒤에는 「더 나은 방법이 있나」를 따진다. 면접관이 「더 잘할 수 있을까요?」라고 묻는 지점이다.

이론상 최선 복잡도(BTTC)부터 정한다

이론상 최선 시간 복잡도(Best Theoretical Time Complexity, BTTC)는 어떤 풀이로도 넘을 수 없는 하한이다. 대개 「입력을 적어도 한 번은 봐야 한다」에서 나온다.

• 최적 풀이는 지금 풀이와 BTTC 사이에 있다. BTTC보다 빠른 풀이를 찾느라 시간을 쓰지 않는다. BTTC를 면접관에게 말하는 것도 좋은 신호다.
• 문제의 조건(정렬됨, 범위 제한)을 놓치면 BTTC를 잘못 잡는다.
• 이미 BTTC인데 더 최적화하라고 하면, 대개 같은 복잡도에서 일을 덜 하기(두 번 훑던 것을 한 번에)나 공간 줄이기를 묻는 것이다.

시간 줄이기

불필요한 작업의 흔한 모양은 다음과 같다.

• 중복 조건: not arr and len(arr) == 0, x < 5 and x < 10은 뒤 조건이 필요 없다.
• 조건 순서: or는 빠르거나 참일 가능성이 높은 쪽을, and는 거짓일 가능성이 높은 쪽을 앞에 둔다(단락 평가).
• 반복 호출 캐싱: 함수 안에서 바뀌지 않는 len(array) 같은 값은 변수에 한 번 담는다.
• 조기 종료: 답이 정해지면 바로 return한다. 긴장하면 가장 자주 잊는다.
• 반복문 안 작업 줄이기: 반복마다 같은 값을 다시 계산하지 않는다(루프 밖으로 꺼낸다).
• 지연 평가: 필요할 때까지 계산·초기화를 미룬다. 입력이 비었으면 해시 테이블도 만들지 않는다.

def contains_string(search_term, strings):
    if not strings:                       # 지연: 빈 입력이면 아무것도 계산하지 않는다
        return False
    target = search_term.lower()          # 반복문 밖으로: 매번 lower()하지 않는다
    for s in strings:
        if s.lower() == target:
            return True                   # 조기 종료
    return False

공간 줄이기

보통 시간이 공간보다 중요하다. 최적 시간에 도달한 뒤 추가 공간을 줄이라는 요청이 온다.

입력을 바꾸는 기법은 면접용이다. 실무에서 입력 변경은 코드를 읽고 유지하기 어렵게 만든다. 뒤에서 원래 입력이 필요하면 되돌릴 수 없게 망가뜨리지 않는다. 면접에서도 입력을 바꿔도 되는지 먼저 묻는다.

파이썬 실전 팁

import sys
from collections import deque
import heapq
 
input = sys.stdin.readline          # 입력이 많을 때 input()보다 훨씬 빠르다
sys.setrecursionlimit(10 ** 6)      # 재귀 DFS 사용 시 기본 한도(약 1000) 늘리기
 
n = int(input())
arr = list(map(int, input().split()))
s = input().rstrip()                # readline은 줄바꿈 문자를 포함하므로 제거

• 큐는 list.pop(0)(O(n)) 대신 deque.popleft()(O(1))
• 우선순위 큐는 heapq(최소 힙). 최대 힙은 음수로 넣기
• 원소 존재 여부를 자주 확인하면 리스트(O(n)) 대신 set/dict(평균 O(1))
• 순열·조합은 itertools의 permutations, combinations, product(중복 순열), combinations_with_replacement(중복 조합)
• 개수 세기는 collections.Counter, 정렬된 리스트의 위치 찾기는 bisect_left·bisect_right
• 실수 계산은 오차가 있다(0.3 + 0.6 == 0.8999999999999999). 비교는 abs(a - b) < 1e-9나 math.isclose로 하고, 가능하면 정수로 바꿔 계산한다.
• 2차원 리스트는 [[0] * m for _ in range(n)]으로 만든다. [[0] * m] * n은 같은 행을 공유하는 버그가 생긴다.
• 문자열을 반복해서 이어 붙일 때는 리스트에 모은 뒤 ''.join()
• 출력이 많으면 print('\n'.join(map(str, result)))로 한 번에 출력
• 리스트를 공백으로 구분해 한 줄에 출력할 때는 print(*arr). *는 iterable을 개별 인자로 풀어 넘기는 언패킹 연산자다. 딕셔너리는 **로 키워드 인자로 풀 수 있다('{y}-{m}'.format(**info)). 이때 이미 넘긴 인자와 같은 키가 겹치면 TypeError가 난다.

자바스크립트 실전 팁

// Node.js에서 표준 입력 전체 읽기
const input = require('fs').readFileSync(0, 'utf8').trim().split('\n')
const [n, m] = input[0].split(' ').map(Number)

핵심 정리

• 주석 설계 → TC 작성 → 구현 → 정리 순서로 푼다.
• N의 범위에서 허용 복잡도를 역산해 알고리즘을 고른다.
• 최적화는 이론상 최선 복잡도(BTTC)를 하한으로 잡고, 겹치는 계산 재사용·자료구조 교체·불필요한 작업 제거 순으로 본다.
• 막히면 30분·1시간·2시간 기준으로 풀이를 보고, 1주 뒤 다시 푼다. 다만 「푸는 척하다 풀이 보기」와 쉬운 문제만 고르기가 되지 않게, 때로는 풀이 없이 끝까지 푼다.
• sys.stdin.readline, deque, heapq, setrecursionlimit은 기본 장비다.

관련 노트: 빅오 표기법, 기술 면접 준비, 프론트엔드 면접 유형과 준비법, 투 포인터와 슬라이딩 윈도우, BFS, 다익스트라, 동적 계획법, 그리디, 이분 탐색, 접두사 합, 면접 잘 보는 법, 초보 웹 개발자의 공부 방향과 차별화, KMP 문자열 검색 알고리즘, 컴퓨팅 사고와 개발 실력 늘리는 법