Step 54. 알고리즘 훈련 1 — 문제를 코드로 번역하는 근육

Level 1 — 프로그래밍과 컴퓨터 내부 | 난이도 ★★☆☆☆ | 예상 소요 시간 4시간 (며칠에 나눠 합니다)

전제: Step 41~53 완료. 조건문, 반복문, 문자열 다루기를 압니다. 오늘은 백준(acmicpc.net) 가입이 필요합니다.

준비물: 인터넷 연결, 백준 계정(오늘 만듭니다), 풀이를 보관할 폴더 하나.
주의: 오늘 실습은 100% 안전합니다. 채점 사이트에 제출하는 코드는 내 컴퓨터에서만 계산하는 순수한 연습 코드입니다. 서두르지 마세요 — 이 챕터는 며칠에 나눠 하는 것이 정상입니다.

지금까지 우리는 도구를 배웠습니다. 변수, 반복문, 함수, 파일. 그런데 도구를 아는 것과 문제를 푸는 것은 다릅니다. 요리 도구를 다 안다고 요리가 되지 않듯이, 문법을 안다고 프로그램이 나오지 않습니다. 사이에는 "문제를 코드로 번역하는 근육"이 필요하고, 그 근육은 반복 훈련으로만 자랍니다.

오늘부터 그 훈련을 시작합니다. 왜 보안 공부에 이것이 필요할까요. CTF 문제는 결국 "제한된 시간 안에 문제를 분석하고 코드로 자동화하는" 시합입니다. 비밀번호 후보를 전부 대입하는 브루트포스의 시도 횟수를 계산하는 것도, 대용량 데이터에서 패턴을 찾는 것도, 전부 알고리즘 감각 위에 서 있습니다. 오늘은 평생 이어질 훈련의 첫날입니다.

1. 학습 목표

이 챕터를 끝내면 다음을 할 수 있습니다:

백준에 가입하고 문제를 읽고 코드를 제출해 채점받는 전체 순환을 돌린다
문제를 작게 나눠 코드로 옮기는 절차(한글 풀이 먼저)를 사용한다
입력이 커질 때 코드가 얼마나 느려지는지(시간 복잡도)를 실험으로 확인한다
채점 판정 여섯 종류를 읽고 다음 행동을 정한다
10문제 정답 판정을 받고 풀이 코드를 형식 있게 보관한다

2. 배경 지식 — 오늘의 도구와 개념

오늘의 도구 한눈에 보기

구분	내용
언어·환경	파이썬 3 + 브라우저(백준 채점). 로컬 실험에는 time 모듈 사용
오늘의 문법	`a, b = map(int, input().split())`, `input = sys.stdin.readline`(빠른 입력), `time.time()`(시간 재기)
필요한 개념	자동 채점 시스템, 표준 입력/출력 형식, 시간 복잡도(O(n), O(n²)), 경계값

2-1. 백준과 채점 시스템

백준(BOJ, acmicpc.net)은 한국에서 가장 널리 쓰이는 알고리즘 문제 풀이 사이트입니다. 문제를 고르고 코드를 제출하면, 서버가 미리 준비한 수많은 입력을 넣어 보고 전부 맞으면 "맞았습니다!!"(Accepted) 판정을 줍니다. "내 컴퓨터에서 되는 것"과 "어떤 입력에서도 되는 것"이 다르다는 것을 가르쳐 주는 묵직한 선생입니다.

2-2. 입력과 출력의 규칙

채점 프로그램은 우리 코드에게 표준 입력(input()으로 받는 그것)으로 문제의 데이터를 건네고, 표준 출력(print)으로 답을 받습니다. 그래서 문제마다 적힌 입력 형식과 출력 형식을 정확히 지키는 것이 절반입니다. "예제는 맞는데 틀렸습니다"의 대부분이 형식 문제입니다.

2-3. 시간 복잡도 — 느려지는 법칙의 감각

입력이 두 배가 될 때 내 코드는 몇 배 느려질까요. 반복문 하나면 대략 두 배, 이중 반복문이면 네 배. 이 관계를 시간 복잡도(time complexity)라고 하고 O(n), O(n²)처럼 적습니다. 지금은 기호보다 감각이 중요합니다 — "입력이 10만이면 이중 반복(10만 × 10만 = 100억 번)은 몇 분이 걸린다." 이 감각은 나중에 "이 암호를 무작정 대입하면 며칠 걸리는가"를 재는 자가 됩니다.

2-4. 문제 해결 절차

초보와 고수의 차이는 재능이 아니라 절차입니다. 고수는 이렇게 합니다: (가) 문제를 세 번 읽는다. (나) 예제 입력을 손으로 따라 해 본다. (다) 풀이를 한글로 적는다. (라) 그 한글을 코드로 옮긴다. (마) 예제로 확인하고 제출한다. (다)의 "한글로 적기"가 핵심입니다 — 코드로 바로 뛰어드는 것이 초보의 함정입니다.

3. 따라 하기

3-1. 가입과 첫 문제

브라우저에서 acmicpc.net에 접속해 가입합니다
검색창에 1000을 입력합니다 — "A+B" 문제입니다
문제를 읽습니다: 두 수를 입력받아 합을 출력하라

제출할 코드:

a, b = map(int, input().split())
print(a + b)

코드 읽는 법: input().split()은 입력 한 줄("3 5")을 공백으로 쪼개고, map(int, ...)가 둘을 정수로 바꾸며, a, b =가 나눠 담습니다. 채점 사이트의 표준 첫 문법입니다. 제출 버튼을 누르고 언어를 Python 3로 고른 뒤 제출하세요.

맞았습니다!!

(채점 결과는 백준 서버가 주는 것이라 출력 예시입니다. 여러분이 직접 받을 결과입니다.)

왜 하는가: 이 한 문제가 "가입-읽기-코딩-제출-판정" 전체 순환의 완주입니다. 이 순환을 열 번 돌리는 것이 이번 챕터의 목표입니다.

3-2. 흐름 익히기 — 입출력과 사칙연산 단계

문제집 메뉴에서 "단계별로 풀어보기" → "입출력과 사칙연산" 단계를 엽니다. 위에서부터 순서대로 풉니다. 2557(Hello World), 1000(A+B), 1001(A-B), 10998(A×B)…

10926(??!)은 문자열 형식 연습입니다. 입력이 joonas로 들어올 때:

name = input()
print(name + "??!")

joonas??!

(2026-09-09 로컬 실측. 입력을 직접 넣어 확인한 출력입니다.)

읽는 법: 간단해 보여도 "입력 형식 그대로, 출력 형식 정확히"의 훈련입니다. 공백 하나, 대소문자 하나가 정답과 오답을 가릅니다.

예측해 보기: 입력이 baekjoon이면 출력은? 손으로 적고 제출해 확인하세요.

3-3. 한글로 먼저 — 반복문 문제에 절차 적용

문제 2739(구구단)로 절차를 연습합니다. 문제: N을 입력받아 N단을 출력하라.

(다) 한글 풀이 먼저:

1. 숫자 N을 하나 입력받는다.
2. 1부터 9까지 숫자 i를 돌면서:
   "N * i = N곱하기i" 모양으로 출력한다.

(라) 코드로 옮기기:

n = int(input())
for i in range(1, 10):
    print(n, "*", i, "=", n * i)

입력 2를 넣은 출력 앞부분 (2026-09-09 실측):

2 * 1 = 2
2 * 2 = 4
2 * 3 = 6

읽는 법: 한글 풀이의 한 줄이 코드의 한 줄이 되었습니다. 이 대응이 보이면 절차가 몸에 붙기 시작한 것입니다. 출력 형식("=" 주위 공백 등)은 문제의 예제 출력과 똑같아야 합니다.

3-4. 빠른 입력 — 시간 초과 예방 주사

나중에 입력이 수만 줄인 문제를 만나면 input()이 느려서 시간 초과가 날 수 있습니다. 그때 쓰는 표준 기술을 미리 익혀 둡니다. 코드 맨 위에:

import sys
input = sys.stdin.readline

읽는 법: input()을 더 빠른 것으로 교체하는 주문입니다. 대신 입력 끝에 줄바꿈 문자가 붙어 오니, 숫자로 쓸 때는 int(input())처럼 감싸면(변환 과정에서 줄바꿈이 무시됩니다) 되고, 문자열이 필요할 때는 input().strip()으로 줄바꿈을 떼 줍니다.

왜 하는가: 지금 당장 필요하지 않아도, "시간 초과"라는 벽을 만났을 때 꺼낼 카드를 미리 손에 쥐어 두는 것입니다.

3-5. 느려지는 것 직접 보기 — 이중 반복 실험

백준이 아니라 내 컴퓨터에서 실험합니다. speed.py:

import time

for size in (1000, 2000, 4000, 8000):
    start = time.time()
    count = 0
    for i in range(size):
        for j in range(size):
            count += 1
    print(size, "→", round(time.time() - start, 3), "초")

1000 → 0.033 초
2000 → 0.132 초
4000 → 0.562 초
8000 → 2.243 초

(2026-09-09 실측. 숫자는 컴퓨터마다 다르지만 배율은 비슷하게 나옵니다.)

출력 읽는 법: 입력이 두 배(1000→2000→4000→8000)가 될 때 시간은 네 배씩 늘어납니다 — 실측에서도 0.033 → 0.132 → 0.562 → 2.243으로 정확히 네 배 법칙이 나왔습니다. 이것이 O(n²)를 몸으로 느끼는 모습입니다. 이 추세면 10만은 수십 분이 걸립니다.

왜 하는가: "이 방법으로는 시간 안에 못 푼다"를 코드 짜기 전에 아는 능력. 이것이 알고리즘 훈련의 진짜 수확이고, 브루트포스의 한계를 계산하는 눈이기도 합니다.

3-6. 디버깅 연습 — 틀린 코드 고치기

일부러 틀린 코드를 고쳐 봅시다. 문제: "1부터 N까지의 합을 출력하라."

n = int(input())
total = 0
for i in range(n):
    total += i
print(total)

이 코드는 틀렸습니다. range(n)은 0부터 n-1까지라서 n이 빠집니다. n=5를 넣은 실측 (2026-09-09):

버그 코드: 10      ← 정답은 15인데 10
수정 코드: 15      ← range(1, n + 1)로 고친 후

읽는 법: 고치는 법은 range(1, n + 1). 고치기 전에 n=3일 때 이 코드가 뭐라고 출력할지 손으로 계산해 보세요(0+1+2=3, 정답은 6). 그다음 실행해 대조합니다. "손 계산 → 실행 대조"가 알고리즘 디버깅의 표준 동작입니다.

왜 하는가: 채점은 전부 맞아야 통과라서, "거의 맞는 코드"와 "맞는 코드"를 가르는 감각이 필요합니다. 그 감각은 경계값(처음과 끝)을 손으로 대입해 보는 습관에서 자랍니다.

3-7. 기록하는 훈련 — 풀이 노트의 형식

오늘부터 풀이 파일에는 같은 형식으로 적습니다:

문제: 2739 구구단
접근: 1부터 9까지 돌며 "N * i = 곱" 출력
막힌 곳: 출력 형식의 공백 위치
배운 것: 예제 출력과 한 글자씩 비교하는 습관

읽는 법: 네 줄이면 충분합니다. "접근"은 한글 풀이의 한 줄 요약이고, "막힌 곳"과 "배운 것"이 복기의 심장입니다. 이 기록이 쌓이면 자신이 어떤 유형에서 막히는지가 데이터로 보입니다 — 형식 실수가 잦은 사람, 경계값에서 막히는 사람, 문제를 잘못 읽는 사람, 약점마다 훈련법이 다르기 때문입니다.

3-8. 채점 결과 읽는 법

제출하면 받게 되는 판정들의 뜻을 정리해 둡니다:

판정	뜻	다음 행동
맞았습니다!!	모든 시험 입력 통과	축하합니다, 다음 문제로
틀렸습니다	어떤 입력에서 답이 다름	경계값과 로직 의심
출력 형식이 잘못되었습니다	답은 비슷한데 형식이 다름	공백·줄바꿈·대소문자 비교
시간 초과	방법이 느림	빠른 입력, 반복 줄이기
런타임 에러	실행 중 죽음	인덱스·나눗셈·형변환 점검
컴파일 에러	문법 오류로 실행조차 안 됨	제출 전 로컬에서 한 번 실행

읽는 법: 이 여섯 가지를 알면 "왜 안 되지?"의 막막함이 "어느 종류의 문제지?"의 진단으로 바뀝니다. 판정은 벌이 아니라 진단서입니다. 맞으면 배운 것이고 틀리면 배울 것이니, 어느 쪽이든 이기는 게임입니다.

4. 미션과 연습문제

미션 — 10문제 완주와 풀이 보관소

며칠에 걸쳐 합니다. 서두르지 마세요:

백준 "단계별로 풀어보기"의 1단계(입출력과 사칙연산)를 전부 풉니다
2단계(조건문)와 3단계(반복문)에서 합쳐서 10문제 이상 "맞았습니다!!"를 받습니다
풀 때마다 세 가지를 파일로 보관합니다: 문제 번호, 풀이 코드, 한글 풀이
- 폴더 구조 예: baekjoon/1000.py, baekjoon/1000_풀이.txt
한 문제라도 "틀렸습니다"를 만나면 원인을 진단해 풀이 파일에 한 줄로 적습니다 (형식? 로직? 경계값?)
10문제를 채우면, 가장 오래 붙잡혔던 문제 하나를 골라 노트에 복기합니다: 무엇이 막혔고, 어떻게 뚫었는가

연습문제

문제 1. 채점 서버는 우리 코드와 어떻게 주고받나요? "예제는 맞는데 틀렸습니다"의 가장 흔한 두 원인은 무엇인가요?

문제 2. 입력이 1,000일 때 0.03초 걸리던 이중 반복 코드가 있습니다. 입력이 100,000이면 대략 얼마나 걸릴까요? 3-5절 실측의 배율을 근거로 계산해 보세요.

문제 3. 문제 해결 절차 다섯 단계를 순서대로 말하고, 그중 초보가 가장 건너뛰기 쉬운 단계는 무엇인가요?

문제 4. "시간 초과" 판정을 받았을 때 시도할 두 가지를 말해 보세요.

5. 모범 답안과 완료 기준

미션 모범 답안

미션은 코드 하나가 아니라 절차의 완주입니다. 합격한 보관소의 모습:

baekjoon/
 ├─ 1000.py
 ├─ 1000_풀이.txt     ← 접근: 두 수를 받아 합 출력. 막힌 곳: 없음
 ├─ 2557.py
 ├─ 2739.py
 ├─ 2739_풀이.txt     ← 막힌 곳: "=" 주위 공백. 배운 것: 예제와 한 글자씩 비교
 └─ ... (10문제 이상)

검증하는 법: ① 백준 프로필의 "맞은 문제"가 10 이상인가. ② 폴더에 코드와 한글 풀이가 짝으로 있는가. ③ 틀렸던 문제의 파일에 원인 진단 한 줄이 있는가. ④ 복기 노트가 있는가. 10문제를 채우는 데 사흘이 걸려도 정상입니다 — 이 훈련의 단위는 문제가 아니라 날짜입니다.

연습문제 해답

문제 1 해답. 서버는 표준 입력으로 테스트 데이터를 건네고 표준 출력으로 답을 받아, 준비된 정답과 비교합니다. "예제는 맞는데 틀렸습니다"의 흔한 원인은 ① 예제에 없는 경계값(0, 최댓값 등)에서 로직이 무너지는 경우, ② 출력 형식(공백, 줄바꿈)이 미세하게 다른 경우입니다.

문제 2 해답. 이중 반복은 입력이 두 배면 시간이 네 배입니다 (3-5절 실측: 0.033 → 0.132 → 0.562 → 2.243초, 매번 약 4배). 입력이 1,000 → 100,000은 100배이므로 시간은 100 × 100 = 10,000배, 즉 대략 0.03초 × 10,000 ≈ 300초(약 5분)입니다. 이런 입력에서는 이중 반복이 아니라 다른 풀이를 찾아야 합니다.

문제 3 해답. ① 문제를 세 번 읽기 → ② 예제를 손으로 따라 하기 → ③ 한글 풀이 적기 → ④ 코드로 옮기기 → ⑤ 예제 확인 후 제출. 초보가 가장 건너뛰기 쉬운 것은 ③입니다 — 코드로 바로 뛰어드는 것이 초보의 함정이고, 한글로 적는 삼십 초가 헤매는 삼십 분을 막습니다.

문제 4 해답. 첫째, 3-4절의 빠른 입력(import sys; input = sys.stdin.readline)으로 교체합니다. 둘째, 반복이 겹쳐 있지 않은지 봅니다 — "이중 반복을 한 번의 반복으로 줄일 수 없는가"가 시간 초과 문제의 표준 질문입니다. 입력 범위("N은 100만 이하" 같은 한 줄)가 풀이법을 결정하니 문제의 입력 범위를 다시 읽는 것도 잊지 마세요.

완료 기준 체크리스트

[ ] 백준에 가입하고 첫 문제(1000번)를 맞혔다
[ ] 가입-읽기-코딩-제출-판정의 전체 순환을 경험했다
[ ] 한글 풀이를 먼저 적고 코드로 옮기는 절차를 써 봤다
[ ] 이중 반복 실험으로 "두 배 → 네 배"를 눈으로 확인했다
[ ] 채점 판정 여섯 종류의 뜻과 다음 행동을 안다
[ ] 버그 코드(합 구하기)를 손 계산으로 진단하고 고쳤다
[ ] 미션: 10문제 정답과 풀이 보관소를 완성했다

6. 흔한 실수와 해결

벽 1. 예제는 맞는데 "틀렸습니다"

증상: 내 컴퓨터에서는 예제가 딱 맞는데 채점에서 틀립니다.
원인: 예제에 없는 입력(0, 음수, 최댓값 같은 경계값)에서 로직이 무너지거나, 출력 형식이 미세하게 다릅니다.
해결: 문제의 입력 범위를 다시 읽고, 가장 작은 입력과 가장 큰 입력을 손으로 넣어 보세요. 형식은 예제 출력과 내 출력을 한 글자씩 비교합니다.

벽 2. 시간 초과

증상: 코드는 맞는 것 같은데 "시간 초과" 판정.
원인: 입력이 큰 문제에서 느린 방법(이중 반복, 느린 input)을 썼습니다. 3-5절 실측처럼 입력 8,000의 이중 반복도 이미 2초를 넘습니다.
해결: 먼저 빠른 입력으로 바꾸고, 그래도 안 되면 이중 반복을 줄일 방법을 찾습니다. 입력 범위가 "100만 이하"라면 이중 반복은 애초에 버리라는 신호입니다.

벽 3. 런타임 에러 / 인덱스 에러

증상: 제출하면 "런타임 에러"가 납니다.
원인: 입력이 항상 예제처럼 오지 않습니다. 빈 줄, 예상보다 적은 수 등에서 리스트 범위를 넘습니다.
해결: 문제의 입력 형식을 다시 읽고 "입력이 최소일 때"를 가정해 보세요. 제출 전에 내 컴퓨터에서 예제 입력을 전부 돌려 보는 습관이 컴파일 에러와 런타임 에러를 함께 줄여 줍니다.

벽 4. range의 끝이 하나 모자라다

증상: 합계나 개수가 자꾸 하나씩 어긋납니다 (3-6절 실측: n=5에 10이 나와야 할 자리에 15가, 혹은 그 반대).
원인: range(n)은 0부터 n-1까지입니다. 끝을 포함하려면 range(1, n + 1).
해결: 반복 범위를 칠 때마다 "처음 값과 마지막 값이 뭐지?"를 소리 내어 물으세요. 경계값 하나를 손으로 대입해 보는 것이 이 유형의 백신입니다.

벽 5. 한 문제에 두 시간을 태운다

증상: 한 문제가 안 풀려서 하루가 가고 의욕이 꺾입니다.
원인: 초보 시절의 정상적인 과정이지만, 관리가 필요합니다.
해결: 30~40분 규칙을 권합니다. 그 시간 안에 진전이 없으면 문제를 접고 다른 문제를 풉니다. 며칠 뒤 다시 보면 풀리는 경우가 놀랍도록 많습니다. 훈련의 목적은 정답 수가 아니라 근육입니다.

7. 정리

오늘의 개념

개념	한 줄 설명
자동 채점	서버가 준비한 모든 입력으로 검사 — 하나라도 틀리면 오답
표준 입력/출력	채점이 주고받는 통로 — 형식 준수가 절반
시간 복잡도	입력이 커질 때 얼마나 느려지는가의 법칙
O(n²)	이중 반복 — 입력 두 배에 시간 네 배 (실측 확인)
경계값	처음과 끝의 입력 — 버그가 숨는 자리

오늘의 문법

문법	하는 일
`a, b = map(int, input().split())`	한 줄의 두 수를 정수로 받기
`import sys; input = sys.stdin.readline`	빠른 입력으로 교체
`time.time()`	코드의 실행 시간 재기
`range(1, n + 1)`	1부터 n까지 (끝 포함)

명령어보다 중요한 감각

문제문의 함정은 대개 세 군데에 있습니다. (가) 입력 범위 — "N은 100만 이하"라는 한 줄이 풀이법 전체를 결정합니다. (나) 출력 형식 — 한 줄에 하나씩인지 공백 구분인지. (다) 예외 조건 — "같은 경우 -1 출력" 같은 한 줄. 이 세 곳에 밑줄을 긋고 풀기 시작하세요. 밑줄 삼십 초가 오답 삼십 분을 막습니다.

두 가지를 더 기억해 두세요. 첫째, 오늘의 시간 복잡도 감각은 나중에 "이 암호를 무차별 대입하면 며칠 걸리는가"를 재는 자가 됩니다. 숫자 4자리는 1만 번이지만 영소문자 8자리는 약 2천억 번 — 공격의 시간을 재는 것은 방어의 기준을 정하는 일이기도 합니다. 둘째, 알고리즘 실력은 폭발이 아니라 적금입니다. 하루 1~2문제가 반 년이면 이백 문제입니다. 캘린더에 시작일을 동그라미 쳐 두세요. 백 일 뒤 그 동그라미를 보면 다른 사람이 되어 있을 것입니다.

전부 체크되면 Step 54 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.