알고리즘 수학 시작

시작하기 전에

이 글을 처음 읽으시려는 분에게 제가 가장 먼저 하고 싶은 말은 "겁먹지 않아도 된다"는 것입니다. 이번 글에서는 앞으로 올라 올 관련 글을 어떻게 읽으면 좋을지, 코딩테스트에서 수학이 왜 필요한지, 그리고 앞으로 계속 등장할 비유와 도구들을 미리 살펴봅니다. 준비운동이라 생각하고 편하게 읽어주세요.

수학을 못해도 괜찮은 이유

"저 수포자예요." 코딩테스트를 준비하는 분들과 이야기를 나누다 보면 정말 자주 듣는 말입니다. 고등학교 수학, 심지어 중학교 수학도 가물가물한데 알고리즘 책을 펼치면 시그마와 그리스 문자가 쏟아지니 시작도 하기 전에 책을 덮게 되죠. 그런데 안심하셔도 됩니다. 이 글은 여러분에게 수학 공식을 외우게 하려는 글이 아닙니다. 이 글이 기르고자 하는 것은 딱 세 가지 "감각"입니다. 몇 가지 경우가 있는지 세는 감각, 큰 문제를 작은 문제로 쪼개서 보는 감각, 그리고 내가 짠 코드가 시간 안에 끝날지 가늠하는 감각. 이 세 가지 감각만 몸에 붙으면, 처음 보는 문제 앞에서도 "아, 이건 저번에 본 그 패턴이랑 비슷하네"라는 실마리를 잡을 수 있습니다. 코딩테스트에서 필요한 것은 증명이 아니라 바로 이 실마리입니다.

 

그래서 이 글에서는 공식을 먼저 던지지 않습니다. 대신 여러분이 일상에서 이미 겪어본 상황 — 도서관에서 책을 찾는 일, 러시아 인형을 하나씩 여는 일, 지갑 속 동전으로 거스름돈을 맞추는 일 — 에서 출발해서, 그 익숙한 감각을 슬쩍 수식으로, 그다음 파이썬 코드로 옮겨갑니다. 처음에는 그림과 비유로 "아하, 이런 느낌이구나"를 느끼고, 그다음에 그 느낌에 이름표(수식)를 붙이고, 마지막에 그 이름표를 실제로 동작하는 코드로 확인하는 순서입니다. 순서를 거꾸로, 즉 수식부터 외우려고 하면 힘들지만, 비유에서 시작하면 훨씬 자연스럽게 이해가 됩니다. 글의 공통된 순서는 이렇습니다.

1. 도입 — 코딩테스트에서 실제로 마주칠 법한 문제 상황으로 시작합니다.
2. 핵심 개념 — 이번 글에서 배울 개념을 한두 문장으로 정의합니다.
3. 비유로 이해하기 — 일상적인 비유로 개념의 "느낌"을 잡습니다.
4. 그림 — 비유를 시각적으로 한 번 더 정리합니다.
5. 수식으로 표현하기 — 비유를 점화식이나 수식, 의사코드로 옮깁니다.
6. Colab 코드로 확인하기 — 실제로 실행되는 파이썬 코드로 개념을 확인합니다.
7. 틀리기 쉬운 포인트 — 초보자가 자주 하는 실수를 짚어줍니다.
8. 코딩테스트에 연결하기 — 이 개념이 실전 문제에서 어떻게 쓰이는지 보여줍니다.
9. 한 줄로 정리하면 / 연습문제 — 핵심을 다시 한번 각인시키고, 직접 풀어볼 문제를 제시합니다.

이 글을 읽는 가장 좋은 방법은 "코드를 눈으로만 읽지 않는 것"입니다. 각 글의 Colab 코드는 여러분이 직접 실행해보라고 넣어둔 것입니다. 코드를 실행해보고, 숫자를 바꿔보고, 심지어 일부러 코드를 망가뜨려보면서 "왜 이렇게 되지?"를 스스로 질문해보세요. 그 질문과 답을 스스로 만들어내는 과정이야말로 수학 감각이 자라는 순간입니다. 이 글의 목표는 여러분이 마지막 글을 읽을 때 "나도 알고리즘 문제를 겁내지 않고 실마리를 찾을 수 있다"고 느끼는 것입니다.

코딩테스트, 왜 수학을 알아야 할까? — 문법을 알아도 문제가 안 풀리는 이유

변수도 알고, 조건문도 알고, 반복문도 알고, 함수도 짤 줄 알고, 리스트도 다룰 줄 압니다. 그런데 막상 코딩테스트 문제를 펼치면 손이 멈춥니다. 이 경험, 정말 많은 분들이 겪습니다. 왜 그럴까요? 문법은 "글자를 쓰는 법"을 아는 것이고, 알고리즘 문제를 푸는 것은 "무엇을 써야 할지 아는 것"이기 때문입니다. 이 둘 사이에는 큰 간극이 있고, 그 간극을 메워주는 것이 바로 이 글에서 말하는 세 가지 수학 감각입니다.

 

첫 번째는 경우의 수를 세는 감각입니다. "N명 중에서 2명을 뽑는 방법은 몇 가지일까?", "이 순서로 나열하는 방법은 몇 가지일까?" 같은 질문에 답할 수 있어야, 완전 탐색으로 풀 수 있는 문제인지 아니면 다른 방법이 필요한 문제인지 판단할 수 있습니다. 경우의 수를 세지 못하면, 반복문을 몇 겹으로 돌려야 할지조차 감이 오지 않습니다.

 

두 번째는 규칙을 점화식으로 만드는 감각입니다. 큰 문제를 통째로 풀려고 하면 막막하지만, "이 문제는 한 단계 작은 문제의 답을 알면 쉽게 풀 수 있지 않을까?"라는 질문을 던질 줄 알면 재귀와 동적 계획법(DP: Dynamic Programming) 같은 강력한 도구를 쓸 수 있게 됩니다. 피보나치 수열, 계단 오르기, 배낭 문제 같은 단골 유형이 전부 이 감각 위에 서 있습니다.

 

세 번째는 얼마나 걸릴지 가늠하는 감각, 즉 시간복잡도 감각입니다. 이게 없으면 코드가 "논리적으로는 맞는데 시간 초과로 틀리는" 상황을 계속 만나게 됩니다. 예를 들어 백준이나 프로그래머스 문제에는 보통 "시간 제한 1초"라는 조건이 붙어 있습니다. 컴퓨터는 1초에 대략 1억(10^8) 번 정도의 단순 연산을 처리할 수 있다고 흔히 어림잡습니다. 그런데 데이터의 개수가 N = 100,000인 문제에서, 반복문을 무심코 3중으로 겹쳐서 N³ 번 연산을 하게 짜버리면 어떻게 될까요? 100,000의 세제곱은 1,000,000,000,000,000, 즉 10^15번의 연산입니다. 1초에 처리할 수 있는 연산의 1억 배에 가까운 양이니, 이 코드는 아무리 기다려도 끝나지 않고 "시간 초과(Time Limit Exceeded)"라는 채점 결과만 받게 됩니다. 문법적으로는 완벽하게 맞는 코드인데도 말이죠.

 

이 세 가지 감각이 없으면 어떤 일이 벌어질까요? 문제를 읽고 나서 "일단 되는대로 이중 반복문을 돌려보자"는 식으로 접근하게 됩니다. 운이 좋으면 통과하지만, N이 조금만 커져도 시간 초과를 만나고, 왜 틀렸는지 이해하지 못한 채 답지를 찾아보는 악순환에 빠지기 쉽습니다. 반대로 세 가지 감각이 있으면, 문제를 읽자마자 "N이 10만이니까 O(N log N) 정도로 풀어야겠다", "이건 순서를 세는 문제니까 순열/조합으로 접근해야겠다", "부분 문제로 쪼개지는 구조니까 DP 테이블을 만들어야겠다"는 식으로 방향을 먼저 잡고 코드를 쓰게 됩니다. 이 글 이 세 가지 감각을 순서대로, 그리고 실제 코딩테스트 문제와 연결해서 길러드리는 여정입니다.

이 글에서 자주 쓰는 비유와 파이썬·Colab 준비물 미리 보기

이 글의 대표 비유 미리 보기

이 글에서는 같은 비유가 여러 글에 걸쳐 반복해서 등장합니다. 처음 만나는 낯선 개념도, 이미 익숙해진 비유에 빗대어 설명하면 훨씬 편하게 다가옵니다. 앞으로 자주 만나게 될 대표 비유들을 미리 표로 정리해봤습니다.

도서관에서 책 찾기	시간복잡도 (선형 탐색 vs 이진 탐색)	글 1
러시아 인형(마트료시카)	재귀 (큰 문제 안에 작은 문제가 들어있는 구조)	글 3
거스름돈 계산	그리디 알고리즘 (당장 최선의 선택을 반복하기)	글 6
책상 위 메모지	동적 계획법, DP (한 번 푼 답을 메모해두고 재사용하기)	글 5
지하철 노선도	그래프와 최단 경로	글 7
톱니바퀴 맞물림	최대공약수(GCD)와 최소공배수(LCM)	글 2

이 표는 지도라고 생각하시면 됩니다. 나중에 "어? 이 비유 어디서 봤더라?" 싶을 때 다시 돌아와서 확인해보세요.

파이썬 기초 문법 5분 복습

본격적으로 들어가기 전에, 이 글 전반에서 계속 쓰이는 다섯 가지 문법을 아주 짧게 복습하겠습니다. 이미 잘 아신다면 가볍게 훑고 넘어가도 좋습니다.

# 1. 변수 — 값에 이름을 붙여 저장합니다.
n = 5

# 2. 조건문 — 상황에 따라 다른 코드를 실행합니다.
if n % 2 == 0:
    print("짝수")
else:
    print("홀수")

# 3. 반복문 — 같은 동작을 여러 번 반복합니다.
total = 0
for i in range(1, n + 1):   # 1부터 n까지
    total += i
print(total)  # 1+2+3+4+5 = 15

# 4. 함수 — 반복해서 쓸 코드를 이름 붙여 묶어둡니다.
def add(a, b):
    return a + b

print(add(3, 4))  # 7

# 5. 리스트 — 여러 값을 순서대로 담는 상자입니다.
numbers = [3, 1, 4, 1, 5]
numbers.append(9)          # 값 추가
print(numbers)              # [3, 1, 4, 1, 5, 9]
print(numbers[0], numbers[-1])  # 첫 번째, 마지막 원소: 3 9

 

이 다섯 가지 — 변수, 조건문, 반복문, 함수, 리스트 — 만 있으면 이 글의 모든 코드를 따라가는 데 문법적으로는 전혀 문제가 없습니다. 앞으로 등장하는 어려움은 "새로운 문법"이 아니라 "이 문법들을 어떤 순서와 구조로 조합할 것인가"에서 옵니다. 그리고 그 조합의 감각을 길러주는 것이 바로 이 글의 역할입니다.

구글 Colab, 이렇게 열면 됩니다

이 글의 모든 코드는 여러분의 컴퓨터에 파이썬을 따로 설치하지 않아도 바로 실행해볼 수 있도록 구글 Colab 기준으로 안내합니다. 웹 브라우저에서 colab.research.google.com에 접속한 뒤, 구글 계정으로 로그인하고 좌측 상단의 "새 노트북" 버튼을 누르면 바로 코드를 입력할 수 있는 화면이 열립니다. 회색 상자로 표시된 "코드 셀"에 이 글의 파이썬 코드를 붙여넣고, 셀을 클릭한 상태에서 Shift + Enter를 누르면 코드가 즉시 실행되고 바로 아래에 결과가 출력됩니다. 눈으로 읽는 것과 직접 실행해서 숫자가 바뀌는 것을 보는 것은 이해의 깊이가 완전히 다릅니다.