코스

기초 다지기

입출력부터 완전탐색까지, 프로그래밍과 문제풀이의 토대를 다지는 코스.

Level 1 → Level 2 63 아이템 30 문제 33 강의 0 확인 문제
코스 진행도 0%
0 / 63 아이템 완료
01
Level 1 · Beginner

Beginner

기초 다지기 · Beginner 단계

0/48 완료
Lesson 변수와 자료형: 값을 담는 그릇 필수 8m 현재

변수란 무엇인가

변수(variable) 는 값을 담아 두는, 이름표가 붙은 상자입니다. 프로그램은
입력으로 받은 수, 중간 계산 결과, 최종 답 따위를 변수에 저장해 두었다가
필요할 때 꺼내 쓰고, 다시 새 값으로 갱신합니다. "무엇을 기억해야 하는가?"
라는 질문의 답이 곧 변수입니다.

int age = 17;      // 정수
double pi = 3.14;  // 실수
char grade = 'A';  // 문자 하나

age = 17       # 정수
pi = 3.14      # 실수
grade = 'A'    # 파이썬엔 char 타입이 없어 길이 1 문자열이다

C++은 변수를 만들 때 자료형을 반드시 적어야 하고(정적 타입), 파이썬은
대입하는 값에 따라 자료형이 자동으로 정해집니다(동적 타입).

1. 자주 쓰는 정수 자료형 (C++)

자료형 크기 대략적인 범위
int 4바이트 약 \(-2.1 \times 10^9 \sim 2.1 \times 10^9\)
long long 8바이트 약 \(-9.2 \times 10^{18} \sim 9.2 \times 10^{18}\)

규칙은 하나입니다. 계산 결과가 약 21억(\(2\,147\,483\,647\))을 넘을 수 있으면
long long. 두 수의 곱, \(1\)부터 \(N\)까지의 합 같은 값은 금방 int 범위를
넘깁니다.

long long a = 1000000, b = 1000000;
cout << a * b << '\n';   // 10^12 — long long이라 안전

파이썬의 정수(int)는 크기 제한이 없으므로 오버플로를 걱정할 필요가 없습니다.

2. 실수 자료형

소수를 담을 땐 C++에서 double을 씁니다(float보다 정밀해서 거의 항상
double 권장).

double x = 1.0 / 3.0;  // 0.333333...

실수는 정확히 저장되지 않을 수 있다는 점만 기억하세요. 0.1 + 0.2가
정확히 0.3이 아닌 것이 대표적입니다. 그래서 실수는 ==로 비교하지 않고
"차이가 아주 작으면 같다"로 판단합니다(다음 강에서 자세히).

3. 문자와 참/거짓

char c = 'Z';   // 작은따옴표 하나 — 문자 하나
bool flag = true;   // 참(true)/거짓(false)

C++에서 char는 사실 작은 정수라, 'A'는 아스키 코드 \(65\)로도 다뤄집니다.
'A' + 1 == 'B' 같은 계산이 되는 이유입니다.

4. 변수 이름 규칙

  • 알파벳·숫자·밑줄(_)로 짓되 숫자로 시작하면 안 됩니다(2a ✗, a2 ○).
  • 의미가 드러나는 이름을 쓰세요. int sum, cnt, mx;처럼 짧고 뜻이 통하게.
  • C++ 예약어(int, for, return …)는 변수 이름으로 못 씁니다.

정리

  • 변수 = 이름표 붙은 값 상자. "기억해야 할 값"마다 하나씩.
  • C++은 자료형을 직접 적고, 파이썬은 자동으로 정해진다.
  • 정수는 기본 int, 커질 것 같으면 long long.
  • 다음 강에서 이 자료형의 한계(오버플로) 를 깊게 다룹니다.
Lesson 정수 오버플로와 실수 오차: 자료형의 함정 선택 8m

변수가 담을 수 있는 한계

변수는 값을 담는 그릇이지만, 그릇마다 담을 수 있는 최대 크기가 정해져
있습니다. 이 한계를 넘는 순간 값이 망가지는 것을 오버플로(overflow) 라고
합니다. "식은 분명 맞는데 답이 이상하다"의 대부분은 이 함정입니다.

1. int의 진짜 한계

C++의 int는 32비트라서 약 21억(\(2\,147\,483\,647\)) 까지만 담깁니다.

int a = 2000000000;   // 20억
int b = a + a;        // 40억 → int 한계 초과!
cout << b << '\n';    // -294967296  (음수가 튀어나온다)

\(40\)억은 \(21\)억을 넘으므로 그릇이 넘쳐 음수로 돌아 버립니다.

2. 언제 long long이 필요한가

다음 신호가 보이면 망설이지 말고 long long.

상황 예시 값
두 수의 곱 \(10^5 \times 10^5 = 10^{10}\) (int 초과)
\(1\)부터 \(N\)까지의 합 \(N = 10^5\) 면 약 \(5 \times 10^9\)
거듭제곱 \(2^{40} \approx 10^{12}\)

곱셈이 특히 위험합니다. int끼리 곱하면 곱하는 순간 int로 계산되므로,
결과를 long long에 담아도 이미 늦습니다.

int x = 100000, y = 100000;
long long bad  = x * y;             // 먼저 int로 계산돼 이미 망가짐
long long good = (long long)x * y;  // 한쪽을 미리 long long으로 — 안전

3. 파이썬은 왜 안전한가

파이썬 정수엔 크기 제한이 없습니다.

x = 10 ** 100     # 1 뒤에 0이 100개 — 그냥 됩니다
print(x * x)

대신 큰 수 연산은 C++보다 느립니다. "오버플로 걱정 없음"이 파이썬의 장점입니다.

4. 실수의 함정

double은 소수를 담지만 정확하지 않습니다.

double d = 0.1 + 0.2;
cout << (d == 0.3) << '\n';   // 0 (false!)

그래서 실수는 절대 ==로 비교하지 않고, 오차 허용 비교를 씁니다.

if (abs(d - 0.3) < 1e-9) { /* 같다고 본다 */ }

if abs(d - 0.3) < 1e-9:
    pass  # 같다고 본다

또, 아주 큰 정수를 double에 담으면 정밀도가 부족해 값이 틀어집니다. 정수는
정수 자료형으로 다루세요.

5. 정수 나눗셈 착각

C++에서 int / int는 정수 나눗셈이라 소수점이 잘립니다.

int a = 7, b = 2;
cout << a / b << '\n';            // 3  (0.5가 버려짐)
cout << (double)a / b << '\n';    // 3.5  (한쪽을 double로)

print(7 / 2)    # 3.5  (파이썬 / 는 항상 실수 나눗셈)
print(7 // 2)   # 3    (// 가 정수 나눗셈)

평균 (a+b)/2가 정수로 잘리는 실수가 여기서 자주 납니다.

정리

  • 계산 중 값이 21억을 넘을 수 있으면 long long.
  • 곱셈은 곱하기 전에 (long long)으로 형변환.
  • 실수는 == 금지 → 오차 허용 비교. 큰 정수를 double에 담지 말 것.
  • C++의 int/int는 소수점이 잘린다.
Lesson 변수로 푸는 실전 패턴: swap·최댓값·누적 선택 8m

변수를 굴리는 네 가지 기본기

변수의 핵심은 "받아 두고, 꺼내 쓰고, 갱신한다"입니다. 실전에서 변수를 어떻게
굴리는지, 손에 익혀야 할 표준 패턴을 모았습니다.

1. 값 교환 (swap)

두 변수 값을 맞바꾸려면 임시 변수가 필요합니다.

int a = 3, b = 5;
int tmp = a;   // a를 잠깐 보관
a = b;         // a에 b를 넣고
b = tmp;       // 보관해 둔 옛 a를 b에
// 이제 a = 5, b = 3

a, b = 3, 5
a, b = b, a    # 파이썬은 한 줄로 교환

a = b; b = a;처럼 바로 하면 a가 먼저 덮여 둘 다 같아지니 주의. C++엔
swap(a, b); 함수도 있습니다.

2. 최댓값 / 최솟값 추적

여러 값 중 최대를 찾을 땐 "지금까지의 최댓값" 변수를 둡니다.

int best = -2000000000;         // 충분히 작은 값으로 시작
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    if (x > best) best = x;     // 더 크면 갱신
}
cout << best << '\n';

best = -10**9
for _ in range(n):
    x = int(input())
    best = max(best, x)
print(best)

시작값이 포인트입니다. 최댓값은 아주 작은 값, 최솟값은 아주 큰 값으로
시작하세요. 최댓값 변수를 0으로 시작하면 모든 값이 음수일 때 틀립니다.
확실히 하려면 첫 입력으로 초기화하는 방법도 있습니다.

int best; cin >> best;          // 첫 값으로 초기화 — 시작값 고민 불필요
for (int i = 1; i < n; i++) { int x; cin >> x; best = max(best, x); }

3. 누적(합·개수) 세기

합계·개수는 \(0\)에서 시작하는 변수에 차곡차곡 더합니다.

long long sum = 0;   // 합은 커질 수 있으니 long long
int cnt = 0;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    sum += x;
    if (x % 2 == 0) cnt++;      // 짝수 개수도 함께
}
cout << sum << ' ' << cnt << '\n';

total, cnt = 0, 0
for x in map(int, input().split()):
    total += x
    if x % 2 == 0:
        cnt += 1
print(total, cnt)

sum을 int로 두면 \(N\)이 클 때 오버플로. 합은 long long이 기본이라고
외워 두세요.

4. 카운터·플래그·상태 변수

  • 카운터 — 조건을 만족한 횟수를 세는 cnt.
  • 플래그(bool) — "찾았다/못 찾았다"를 기억. bool found = false; 로
    시작해 조건 만족 시 found = true;.
  • 직전 값 기억 — 수열에서 "이전보다 커졌는가"를 볼 때 prev 변수를 둡니다.
int prev = -2000000000, up = 0;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    if (x > prev) up++;   // 직전보다 증가한 횟수
    prev = x;             // 다음 비교를 위해 갱신
}

5. 자주 하는 실수

  • 초기화 누락 — C++에서 int sum;만 쓰면 쓰레기 값으로 시작. 꼭 = 0.
  • 잘못된 시작값 — 최댓값 변수를 0으로 시작(음수 데이터에서 오답).
  • 합 오버플로 — 누적 합 변수는 거의 항상 long long.
  • 갱신 위치 실수 — prev = x;를 조건 안에 넣어 버리는 실수. 매 바퀴 갱신할
    값은 조건 밖에 두세요.

정리

문제를 보면 "어떤 값을 기억해야 하는가?"를 먼저 찾으세요. 값마다 변수를
하나씩 만들고, 적절한 시작값으로 초기화한 뒤, 반복하며 갱신 — 이 흐름이 거의
모든 Bronze 문제의 뼈대입니다.

Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 입력 받기의 기본: cin과 input 필수 8m

입력이란

문제는 대부분 표준 입력(standard input) 으로 데이터를 줍니다. 우리는 그
값을 변수에 받아서 계산하고, 답을 출력합니다. 입력을 정확히 받는 것이 풀이의
첫 단추입니다.

1. 정수 하나 받기

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;        // 정수 하나를 n에 읽는다
    cout << n << '\n';
}

n = int(input())     # 한 줄을 읽어 정수로 변환
print(n)

cin >> 는 공백(스페이스, 탭, 줄바꿈)을 알아서 건너뛰고 다음 값을 읽습니다.
그래서 값들이 한 줄에 있든 여러 줄에 있든 cin >> a >> b; 로 똑같이 읽힙니다.

2. 한 줄에 여러 값

int a, b;
cin >> a >> b;       // "3 5" 든 "3\n5" 든 모두 읽힘
cout << a + b << '\n';

a, b = map(int, input().split())   # "3 5" → a=3, b=5
print(a + b)

파이썬의 input().split() 은 한 줄을 공백 기준으로 쪼갠 문자열 리스트를
주고, map(int, ...) 가 각각을 정수로 바꿉니다. 이 A+B류 입력이 가장 기본입니다.

3. 문자열·실수 받기

string s;  cin >> s;        // 공백 없는 단어 하나
double d;  cin >> d;        // 실수

s = input()          # 한 줄 전체(문자열)
d = float(input())   # 실수

주의: C++ cin >> s 는 공백에서 끊어 단어 하나만 읽습니다. 공백 포함 한
줄 전체가 필요하면 getline(cin, s); 를 씁니다(뒤에서 다룸).

4. 여러 줄 반복해서 받기

개수 \(N\)이 먼저 주어지고 \(N\)줄이 이어지는 형식이 흔합니다.

int n; cin >> n;
long long sum = 0;
for (int i = 0; i < n; i++) {
    int x; cin >> x;   // 반복 안에서 계속 읽는다
    sum += x;
}
cout << sum << '\n';

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

정리

  • cin >> 는 공백/줄바꿈을 자동으로 건너뛴다 → 형식에 관대.
  • 한 줄 여러 값: 파이썬은 map(int, input().split()).
  • \(N\)개 반복 입력은 for 안에서 계속 읽으면 된다.
  • 다음 강에서 개수를 안 알려 주는 EOF까지 읽기 를 다룹니다.
Lesson 까다로운 입력: EOF·한 줄 전체·가변 개수 선택 8m

개수를 안 알려 줄 때

"입력이 끝날 때까지 계속 읽어라"처럼 개수 \(N\)이 주어지지 않는 문제가 있습니다.
이때는 입력의 끝(EOF) 까지 읽어야 합니다.

1. EOF까지 읽기 — A+B 여러 줄

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    while (cin >> a >> b) {   // 더 읽을 게 없으면 false → 종료
        cout << a + b << '\n';
    }
}

cin >> a >> b 는 읽기에 성공하면 참, EOF에 닿으면 거짓이 됩니다. 그래서
while (cin >> ...) 가 EOF 처리의 표준입니다.

import sys
for line in sys.stdin:          # 각 줄을 EOF까지
    line = line.strip()
    if not line:
        continue
    a, b = map(int, line.split())
    print(a + b)

파이썬은 for line in sys.stdin: 이 EOF까지 한 줄씩 돌려줍니다.

2. 특정 값이 나오면 종료

"0이 입력되면 끝"처럼 보초값(sentinel) 으로 끝나는 형식입니다.

int x;
while (cin >> x) {
    if (x == 0) break;      // 종료 신호
    cout << x * x << '\n';
}

import sys
for line in sys.stdin:
    x = int(line)
    if x == 0:
        break
    print(x * x)

3. 공백 포함 한 줄 전체 — getline

cin >> s 는 공백에서 끊기므로, 문장처럼 공백이 든 한 줄은 getline으로 받습니다.

string line;
getline(cin, line);     // 줄바꿈 전까지 통째로
cout << line << '\n';

함정: 앞에서 cin >> n; 으로 숫자를 읽은 뒤 getline을 하면, 숫자 뒤에
남은 줄바꿈을 먼저 읽어 빈 줄이 잡힙니다. 사이에 줄바꿈을 버려 주세요.

int n; cin >> n;
cin.ignore();           // 남은 줄바꿈 하나를 버린다
string line;
getline(cin, line);     // 이제 제대로 한 줄이 읽힌다

n = int(input())
line = input()          # 파이썬 input()은 이런 문제가 없다

4. 한 줄에 개수도 모를 만큼 많은 수

한 줄에 여러 정수가 공백으로 나열되는데 개수를 모를 때:

int x;
vector<int> v;
while (cin >> x) v.push_back(x);   // 그냥 EOF까지 다 담는다

import sys
nums = list(map(int, sys.stdin.read().split()))

sys.stdin.read().split() 은 모든 공백·줄바꿈을 무시하고 토큰을 전부
모아 주므로, 줄 구분이 복잡할 때 아주 편합니다.

정리

  • 개수를 모르면 while (cin >> ...)(C++) / for line in sys.stdin(Python).
  • 보초값 종료는 읽은 뒤 break.
  • 공백 포함 한 줄은 getline — 단, 앞의 숫자 입력 뒤엔 cin.ignore().
  • 토큰이 어디에 있든 다 필요하면 sys.stdin.read().split().
Lesson 빠르고 안전한 입력, 그리고 흔한 실수 선택 8m

입력이 느려서 시간 초과?

입력 데이터가 수십만 줄이면, 입력 방식 자체가 느려 시간 초과가 날 수 있습니다.
경쟁 프로그래밍의 표준 가속법을 익혀 둡시다.

1. C++ 입력 가속 3종 세트

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);   // C 입출력과의 동기화 끄기
    cin.tie(nullptr);                   // cin/cout 묶음 풀기
    int n; cin >> n;
    while (n--) {
        int x; cin >> x;
        cout << x << '\n';              // endl 대신 '\n'
    }
}
  • sync_with_stdio(false) — C++ 스트림을 C의 scanf/printf와 분리해 빠르게.
  • cin.tie(nullptr) — 입력 전 출력 강제 비우기를 끔.
  • 출력엔 endl(매번 flush) 대신 '\n'.

이 세 줄이면 cin으로도 충분히 빠릅니다.

2. Python 입력 가속

파이썬의 input() 은 느립니다. 대량 입력엔 sys.stdin 을 쓰세요.

import sys
input = sys.stdin.readline      # input을 빠른 버전으로 교체

n = int(input())
for _ in range(n):
    x = int(input())
    # ...

한꺼번에 다 읽는 방식이 가장 빠릅니다.

import sys
data = sys.stdin.buffer.read().split()   # 모든 토큰을 bytes로
idx = 0
n = int(data[idx]); idx += 1
for _ in range(n):
    x = int(data[idx]); idx += 1

readline 은 끝에 줄바꿈(\n)이 붙으므로 int() 로 감쌀 땐 상관없지만,
문자열로 쓸 땐 .rstrip() 하세요.

3. 자주 하는 실수 모음

증상 원인 해결
값이 하나씩 밀림 개수 줄과 데이터 줄을 헷갈려 읽음 형식을 종이에 그려 보기
빈 줄이 읽힘 cin >> n 뒤 바로 getline 사이에 cin.ignore()
마지막 값에서 멈춤 EOF 처리 안 함 while (cin >> x)
파이썬 값 오류 input()에 줄바꿈/공백 .split() / int() 로 변환
시간 초과 대량 입력에 느린 방식 위의 가속 사용

4. 입력 형식을 읽는 법

문제의 "입력" 설명을 이렇게 해부하세요.

  1. 첫 줄에 무엇이 오는가? — 보통 개수 \(N\), 또는 여러 파라미터.
  2. 이어지는 줄의 형식은? — "각 줄에 정수 하나" / "한 줄에 \(N\)개".
  3. 끝을 어떻게 아는가? — 개수로? EOF로? 보초값으로?

이 셋을 답하면 입력 코드는 거의 자동으로 나옵니다.

// "첫 줄 N, 다음 줄에 N개의 정수" 형식의 표준 골격
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

정리

  • C++ 가속: sync_with_stdio(false), cin.tie(nullptr), '\n'.
  • Python 가속: sys.stdin.readline 또는 sys.stdin.buffer.read().split().
  • 입력 형식은 "첫 줄 / 이어지는 줄 / 끝나는 방법" 세 질문으로 해부.
  • 밀림·빈 줄·EOF 미처리가 3대 실수.
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 출력의 기본: cout과 print 필수 8m

출력이란

계산한 답을 표준 출력(standard output) 으로 내보내는 것이 출력입니다.
채점기는 우리 출력과 정답을 글자 단위로 비교하므로, 공백·줄바꿈 하나까지
문제가 요구한 형식과 정확히 맞아야 합니다.

1. 값 하나 출력

#include <bits/stdc++.h>
using namespace std;
int main() {
    cout << 42 << '\n';        // 42 출력 후 줄바꿈
    cout << "Hello" << '\n';   // 문자열
}

print(42)          # 자동으로 줄바꿈까지
print("Hello")

C++의 cout << 는 줄바꿈을 자동으로 넣지 않습니다. 필요하면 '\n' 을
직접 붙이세요. 파이썬 print 는 끝에 줄바꿈을 자동으로 붙입니다.

2. 여러 값을 한 줄에

int a = 3, b = 5;
cout << a << ' ' << b << '\n';   // "3 5"
cout << a + b << '\n';            // "8"

a, b = 3, 5
print(a, b)          # "3 5" — print는 값 사이에 공백을 자동으로
print(a + b)         # "8"

파이썬 print(a, b) 는 인자 사이에 공백을, 끝에 줄바꿈을 넣습니다.
C++에선 공백(' ')과 줄바꿈('\n')을 손으로 넣어 줘야 합니다.

3. 여러 줄 출력

for (int i = 1; i <= 5; i++)
    cout << i << '\n';        // 한 줄에 하나씩

for i in range(1, 6):
    print(i)

4. 줄바꿈 없이 이어 붙이기

for (int i = 1; i <= 5; i++)
    cout << i << ' ';         // "1 2 3 4 5 "
cout << '\n';

for i in range(1, 6):
    print(i, end=' ')         # 줄바꿈 대신 공백으로 끝맺음
print()                       # 마지막에 줄바꿈 하나

파이썬 print(..., end=' ') 는 기본 줄바꿈을 다른 문자로 바꿉니다.

정리

  • 채점은 글자 단위 비교 → 공백·줄바꿈까지 형식대로.
  • C++ cout 은 줄바꿈을 자동으로 안 넣는다('\n' 직접).
  • 파이썬 print 는 인자 사이 공백 + 끝 줄바꿈이 기본, sep/end로 조절.
Lesson 서식 있는 출력: 소수 자릿수·정렬·특수 형식 선택 8m

형식을 맞춰 출력하기

"소수점 아래 둘째 자리까지", "여섯 자리로 정렬해서" 같은 요구가 나오면
서식 출력 이 필요합니다.

1. 실수의 소수 자릿수

#include <bits/stdc++.h>
using namespace std;
int main() {
    double x = 3.14159265;
    cout << fixed << setprecision(2);   // 소수점 아래 2자리 고정
    cout << x << '\n';                  // 3.14
}

fixed 와 setprecision(k) 를 함께 쓰면 소수점 아래 \(k\)자리로 반올림해
출력합니다(한 번 설정하면 이후 출력에 계속 적용).

x = 3.14159265
print(f"{x:.2f}")        # 3.14
print(round(x, 2))       # 3.14 (단, round는 표시 목적엔 f-string이 안전)

파이썬은 f-string의 :.2f 가 가장 깔끔합니다.

2. 자릿수 맞춰 정렬 / 0 채우기

cout << setw(6) << 42 << '\n';        // "    42" (오른쪽 정렬, 폭 6)
cout << setfill('0') << setw(4) << 7; // "0007"
cout << '\n';

print(f"{42:6d}")     # "    42"
print(f"{7:04d}")     # "0007"

시:분:초를 03:07:09 처럼 두 자리로 찍는 문제에서 setfill('0')/:02d 가
유용합니다.

3. 큰 정수와 오버플로 재확인

출력 단계에서 자료형을 다시 점검하세요. 합·곱이 크면 long long 으로 계산하고
출력해야 값이 안 깨집니다.

long long ans = (long long)1000000 * 1000000;
cout << ans << '\n';      // 1000000000000

4. 실수 출력의 함정

  • 정수를 실수로 출력하면 1 이 1.00 처럼 나와 오답이 될 수 있습니다.
    정수 답은 정수형으로 출력하세요.
  • 반올림 방향은 언어/설정마다 미세하게 다를 수 있으니, 문제가 오차 허용치
    (\(10^{-6}\) 등)를 주면 그 안에 들어오게 자릿수를 넉넉히 잡습니다.
cout << fixed << setprecision(6) << ans << '\n';  // 오차 문제엔 넉넉히 6자리

정리

  • 실수 자릿수: C++ fixed+setprecision(k), Python f"{x:.kf}".
  • 폭·0 채움: setw/setfill('0'), Python f"{x:0wd}".
  • 정수 답을 실수로 찍지 말 것. 오차 허용 문제는 자릿수를 넉넉히.
Lesson 대량 출력 최적화와 출력 함정 총정리 선택 8m

출력이 느려서 시간 초과?

수십만 줄을 출력하면 출력 방식 때문에 시간 초과가 날 수 있습니다. 원인은
대개 매 줄마다 버퍼를 비우는(flush) 동작입니다.

1. endl은 느리다 → '\n'

for (int i = 0; i < 1000000; i++)
    cout << i << endl;    // 매번 flush → 느림!

endl 은 줄바꿈 + 버퍼 비우기를 매번 합니다. 대량 출력에선 치명적입니다.

for (int i = 0; i < 1000000; i++)
    cout << i << '\n';    // 그냥 줄바꿈 문자 → 빠름

여기에 입력 가속과 같은 두 줄을 더하면 완성입니다.

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

2. 아주 많은 출력은 한 번에 모아서

문자열 버퍼에 답을 모아 두었다가 마지막에 한 번에 출력하면 가장 빠릅니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    string out;
    for (int i = 1; i <= n; i++) {
        out += to_string(i);
        out += '\n';
    }
    cout << out;          // 한 방에 출력
}

import sys
n = int(sys.stdin.readline())
buf = []
for i in range(1, n + 1):
    buf.append(str(i))
sys.stdout.write('\n'.join(buf) + '\n')   # 한 번에 출력

파이썬은 print 를 반복 호출하는 것보다 '\n'.join(...) 후 한 번 출력이
훨씬 빠릅니다.

3. 출력 형식 함정 총정리

함정 설명 대책
끝 공백/줄바꿈 요구 안 한 공백을 붙임 형식 예시와 정확히 대조
대소문자 YES vs Yes 문제 표기 그대로
정수를 실수로 1 을 1.0 으로 정수는 정수형 출력
마지막 줄바꿈 누락/과다 보통 문제없지만 예민한 채점기 존재 예시와 동일하게
부호 있는 0 -0.00 출력 if (x == 0) x = 0; 로 정규화

특히 YES/NO, Yes/No, possible/impossible 같은 정확한 표기는 문제에
쓰인 그대로 복사하듯 출력해야 합니다.

4. 디버깅용 출력은 반드시 제거

중간 확인용으로 넣은 cout << "debug " << x; 를 지우지 않으면 출력 형식이
오염돼 오답입니다. 제출 전에 디버그 출력을 모두 지웠는지 확인하세요.

정리

  • 대량 출력엔 endl 금지 → '\n', 필요하면 버퍼에 모아 한 번에.
  • Python은 '\n'.join 후 sys.stdout.write 가 빠르다.
  • 대소문자·여분 공백·정수/실수 표기를 문제 예시와 글자 단위로 대조.
  • 디버그 출력은 제출 전 삭제.
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 조건문의 개념: 프로그램에 갈림길 만들기 필수 8m

조건문이란?

조건문(conditional statement) 은 "어떤 조건이 참일 때만 특정 코드를
실행"하도록 프로그램의 흐름을 갈라 주는 문장입니다. 위에서 아래로만 흐르던
프로그램에 갈림길을 만드는 것이죠.

예를 들어 "점수가 60점 이상이면 합격, 아니면 불합격"처럼, 상황에 따라 다른
동작을 해야 할 때 조건문을 씁니다.

1. if 문 — 참일 때만 실행

int score = 75;
if (score >= 60) {
    cout << "합격\n";
}

score = 75
if score >= 60:
    print("합격")

if (조건)의 조건이 참(true)이면 중괄호 { } 안(파이썬은 들여쓴 블록)을
실행하고, 거짓이면 통째로 건너뜁니다.

2. if - else — 참일 때와 거짓일 때

if (score >= 60) {
    cout << "합격\n";
} else {
    cout << "불합격\n";
}

if score >= 60:
    print("합격")
else:
    print("불합격")

else는 "위 조건이 거짓일 때"를 담당합니다. 둘 중 반드시 하나만 실행됩니다.

3. else if — 여러 갈래로 나누기

조건이 셋 이상이면 else if(파이썬은 elif)로 사다리처럼 잇습니다.

if (score >= 90)      cout << "A\n";
else if (score >= 80) cout << "B\n";
else if (score >= 60) cout << "C\n";
else                  cout << "F\n";

if score >= 90:
    print("A")
elif score >= 80:
    print("B")
elif score >= 60:
    print("C")
else:
    print("F")

위에서부터 검사해 가장 먼저 참이 되는 가지 하나만 실행하고 나머지는
건너뜁니다. 그래서 score = 95면 A만 출력됩니다.

4. 비교 연산자와 논리 연산자

조건을 만들 때 쓰는 도구들입니다.

종류 C++ 파이썬 뜻
같다 / 다르다 == != == != 값 비교
크기 비교 < <= > >= 같음 대소 비교
그리고 && and 둘 다 참
또는 \|\| or 하나라도 참
부정 ! not 참↔거짓 뒤집기 
if (10 <= x && x <= 20) cout << "범위 안\n";   // 10 이상 20 이하
if (x < 0 || x > 100)   cout << "범위 밖\n";

if 10 <= x <= 20:      # 파이썬은 이렇게 이어 쓸 수 있다
    print("범위 안")
if x < 0 or x > 100:
    print("범위 밖")

정리

  • 조건이 참일 때만 실행 → if, 거짓일 때 → else, 여러 갈래 → else if/elif.
  • 위에서부터 검사해 처음 참이 되는 가지 하나만 실행.
  • 조건은 비교 연산자와 논리 연산자(&&/and, ||/or)로 조합.
  • 다음 강의에서 흔한 실수와 실전 패턴을 다룹니다.
Lesson 조건문 실전과 함정 — 경곗값·논리 연산 선택 8m

조건문 실전과 함정

조건문은 문법이 쉬워 보이지만, 실수하기 딱 좋은 지점이 몇 군데 있습니다.
Bronze 문제에서 "논리는 맞는데 답이 틀리는" 대부분이 여기서 나옵니다.

1. = 와 == 혼동 (가장 흔한 실수)

==는 비교, =는 대입입니다.

int x = 5;
if (x = 3) { ... }   // 위험! x에 3을 "대입"하고, 3은 참이라 항상 실행
if (x == 3) { ... }  // 올바름 — x가 3인지 "비교"

C++에서 if (x = 3)은 문법 오류가 아니라 논리 오류라 잡기 어렵습니다.
파이썬은 if x = 3:을 아예 문법 오류로 막아 줘서 이 실수가 덜합니다.

2. 경곗값(등호) 실수

"이상/이하/초과/미만"을 정확히 옮겨야 합니다.

말 기호
N 이상 >= N
N 이하 <= N
N 초과 > N
N 미만 < N

"90점 이상이면 A"인데 > 90으로 쓰면 정확히 90점인 사람이 빠집니다.
경곗값(90, 0, 100 같은)으로 직접 손 계산해 확인하는 습관이 중요합니다.

3. 범위를 나눌 땐 겹치거나 빠뜨리지 않기

등급을 매길 때 구간이 빈틈없이, 겹치지 않게 이어져야 합니다.
else if 사다리는 "이전 조건이 거짓"임을 이미 보장하므로 위쪽 경계만
쓰면 됩니다.

if (x >= 90)      grade = 'A';
else if (x >= 80) grade = 'B';   // 여기 오면 x < 90은 이미 보장됨
else if (x >= 70) grade = 'C';
else              grade = 'F';

else if를 안 쓰고 독립된 if를 여러 개 쓰면, 여러 조건이 동시에 참이 되어
중복 실행되니 주의하세요.

4. 논리 연산자 우선순위와 괄호

&&(and)가 ||(or)보다 먼저 묶입니다. 헷갈리면 괄호로 명시하세요.

if ((a && b) || c) { ... }   // 의도를 괄호로 분명히

또 "x가 3 또는 5"를 if (x == 3 || 5)로 쓰면 안 됩니다. 5는 항상 참이라
언제나 실행돼 버립니다. 반드시 if (x == 3 || x == 5).

5. 삼항 연산자와 switch (짧게)

간단한 이지선다는 삼항 연산자로 한 줄에 씁니다.

int mx = (a > b) ? a : b;   // a가 크면 a, 아니면 b

mx = a if a > b else b

값이 딱 떨어지는 여러 경우는 C++에서 switch도 쓸 수 있습니다(break 필수).

switch (n) {
    case 1: cout << "one\n";   break;
    case 2: cout << "two\n";   break;
    default: cout << "other\n";
}

6. 대표 유형 — 세 수의 최댓값

조건문만으로 여러 값을 비교하는 연습입니다.

int a, b, c; cin >> a >> b >> c;
int mx = a;
if (b > mx) mx = b;
if (c > mx) mx = c;
cout << mx << '\n';

a, b, c = map(int, input().split())
print(max(a, b, c))   # 파이썬은 max로 간단히

정리

  • ==(비교)와 =(대입)을 절대 헷갈리지 말 것.
  • 이상/이하/초과/미만 → >= <= > < 정확히, 경곗값으로 손 검산.
  • 여러 갈래는 else if로 이어 중복·누락 방지.
  • x == 3 || x == 5처럼 비교는 항상 완전한 형태로.
  • 복잡한 논리는 괄호로 의도를 분명히.
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 반복문의 개념: 같은 일을 되풀이 필수 8m

반복문이란?

"1부터 100까지 더하라" 같은 일을 손으로 100줄 적을 수는 없습니다. 반복문은
같은 동작을 조건이 만족하는 동안 자동으로 되풀이하게 해 줍니다. 프로그래밍의
힘 대부분이 여기서 나옵니다.

1. for 문 — 횟수가 정해졌을 때

for (int i = 0; i < 5; i++) {
    cout << i << '\n';   // 0 1 2 3 4
}

for는 세 부분으로 이뤄집니다.

  1. 초기화 int i = 0 — 시작할 때 한 번
  2. 조건 i < 5 — 참인 동안 반복, 거짓이면 종료
  3. 증감 i++ — 한 바퀴 끝날 때마다 실행
for i in range(5):     # 0, 1, 2, 3, 4
    print(i)

파이썬은 range(시작, 끝, 간격)을 씁니다. 끝값은 포함하지 않습니다 —
range(5)는 0~4, range(1, n + 1)이라야 1~n입니다.

2. while 문 — 조건만 있을 때

횟수가 아니라 "어떤 조건일 동안" 반복할 땐 while이 자연스럽습니다.

int n; cin >> n;
while (n > 1) {
    n /= 2;          // n이 1이 될 때까지 반으로
    cout << n << '\n';
}

n = int(input())
while n > 1:
    n //= 2
    print(n)

for는 대부분 while로 바꿔 쓸 수 있고 그 반대도 됩니다. 횟수가 명확하면
for, 종료 조건만 명확하면 while 을 고르면 코드가 읽기 좋습니다.

3. 가장 흔한 패턴 — 누적

반복문 밖에 누적용 변수를 두고, 안에서 갱신합니다.

long long sum = 0;              // 합은 커질 수 있으니 long long
for (int i = 1; i <= n; i++)
    sum += i;                   // 1 + 2 + ... + n
cout << sum << '\n';

total = 0
for i in range(1, n + 1):
    total += i
print(total)

합·개수·최댓값 추적 모두 이 "밖에 변수, 안에서 갱신" 틀을 따릅니다.

4. break 와 continue

  • break — 반복을 즉시 끝낸다(반복문 전체 탈출).
  • continue — 이번 바퀴만 건너뛰고 다음 바퀴로.
for (int i = 1; i <= 100; i++) {
    if (i % 7 == 0) continue;   // 7의 배수는 건너뛴다
    if (i > 50) break;          // 50 넘으면 멈춘다
    cout << i << ' ';
}

for i in range(1, 101):
    if i % 7 == 0:
        continue
    if i > 50:
        break
    print(i, end=' ')

복잡도

N번 도는 반복문은 \(O(N)\)입니다. 반복문 안의 일이 무거우면 그만큼 곱해집니다.
Bronze에선 보통 \(O(N)\) 한두 번이면 충분합니다.

정리

  • 횟수가 정해지면 for, 조건만 있으면 while.
  • 파이썬 range의 끝값은 미포함.
  • 누적은 "밖에 변수, 안에서 갱신".
  • break는 즉시 종료, continue는 한 바퀴 건너뛰기.
Lesson 반복문 구현과 무한 루프 피하기 선택 8m

반복문 구현 레퍼런스와 무한 루프 피하기

반복문에서 가장 무서운 건 무한 루프와 off-by-one(하나 차이) 오류입니다.
구체적인 패턴과 함정을 코드로 정리합니다.

1. 기본 골격 (1부터 N까지)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << i * i << '\n';   // 1부터 n까지 제곱
    }
}

n = int(input())
for i in range(1, n + 1):        # 1 ~ n (n 포함하려면 n+1)
    print(i * i)

1 ~ n을 다 돌려면 C++은 i <= n, 파이썬은 range(1, n + 1)이라는 점을
반드시 기억하세요.

2. 입력 개수만큼 반복

int n; cin >> n;
long long sum = 0;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    sum += x;
}
cout << sum << '\n';

n = int(input())
total = 0
for _ in range(n):              # 반복 변수를 안 쓰면 _ 로
    total += int(input())
print(total)

3. "0이 들어올 때까지" — 개수를 모르는 입력

개수가 정해지지 않고 특정 값(예: 0)이 나오면 끝나는 입력은 while과 break
조합으로 처리합니다.

while (true) {
    int x; cin >> x;
    if (x == 0) break;   // 0이 들어오면 종료 — 탈출 조건 필수!
    cout << x * 2 << '\n';
}

while True:
    x = int(input())
    if x == 0:
        break
    print(x * 2)

EOF(입력 끝)까지 읽는 형태도 자주 나옵니다.

int x;
while (cin >> x) {        // 더 읽을 게 없으면 false → 종료
    cout << x << '\n';
}

import sys
for line in sys.stdin:   # EOF까지 한 줄씩
    print(line.strip())

4. 무한 루프의 원인과 예방

조건이 영원히 참이면 프로그램이 멈추지 않습니다(시간 초과).

  • while (true)를 쓸 땐 반드시 안에 break 조건이 있어야 합니다.
  • while (i < n)을 쓰면서 i를 안 늘리면 영원히 돕니다. 카운터 갱신을
    잊지 마세요.
int i = 0;
while (i < n) {
    // ... 처리 ...
    i++;                 // 이걸 빠뜨리면 무한 루프!
}

5. off-by-one 함정

<와 <= 하나 차이로 반복이 한 번 더/덜 돕니다.

for (int i = 0; i < n; i++)   // n번 반복 (0 .. n-1)
for (int i = 1; i <= n; i++)  // n번 반복 (1 .. n)
for (int i = 0; i <= n; i++)  // n+1번! (0 .. n) — 흔한 실수

의심되면 N=3으로 직접 한 바퀴씩 손으로 세어 보세요. i가 어떤 값들을
거치는지 적어 보면 금방 드러납니다.

6. 패턴 인식

문제에 "N개의 수", "1부터 N까지", "0이 입력될 때까지", "각 줄마다" 같은
말이 보이면 반복문이 중심입니다.

정리

반복문은 (1) 시작·끝·간격을 정확히, (2) 무한 루프 방지(탈출 조건/카운터 갱신),
(3) 누적 변수 초기화 — 이 셋을 챙기면 안정적입니다. 개수를 모르면 while+break
또는 while (cin >> x) / for line in sys.stdin으로 EOF까지 읽습니다.

Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 중첩 반복문의 개념: 격자와 별 찍기 필수 8m

중첩 반복문이란?

중첩 반복문(nested loop) 은 반복문 안에 또 반복문을 넣은 것입니다.
바깥 반복이 한 바퀴 돌 때마다 안쪽 반복이 처음부터 끝까지 전부 돕니다.

시계에 비유하면, 시침(바깥)이 한 칸 갈 때 분침(안쪽)은 60칸을 다 도는 것과
같습니다. 격자·표·좌표처럼 가로·세로 두 방향을 훑을 때 자연스럽게 등장합니다.

1. 기본 형태

for (int i = 0; i < 3; i++) {        // 바깥: 3번
    for (int j = 0; j < 4; j++) {    // 안쪽: 매번 4번
        cout << i << ',' << j << ' ';
    }
    cout << '\n';
}

for i in range(3):
    for j in range(4):
        print(f"{i},{j}", end=' ')
    print()

안쪽이 총 \(3 \times 4 = 12\)번 실행됩니다. 출력은 이렇게 됩니다.

0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3

바깥 i가 행(줄), 안쪽 j가 열(칸) 이라고 생각하면 격자 순회가 됩니다.

2. 곱셈표 — 대표 예제

for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++)
        cout << i * j << '\t';
    cout << '\n';
}

for i in range(1, 10):
    for j in range(1, 10):
        print(i * j, end='\t')
    print()

3. 별 찍기 (패턴 출력)

중첩 반복문 연습의 단골입니다. 안쪽 반복 횟수를 바깥 변수에 맞추는 것이
핵심입니다.

직각삼각형:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++)   // i번째 줄엔 별 i개
        cout << '*';
    cout << '\n';
}

for i in range(1, n + 1):
    print('*' * i)                 # 파이썬은 곱셈으로 간단히

n = 4면:

*
**
***
****

오른쪽 정렬 삼각형은 앞에 공백을 채웁니다.

for (int i = 1; i <= n; i++) {
    for (int j = 0; j < n - i; j++) cout << ' ';   // 공백 (n-i)개
    for (int j = 0; j < i; j++)     cout << '*';   // 별 i개
    cout << '\n';
}

4. 언제 쓰는가

  • 격자·표·행렬처럼 2차원 구조를 훑을 때.
  • 모든 쌍 (i, j) 를 검사할 때 (예: 두 수를 골라 합이 목표인지).
  • 어떤 값에 대해 다시 안쪽에서 무언가를 반복해야 할 때.

정리

  • 중첩 반복문 = 반복 안의 반복. 바깥 한 바퀴마다 안쪽이 전부 돈다.
  • 바깥=행, 안쪽=열로 보면 격자 순회.
  • 별 찍기는 "안쪽 횟수를 바깥 변수에 맞추기"가 핵심.
  • 다음 강의에서 복잡도와 시간 초과, break 탈출을 다룹니다.
Lesson 중첩 반복문의 복잡도와 탈출 함정 선택 8m

중첩 반복문의 복잡도와 함정

중첩 반복문은 강력하지만, 실행 횟수가 곱해져 폭발하기 때문에 시간 초과의
가장 흔한 원인입니다. 복잡도를 읽는 법과 실전 함정을 정리합니다.

1. 복잡도는 곱해진다

바깥이 \(N\)번, 안쪽이 \(M\)번이면 안쪽 몸통은 \(N \times M\)번 실행됩니다.

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        work();          // 총 N*N번 → O(N^2)
  • 2중 반복: \(O(N^2)\)
  • 3중 반복: \(O(N^3)\)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            work();      // O(N^3)

2. 시간 초과 판단 (아주 중요)

대회 채점기는 대략 초당 1억(10^8) 회 정도의 단순 연산을 처리합니다.
제한 시간 1~2초 기준으로 어림하면:

복잡도 안전한 N (대략)
\(O(N^2)\) \(N \le\) 약 \(10^4 \sim 3\times10^4\)
\(O(N^3)\) \(N \le\) 약 \(300 \sim 500\)
\(O(N^2)\) 인데 \(N = 10^5\) \(10^{10}\) → 시간 초과!

문제의 \(N\) 제한을 보고 "\(O(N^2)\)면 몇 번 도는가"를 먼저 계산하세요.
\(N = 10^5\)인데 이중 반복이 필요해 보이면, 정렬·해시·투 포인터 등으로
\(O(N \log N)\) 이하로 줄여야 한다는 신호입니다.

3. 안쪽 범위를 바깥에 맞춰 반만 돌기

"모든 쌍 (i, j), i < j"만 필요하면 안쪽을 j = i + 1부터 돌립니다.
실행 횟수가 절반(\(\tfrac{N(N-1)}{2}\))으로 줄지만 복잡도는 여전히 \(O(N^2)\)입니다.

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)   // 중복 쌍 (j, i) 방지
        if (a[i] + a[j] == target) cnt++;

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == target:
            cnt += 1

4. 이중 반복에서 한 번에 빠져나오기 (탈출)

break는 자기를 감싼 반복문 하나만 빠져나옵니다. 안쪽에서 break해도
바깥은 계속 돕니다. 이중 루프를 한 번에 탈출하는 세 가지 방법:

(a) 플래그 변수

bool found = false;
for (int i = 0; i < n && !found; i++)
    for (int j = 0; j < n; j++)
        if (grid[i][j] == target) { found = true; break; }

(b) 함수로 감싸 return (가장 깔끔)

pair<int,int> find_target() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == target) return {i, j};  // 즉시 이중 탈출
    return {-1, -1};
}

© goto (C++에서만, 최후의 수단)

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (grid[i][j] == target) goto done;
done:;

파이썬은 goto가 없으므로 (a) 플래그나 (b) 함수+return을 씁니다. else가
붙는 for(반복이 break 없이 끝났을 때 실행)를 활용하기도 합니다.

def find_target():
    for i in range(n):
        for j in range(n):
            if grid[i][j] == target:
                return (i, j)   # 즉시 전체 탈출
    return (-1, -1)

5. 흔한 실수

  • 안쪽 카운터 초기화 위치. 매 바깥 바퀴마다 새로 세야 하는 값은 바깥
    안·안쪽 밖    에서 0으로 초기화해야 합니다. 반복문 맨 밖에 두면 누적돼 버립니다.
for (int i = 0; i < n; i++) {
    int row_sum = 0;              // 매 행마다 새로!
    for (int j = 0; j < m; j++)
        row_sum += a[i][j];
    cout << row_sum << '\n';
}
  • 바깥·안쪽 변수 혼동. 두 반복 모두 i를 쓰면 안쪽이 바깥 i를 덮어씁니다.
    반드시 다른 이름(i, j, k)을 쓰세요.
  • 복잡도 오판. \(O(N^2)\)을 \(N = 10^5\)에 쓰면 시간 초과. 항상 N 제한과 함께
    실행 횟수를 어림하세요.

정리

  • 중첩 깊이만큼 복잡도가 곱해진다: 2중 \(O(N^2)\), 3중 \(O(N^3)\).
  • N 제한을 보고 초당 1억 기준으로 시간 초과를 미리 판단.
  • 쌍 검사에서 j = i + 1로 중복 방지.
  • 이중 루프 탈출은 플래그나 함수+return이 정석.
  • 행별 누적 변수는 바깥 바퀴마다 초기화.
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 시뮬레이션의 개념: 규칙 그대로 흉내 내기 필수 8m

시뮬레이션이란?

시뮬레이션(simulation) 은 문제에 적힌 규칙과 과정을 그대로 코드로 옮겨,
상황을 한 단계씩 흉내 내는 풀이법입니다. 똑똑한 알고리즘을 찾는 대신,
"문제가 시키는 대로 정확히 따라 하기"가 전부입니다.

"로봇이 명령대로 움직인다", "규칙에 따라 게임을 진행한다", "\(T\)초 동안 무슨
일이 벌어지는가" — 이런 문제가 전형적인 시뮬레이션입니다.

발상이 아니라 구현의 정확성이 승부처입니다. 그래서 시뮬레이션은 "쉬운데
자주 틀리는" 유형으로 악명 높습니다.

1. 언제 시뮬레이션인가

  • 문제에 동작 규칙이 단계별로 명시되어 있다("이렇게 움직이고, 그다음 …").
  • 최적화나 공식을 요구하지 않고 "그 결과 상태/값" 을 묻는다.
  • 입력 크기가 과정을 직접 돌려도 시간 안에 드는 정도다.

핵심 질문은 늘 같습니다: 총 단계 수 × 한 단계 비용이 \(10^8\) 안에 드는가?
\(T\)번의 단계, 각 단계마다 격자 \(N\times M\)을 훑으면 \(O(T \cdot N \cdot M)\)입니다.

2. 시뮬레이션의 기본 틀

거의 모든 시뮬레이션은 아래 골격입니다.

상태 초기화;
while (종료 조건이 아니다) {      // 또는 for (단계 = 0; 단계 < T; 단계++)
    현재 규칙에 따라 상태를 갱신;
    필요하면 결과를 기록;
}
답 출력;

상태(state) 를 무엇으로 잡느냐가 첫 단추입니다. 위치, 방향, 남은 시간,
격자판, 점수 등 "매 단계 바뀌는 것"을 변수/배열로 정확히 표현하세요.

3. 가장 단순한 예 — 규칙대로 값 갱신

"명령 문자열을 읽어 숫자를 조작"하는 간단한 시뮬레이션입니다.

string cmds; cin >> cmds;
long long value = 0;
for (char c : cmds) {
    if (c == '+') value++;
    else if (c == '-') value--;
    else if (c == 'D') value *= 2;   // 규칙을 그대로 옮긴다
}
cout << value << '\n';

cmds = input()
value = 0
for c in cmds:
    if c == '+':
        value += 1
    elif c == '-':
        value -= 1
    elif c == 'D':
        value *= 2
print(value)

포인트는 딱 하나 — 문제의 규칙을 한 줄도 빠뜨리거나 바꾸지 말 것. 조건의
우선순위, 경계값 처리까지 지문 그대로 옮기세요.

4. 시뮬레이션이 어려운 이유

알고리즘이 아니라 디테일에서 틀립니다.

  • 단계의 순서를 헷갈린다("이동 먼저? 충돌 검사 먼저?").
  • 경계(격자 밖, 0, 마지막 원소)를 빠뜨린다.
  • 여러 규칙의 우선순위를 잘못 적용한다.

그래서 시뮬레이션은 "지문을 규칙 목록으로 옮겨 적고, 그 순서대로 짜는" 습관이
정답률을 좌우합니다. 다음 강의에서 격자·방향 이동이라는 대표 도구를 익힙니다.

정리

  • 시뮬레이션 = 문제의 규칙·과정을 그대로 한 단계씩 흉내 내기.
  • 발상이 아니라 구현 정확성이 관건. 복잡도는 단계 수 × 한 단계 비용.
  • 상태를 먼저 정의하고, 지문의 규칙 순서를 그대로 코드로 옮겨라.
Lesson 격자와 방향: dx/dy와 회전 선택 8m

격자와 방향: dx/dy와 회전

시뮬레이션에서 가장 많이 나오는 무대는 2차원 격자이고, 가장 흔한 동작은
상하좌우 이동과 방향 전환입니다. 이 도구를 깔끔하게 다루는 표준 기법이
방향 배열(dx/dy) 입니다.

1. 방향 배열의 아이디어

"위/아래/왼쪽/오른쪽으로 한 칸"을 if 4개로 짜면 지저분합니다. 대신 각 방향의
행·열 변화량을 배열에 담아 두면, 이동이 nr = r + dx[d] 한 줄로 통일됩니다.

// 4방향: 위, 아래, 왼쪽, 오른쪽
int dx[4] = {-1, 1, 0, 0};   // 행(row) 변화
int dy[4] = {0, 0, -1, 1};   // 열(col) 변화

// (r, c)에서 d 방향으로 한 칸
int nr = r + dx[d];
int nc = c + dy[d];

행은 아래로 갈수록 증가함에 주의하세요(화면 좌표계). 위로 가면 r이
줄어듭니다. 8방향(대각선 포함)이면 배열을 8칸으로 늘립니다.

int dx8[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
int dy8[8] = {-1, 0, 1,-1, 1,-1, 0, 1};

2. 격자 안에서만 이동하기 (범위 검사)

새 좌표가 판을 벗어나지 않는지 반드시 확인합니다. 이 검사를 빠뜨리는 것이
런타임 에러/오답의 최대 원인입니다.

int n, m;                                  // n행 m열
bool inside(int r, int c) {
    return 0 <= r && r < n && 0 <= c && c < m;
}

def inside(r, c):
    return 0 <= r < n and 0 <= c < m

이동 예: 명령마다 한 칸씩, 벽 밖이면 제자리에 머무는 로봇.

int r = 0, c = 0;
for (char mv : commands) {
    int d = (mv=='U')?0 : (mv=='D')?1 : (mv=='L')?2 : 3;   // 위/아래/왼/오
    int nr = r + dx[d], nc = c + dy[d];
    if (inside(nr, nc)) { r = nr; c = nc; }                 // 밖이면 안 움직임
}
cout << r << ' ' << c << '\n';

3. 방향 전환(회전) — 시계/반시계

방향을 시계 방향 순서로 배열에 배치하면, 회전이 인덱스 덧셈이 됩니다.

// 북, 동, 남, 서 (시계 방향)
int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0,-1};

int dir = 0;                 // 현재 방향 (0=북)
dir = (dir + 1) % 4;         // 오른쪽(시계)으로 90도 회전 -> 북->동->남->서
dir = (dir + 3) % 4;         // 왼쪽(반시계)으로 90도 회전 (-1과 같음)

(dir + 3) % 4가 (dir - 1 + 4) % 4와 같다는 점을 기억하세요. 음수 모듈로
실수를 피하는 안전한 표현입니다. "앞으로 전진"은 위의 dx/dy[dir]로, "뒤로"는
(dir + 2) % 4 방향으로 처리합니다.

4. 대표 패턴 — 방향 전환하며 전진

"앞이 막히면 오른쪽으로 돌고, 아니면 전진"류(로봇 청소기, 뱀, 달팽이 배열 등)는
회전 + 전진의 조합입니다.

int r = sr, c = sc, dir = 0;
while (조건) {
    int nr = r + dx[dir], nc = c + dy[dir];
    if (inside(nr, nc) && !blocked[nr][nc]) {
        r = nr; c = nc;                 // 전진
    } else {
        dir = (dir + 1) % 4;            // 막히면 시계로 회전
    }
}

나선(달팽이) 채우기도 같은 골격입니다. 값을 1씩 채우다가 "판을 벗어나거나
이미 찬 칸"을 만나면 시계 방향으로 방향을 틀면 됩니다.

5. 파이썬에서의 격자 시뮬레이션

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
grid = [list(input()) for _ in range(n)]      # 문자 격자
r, c, d = 0, 0, 0
nr, nc = r + dx[d], c + dy[d]
if 0 <= nr < n and 0 <= nc < m:
    r, c = nr, nc

2차원 배열 초기화는 [[0]*m for _ in range(n)]로 하세요. [[0]*m]*n은 모든
행이 같은 리스트를 공유해 한 칸만 바꿔도 전 행이 바뀌는 악명 높은 버그입니다.

정리

  • 이동은 방향 배열 dx/dy로 통일 — nr=r+dx[d], 8방향은 8칸.
  • 이동 전 범위 검사 inside(nr,nc)는 필수.
  • 방향을 시계 순서로 두면 회전은 (dir+1)%4(오른쪽)·(dir+3)%4(왼쪽).
  • 파이썬 2차원 배열은 [[0]*m for _ in range(n)]로 만들 것.
Lesson 시뮬레이션 실전: 구현 실수를 줄이는 법 선택 8m

시뮬레이션 실전: 구현 실수를 줄이는 법

시뮬레이션은 알고리즘이 아니라 디테일에서 갈립니다. "분명 규칙대로 짰는데
틀린다"의 원인 대부분은 아래 함정들입니다. 하나씩 점검표로 만들어 두세요.

1. 단계 순서 함정

여러 일이 한 단계에 벌어질 때 순서를 지문과 정확히 맞춰야 합니다.

  • "모두 동시에 이동한 뒤 충돌 검사" vs "하나씩 이동하며 검사"는 완전히 다른
    결과를 냅니다. 동시 이동이면 새 상태를 별도 배열에 쓰고(더블 버퍼링),
    전부 계산한 뒤 한꺼번에 반영해야 합니다.
// 동시 갱신: 원본을 보고 새 판에 쓴다
vector<vector<int>> nxt(n, vector<int>(m, 0));
for (int r = 0; r < n; r++)
    for (int c = 0; c < m; c++)
        nxt[r][c] = 규칙(grid, r, c);   // 항상 원본 grid만 참조
grid = nxt;                              // 다 계산한 뒤 교체

제자리에서 바로 grid를 고치면, 같은 단계 안에서 방금 바꾼 값을 다시 읽어
버리는 버그가 납니다(생명 게임, 물 확산 등에서 치명적).

2. 경계·범위 함정

  • 격자 밖 접근: 이동 후 항상 inside()로 검사. 안 하면 런타임 에러 또는
    엉뚱한 메모리를 읽습니다.
  • 여유 테두리(padding): 경계 검사가 복잡하면 격자를 상하좌우로 한 칸씩
    키워 벽으로 감싸면 조건문이 단순해집니다.
  • 0-인덱스 vs 1-인덱스: 지문이 1부터 셀 때 배열은 0부터 — 한 칸 어긋나기
    쉽습니다. 하나로 통일하세요.

3. 종료 조건 함정

  • 무한 루프: while의 상태가 매 단계 실제로 변하는지 확인. 안 변하면 영원히
    돕니다.
  • 상태 순환: 유한한 상태가 반복되면 답이 주기적입니다. \(T\)가 아주 크면
    (\(10^9\) 등) 한 단계씩 돌 수 없으니, 처음 반복되는 상태를 찾아 주기(cycle)를
    검출    하고 \(T \bmod \text{주기}\)만 돌리세요.
map<상태, int> seen;                  // 상태 -> 처음 본 시각
for (int t = 0; t < T; t++) {
    if (seen.count(cur)) {
        int len = t - seen[cur];      // 주기 길이
        int rem = (T - t) % len;      // 남은 만큼만 더 진행
        while (rem--) cur = step(cur);
        break;
    }
    seen[cur] = t;
    cur = step(cur);
}

4. 복잡도 함정

  • 큰 \(T\)를 그대로 반복: \(T \le 10^6\)쯤이면 직접 돌려도 되지만, \(T\)가 \(10^9\)
    이상이면 위의 주기 검출이나 수식화가 필요합니다.
  • 매 단계 전체 훑기: \(O(T \cdot N \cdot M)\)이 \(10^8\)을 넘으면 시간 초과. 바뀐
    칸만 큐로 관리(변화 전파)하는 식으로 줄입니다.

5. 디버깅·검증 팁

  • 작은 예제를 손으로 단계별로 따라가며 코드 출력과 대조하세요.
  • 매 단계 상태를 출력해 눈으로 확인(제출 전 제거).
  • 규칙을 코드로 옮기기 전에 번호 매긴 규칙 목록으로 지문을 재정리하면
    순서·우선순위 실수가 크게 줄어듭니다.
  • 회전/방향 배열은 표를 그려 dx/dy가 실제 방향과 맞는지 한 번 검증하세요.

6. 대표 유형 정리

유형 핵심 도구
로봇/뱀/청소기 이동 dx/dy + 회전 (dir±1)%4
나선(달팽이) 채우기 방향 전환 + 범위 검사
생명 게임/확산 더블 버퍼링(동시 갱신)
큐가 큰 \(T\) 반복 주기 검출 후 \(T \bmod\) 주기
회전·뒤집기(격자 변환) 좌표 매핑 공식

정리

  • 동시 갱신은 더블 버퍼링, 경계는 범위 검사/패딩, 인덱스 기준을 통일.
  • 큰 \(T\)는 주기 검출로, 매 단계 전체 훑기는 변화 전파로 복잡도를 줄여라.
  • 지문을 번호 매긴 규칙으로 옮겨 적고 작은 예제로 손검증하는 습관이 정답률을 좌우한다.
Practice problem 나선형 채우기 선택 25m
R01562

나선형 채우기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 지우개 선택 25m
KOI00070

지우개

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze II 브론즈 II 지금 풀기
Lesson 입출력은 왜 느린가 · C++ 최적화 필수 8m

입출력이 시간 초과를 부른다

알고리즘은 맞는데 입출력이 느려서 시간 초과가 나는 경우가 있습니다. 입력이
수십만~수백만 줄로 많을 때, 한 줄씩 읽고 쓰는 비용이 쌓여 병목이 됩니다.

핵심 규칙: 입력 개수 \(N\)이 \(10^5\)을 넘어가면 빠른 입출력을 켠다.

1. C++ cin/cout이 느린 이유

cin/cout은 기본적으로 C의 scanf/printf와 동기화되어 있어 매 연산마다
버퍼를 맞추느라 느립니다. 이 동기화를 끄면 크게 빨라집니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);  // C stdio와 동기화 해제
    cin.tie(nullptr);                  // cin↔cout 자동 flush 끊기
    int n; cin >> n;
    while (n--) {
        int a, b; cin >> a >> b;
        cout << a + b << '\n';         // endl 대신 '\n'
    }
}
  • sync_with_stdio(false) — C 입출력과의 동기화 해제(가장 큰 효과).
  • cin.tie(nullptr) — 입력 전마다 출력을 flush 하던 것을 끊음.
  • 주의: 동기화를 끈 뒤엔 scanf/printf와 cin/cout을 섞어 쓰지 마세요.

2. endl vs '\n'

endl은 줄바꿈 + 매번 버퍼 flush 라서 출력이 많으면 크게 느립니다.
줄바꿈만 필요하면 항상 '\n'을 쓰세요.

cout << x << endl;   // 느림: 매번 flush
cout << x << '\n';   // 빠름: 버퍼에 모았다가 한꺼번에

3. scanf/printf 방식

sync_with_stdio(false) 가 꺼려지거나 형식 지정이 편하면 C 방식도 빠릅니다.

int n; scanf("%d", &n);
long long x; scanf("%lld", &x);   // long long은 %lld
printf("%d\n", ans);

형식 문자를 기억하세요: int → %d, long long → %lld,
double → %lf(scanf) / %f(printf), 문자열 → %s.

4. 얼마나 빨라지나

\(10^6\)줄 입력 기준, 아무 설정 없는 cin은 초 단위로 느려질 수 있지만
sync_with_stdio(false) + '\n'이면 보통 문제없이 통과합니다. 복잡도가 같아도
상수(입출력 비용) 때문에 통과 여부가 갈립니다.

정리

C++에서는 main 첫 줄에 ios_base::sync_with_stdio(false); cin.tie(nullptr);,
출력은 '\n' — 이 세 가지가 기본기입니다. 입력이 많다 싶으면 반사적으로
켜세요. 다음 강의에서 파이썬의 빠른 입출력을 다룹니다.

Lesson 파이썬 빠른 입출력 선택 8m

파이썬의 input()은 특히 느리다

파이썬 기본 input()은 한 줄 읽을 때마다 부가 처리를 해서, 입력이 많으면
매우 느립니다. sys 모듈로 바꾸면 몇 배 빨라집니다.

1. sys.stdin.readline로 교체

가장 간단한 처방은 input을 통째로 바꾸는 것입니다.

import sys
input = sys.stdin.readline   # 이후 input()이 빠르게 동작

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print(a + b)

주의: readline은 줄 끝의 개행 문자 '\n'까지 함께 읽습니다.

  • 정수/split()으로 쓸 땐 int()·split()이 공백을 알아서 버리므로 문제없음.
  • 문자열 한 줄을 통째로 쓸 땐 input().rstrip()으로 개행을 떼세요.
s = input().rstrip()   # 뒤 개행/공백 제거

2. 출력도 모아서 한 번에

print를 수십만 번 부르면 그 자체가 느립니다. 결과를 리스트에 모아
마지막에 한 번 출력하세요.

import sys
input = sys.stdin.readline

n = int(input())
out = []
for _ in range(n):
    x = int(input())
    out.append(str(x * 2))
sys.stdout.write('\n'.join(out) + '\n')   # 한 방에 출력

print('\n'.join(out)) 로 써도 됩니다. 핵심은 출력 호출 횟수를 줄이는 것.

3. 초대량 입력: 통째로 읽어 쪼개기

입력이 수백만 토큰이면, 한 줄씩도 부담됩니다. 전부 읽어 한꺼번에 split하는
패턴이 가장 빠릅니다.

import sys

data = sys.stdin.buffer.read().split()   # 모든 토큰을 bytes로 한 번에
idx = 0
n = int(data[idx]); idx += 1
res = []
for _ in range(n):
    a = int(data[idx]); b = int(data[idx + 1]); idx += 2
    res.append(str(a + b))
sys.stdout.write('\n'.join(res) + '\n')

int(b'12') 처럼 int는 bytes도 바로 숫자로 바꿔 주므로 .decode()가 필요 없습니다.
idx 포인터로 토큰을 순서대로 꺼내는 방식이라 줄 구분과 무관하게 동작합니다.

4. 흔한 실수

  • input = sys.stdin.readline 후 rstrip 누락 — 문자열 비교/길이가 개행 때문에 어긋남.
  • readline으로 빈 줄 판단 — 파일 끝(EOF)에선 '', 빈 줄은 '\n'. if not line: break로 EOF 처리.
  • 매 반복 print — 출력이 병목. 모아서 한 번에.

정리

파이썬은 input = sys.stdin.readline으로 입력을, '\n'.join으로 출력을 묶고,
초대량이면 sys.stdin.buffer.read().split()으로 통째 읽기 — 이 세 패턴이면
대부분의 시간 초과를 피할 수 있습니다.

Lesson 빠른 입출력 실전 패턴과 함정 선택 8m

실전에서 바로 쓰는 템플릿

문제 유형별로 빠른 입출력 템플릿을 손에 익혀 두면, 매번 고민 없이 찍어 낼 수
있습니다. 함정도 함께 정리합니다.

1. C++ 표준 템플릿

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long sum = 0;
    for (int x : a) sum += x;
    cout << sum << '\n';
}

문자열이 섞인 줄을 읽을 땐 getline을 쓰는데, cin >> x 다음에 getline을
쓰면 앞의 개행이 남아 빈 줄이 읽히는 함정이 있습니다.

int n; cin >> n;
cin.ignore();          // >> 뒤에 남은 개행을 버린다
string line;
getline(cin, line);    // 이제 한 줄이 제대로 읽힘

2. 파이썬 표준 템플릿

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(sum(a))

main()

여러 수가 여러 줄에 흩어져 있어도, 앞 강의의 sys.stdin.buffer.read().split()
포인터 방식이면 줄 구분과 상관없이 안전합니다.

3. EOF까지 반복 입력

"입력이 끝날 때까지" 형태(개수가 안 주어짐)의 처리.

int a, b;
while (cin >> a >> b) {     // 더 읽을 게 없으면 false → 종료
    cout << a + b << '\n';
}

import sys
for line in sys.stdin:         # 파일 끝까지 한 줄씩
    a, b = map(int, line.split())
    print(a + b)

4. 함정 총정리

함정 증상 해결
endl 남발(C++) 출력 많을 때 시간 초과 '\n' 사용
동기화 해제 후 scanf 혼용 입력 꼬임 한쪽으로 통일
>> 뒤 getline(C++) 빈 줄이 읽힘 cin.ignore()
readline rstrip 누락(파이썬) 문자열에 \n 포함 .rstrip()
매 반복 print(파이썬) 느림 모아서 '\n'.join
%lld 안 씀(C++) long long 출력 깨짐 형식 문자 확인

5. 언제 켤까

  • 입력 줄 수/토큰 수가 대략 \(10^5\) 이상이면 반사적으로 빠른 입출력.
  • 출력도 그만큼 많으면 출력 버퍼링(모아서 한 번에)을 함께.
  • 애초에 알고리즘 복잡도부터 맞아야 합니다 — 빠른 입출력은 상수를 줄일 뿐,
    \(O(N^2)\)을 \(O(N)\)으로 바꿔 주지는 않습니다.

정리

C++은 sync_with_stdio(false)+tie(nullptr)+'\n', 파이썬은 readline/buffer.read
+ 출력 모으기. getline 개행, rstrip, endl, %lld 네 가지 함정만 피하면
입출력 때문에 틀릴 일은 거의 없습니다.

Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem 알파카컵 1회: A - 알파카 선택 25m
A00001

알파카컵 1회: A - 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze V 브론즈 V 지금 풀기
Lesson 브루트포스의 개념: 다 해보기와 시간 판단 필수 8m

브루트포스란?

브루트포스(brute force, 완전 탐색) 는 "가능한 경우를 하나도 빠짐없이 다
해 보고 그중에서 답을 찾는" 가장 정직한 풀이법입니다. 똑똑한 수식이나 자료
구조 없이, 문제가 묻는 그대로 전부 시도합니다.

자물쇠 비밀번호를 모르면 000부터 999까지 전부 돌려 보는 것 — 그게
브루트포스입니다.

머리를 덜 쓰는 대신 컴퓨터의 속도로 밀어붙이는 방식이라, 경우의 수가
충분히 작을 때 가장 먼저 떠올려야 할 정석 접근입니다.

1. 언제 브루트포스를 쓰나

  • 답이 될 수 있는 후보의 개수가 유한하고 셀 수 있을 때.
  • 그 후보를 하나씩 만들어 검사하는 방법이 분명할 때.
  • 그리고 무엇보다 — 그 개수가 시간 안에 들어올 만큼 작을 때.

문제를 읽고 "경우의 수가 몇 개지?"를 먼저 세어 보세요. 그 수가 아래 기준을
넘지 않으면 브루트포스로 충분합니다.

2. 시간으로 가능 여부 판단하기 (가장 중요)

경쟁 프로그래밍에서 컴퓨터는 1초에 약 \(10^8\)번의 단순 연산을 처리한다고
잡습니다. 그래서 "전부 다 해 보면 몇 번 계산하나"를 어림하면 통과 여부를 미리
알 수 있습니다.

경우의 수 대략적인 판단 (1초 기준)
\(10^6\) 이하 아주 여유롭다
\(10^7 \sim 10^8\) 보통 통과 (상수 주의)
\(10^9\) 이상 시간 초과 위험 — 다른 방법 필요

예를 들어 \(N \le 1000\)인데 모든 쌍을 보는 이중 루프면 \(N^2 = 10^6\)이라
안전합니다. 반면 \(N \le 10^5\)에서 이중 루프면 \(10^{10}\)이라 절대 안 됩니다.

$$ \text{총 연산} \approx (\text{경우의 수}) \times (\text{한 경우 처리 비용}) $$

이 곱이 \(10^8\)을 넘으면 브루트포스를 접고 더 나은 알고리즘을 고민해야 합니다.

3. 가장 단순한 예 — 한 겹 루프

"1부터 \(N\)까지 중 조건을 만족하는 수를 세라"류는 한 겹 루프면 끝입니다.

int n; cin >> n;
int cnt = 0;
for (int x = 1; x <= n; x++)
    if (x % 3 == 0 || x % 5 == 0) cnt++;   // 3 또는 5의 배수 개수
cout << cnt << '\n';

n = int(input())
cnt = sum(1 for x in range(1, n + 1) if x % 3 == 0 or x % 5 == 0)
print(cnt)

복잡도는 \(O(N)\). \(N\)이 \(10^8\)쯤 되어도 아슬아슬하게 버팁니다.

4. 두 수 고르기 — 이중 루프

"두 수를 뽑아 합/차/곱이 어떤 조건을 만족하는 경우"는 모든 쌍을 봅니다.

int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

int cnt = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)      // j는 i보다 뒤 — 같은 쌍 두 번 방지
        if (a[i] + a[j] == 0) cnt++;
cout << cnt << '\n';

j를 i + 1부터 도는 것이 핵심입니다. \(\binom{N}{2}\)개의 서로 다른 쌍을
정확히 한 번씩만 봅니다. 복잡도 \(O(N^2)\).

정리

  • 브루트포스 = 가능한 경우를 전부 시도하는 정직한 완전 탐색.
  • 쓰기 전에 경우의 수 × 처리 비용을 어림해 \(10^8\)과 비교하라.
  • 한 겹 \(O(N)\), 두 값 쌍 \(O(N^2)\) — 다음 강의에서 이중·삼중 루프와 함정을 다룹니다.
Lesson 이중·삼중 루프로 경우 세기 선택 8m

이중·삼중 루프로 경우 세기

브루트포스의 몸통은 대개 여러 겹의 반복문입니다. "값 몇 개를 동시에
고른다"면 고르는 개수만큼 루프를 겹치면 됩니다. 이 강의에서는 그 패턴을
손에 익힙니다.

1. 삼중 루프 — 세 수 고르기

"세 수를 뽑아 합이 목표가 되는 경우"는 루프 세 겹입니다.

int n, target;
cin >> n >> target;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

int cnt = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (a[i] + a[j] + a[k] == target) cnt++;
cout << cnt << '\n';

n, target = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if a[i] + a[j] + a[k] == target:
                cnt += 1
print(cnt)

복잡도 \(O(N^3)\). \(N \le 100\)이면 \(10^6\)이라 여유, \(N \le 500\)이면 \(1.2\times10^8\)로
아슬아슬합니다. 겹이 늘수록 \(N\)의 상한이 급격히 작아진다는 감각을 가지세요.

루프 겹 수 복잡도 안전한 \(N\) 대략
1겹 \(O(N)\) \(10^8\)
2겹 \(O(N^2)\) \(10^4\)
3겹 \(O(N^3)\) \(\sim 500\)
4겹 \(O(N^4)\) \(\sim 100\)

2. 좌표·격자 위 완전 탐색

"모든 위치를 시작점으로 시도"하는 격자 문제도 루프를 겹칩니다.

int n, m;                    // n행 m열
cin >> n >> m;
vector<string> g(n);
for (auto& row : g) cin >> row;

int best = 0;
for (int r = 0; r < n; r++)
    for (int c = 0; c < m; c++)
        if (g[r][c] == '#') best++;   // 예: 벽 개수 세기
cout << best << '\n';

"모든 \(2\times2\) 정사각형을 확인" 같은 문제면 시작 좌표를 이중 루프로 훑고,
안에서 고정 크기 검사를 합니다. 시작점 \(O(NM)\) × 검사 비용이 총 복잡도입니다.

3. 최적값 추적하기

경우를 세는 대신 가장 좋은 경우를 찾을 때는, 후보를 모두 만들며 최적값을
갱신합니다.

int best = -2147483647;              // 최댓값 찾기: 아주 작게 시작
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        best = max(best, a[i] * a[j]);   // 두 수 곱의 최댓값
cout << best << '\n';

best = -10**18
for i in range(n):
    for j in range(i + 1, n):
        best = max(best, a[i] * a[j])
print(best)

시작값을 잘못 두는 실수가 흔합니다. 최댓값은 아주 작은 값, 최솟값은 아주
큰 값에서 출발하세요. 값이 음수일 수 있으면 0으로 시작하면 안 됩니다.

4. 조기 종료로 상수 줄이기

답을 하나만 찾으면 되는 문제는, 찾는 즉시 멈춰 시간을 아낍니다.

bool found = false;
for (int i = 0; i < n && !found; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] + a[j] == target) { found = true; break; }
cout << (found ? "YES" : "NO") << '\n';

복잡도의 상한(\(O(N^2)\))은 그대로지만, 평균적으로 훨씬 빨리 끝납니다. 다중
루프를 한 번에 빠져나오려면 플래그나 함수로 감싸 return하는 방법을 씁니다.

정리

  • 고르는 값의 개수만큼 루프를 겹친다. 겹마다 \(N\) 상한이 급락함을 기억.
  • 쌍/삼중은 인덱스를 i < j < k로 돌려 중복을 원천 차단.
  • 최적값은 극단값에서 시작해 갱신, 답 하나면 조기 종료.
Lesson 브루트포스의 함정과 최적화 연결 선택 8m

브루트포스의 함정과 변형

브루트포스는 단순해 보이지만 중복을 세거나, 복잡도를 잘못 재거나, 범위를
빠뜨리는 실수가 잦습니다. 실전에서 걸려 넘어지는 지점을 정리합니다.

1. 중복 카운트 함정

두 값을 고를 때 j를 0부터 돌면 같은 쌍을 두 번, 심지어 자기 자신과의
쌍까지 셉니다.

// 잘못된 예 — (i,j)와 (j,i)를 둘 다 세고, i==j도 셈
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (a[i] + a[j] == target) cnt++;

순서가 상관없는 "쌍"이라면 j = i + 1로 고쳐 서로 다른 쌍을 한 번씩만
세야 합니다. 순서가 의미 있는 "순서쌍"이라면 j != i만 걸러 전부 셉니다.
문제가 "쌍"인지 "순서쌍"인지 먼저 확정하세요.

2. 복잡도 오판 — "될 것 같은데 시간 초과"

가장 흔한 실패입니다. 한 경우를 처리하는 비용을 빠뜨리고 세면 실제보다
낙관하게 됩니다.

경우의 수 N^2 개, 각 경우마다 길이 N 문자열 비교(O(N))
→ 실제 복잡도는 O(N^2) 가 아니라 O(N^3)!

항상 \((\text{경우의 수}) \times (\text{한 경우 비용})\)으로 총합을 재세요. 안쪽에
숨은 반복(문자열 비교, vector 복사, set 삽입 등)이 상수가 아니라 \(N\)에
비례하는 경우가 함정입니다.

3. 경계·범위 실수

  • 오버플로: 브루트포스로 합·곱을 누적하면 값이 커집니다. 곱이 \(10^9\)을
    넘을 수 있으면 long long. 특히 int * int는 곱하기 전에 형변환하세요.
long long prod = (long long)a[i] * a[j];   // 먼저 int로 계산되지 않게
  • 빈 후보: 모든 값이 음수인데 best = 0으로 시작하면 답이 틀립니다.
    실제로 존재할 수 있는 값의 극단으로 초기화하세요.
  • 범위 포함/미포함: "1 이상 \(N\) 이하"인데 < n으로 돌아 마지막을 빠뜨리는
    off-by-one. 작은 예제로 손으로 세어 검증하세요.

4. 변형 — 부분집합·조합을 다뤄야 할 때

"몇 개를 고를지 정해져 있지 않다"면 단순 겹 루프로는 부족합니다. 이때는
부분집합 전체(\(2^N\)) 나 순열/조합을 열거해야 하며, 이는 다음 단원
(완전 탐색, 백트래킹)에서 다룹니다. 신호는 이렇습니다.

  • "부분집합 중 …" → 비트마스크 \(2^N\) 완전 탐색.
  • "순서대로 나열 / 줄 세우기" → 순열 \(N!\).
  • "\(k\)개를 고르는 조합" → 조합 \(\binom{N}{k}\).

\(N\)이 20 안팎이면 \(2^N \approx 10^6\)이라 여전히 브루트포스가 통합니다.

5. 브루트포스를 최적화로 연결하기

브루트포스가 시간 초과라면, 보통 다음 단계로 넘어가는 디딤돌로 씁니다.

  • 정렬 + 이분 탐색: "세 수의 합" \(O(N^3)\)을 두 수 고정 + 나머지 이분 탐색으로
    \(O(N^2 \log N)\).
  • 해시/집합으로 존재 확인: "두 수의 합" \(O(N^2)\)을 set으로 \(O(N)\).
  • 누적 합: 구간 합 반복 계산을 미리 계산해 \(O(1)\) 조회로.

먼저 맞는 브루트포스를 짜 두면, 그것이 정답 검증기(브루트포스 vs 최적화
비교 테스트)로도 쓰입니다.

정리

  • 쌍인지 순서쌍인지 확정해 중복 카운트를 막아라.
  • 복잡도는 경우의 수 × 한 경우 비용 — 숨은 내부 반복을 놓치지 마라.
  • 오버플로·초기값·off-by-one을 점검하고, 막히면 정렬·이분탐색·해시로 승격하라.
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem Debug 선택 25m
COCI00006

Debug

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
02
Level 2 · Solver

Solver

기초 다지기 · Solver 단계

0/15 완료
Lesson 완전 탐색: 부분집합·순열·조합 열거 필수 8m

완전 탐색: 모든 경우를 체계적으로 만들기

브루트포스가 "다 해 본다"는 정신이라면, 완전 탐색의 실전 기술은 경우를
빠짐없이, 겹치지 않게 만들어 내는 방법입니다. 대부분의 문제는 결국 다음
셋 중 하나로 귀결됩니다.

  • 부분집합(subset): 각 원소를 넣거나 뺀다 → 총 \(2^N\)가지.
  • 순열(permutation): \(N\)개를 줄 세운다 → 총 \(N!\)가지.
  • 조합(combination): \(N\)개 중 \(k\)개를 고른다 → 총 \(\binom{N}{k}\)가지.

1. 언제 완전 탐색이 통하는가

핵심은 다시 경우의 수입니다. 컴퓨터는 1초에 약 \(10^8\)번 연산하므로,
열거할 경우의 수가 이 선을 넘지 않아야 합니다.

형태 경우의 수 안전한 \(N\) 대략
부분집합 \(2^N\) 지수 \(N \le 20\sim22\)
순열 \(N!\) 계승 \(N \le 10\sim11\)
조합 \(\binom{N}{k}\) 다항~지수 \(\binom{N}{k}\)가 \(10^7\) 이하면 OK

$$ 2^{20} \approx 10^6, \quad 10! \approx 3.6\times10^6, \quad 13! \approx 6\times10^9 $$

즉 "\(N\)이 작다"(\(N \le 20\)쯤)는 완전 탐색을 쓰라는 강력한 신호입니다.

2. 부분집합 — 비트마스크

\(N\)개의 원소를 넣고/빼는 선택은 \(N\)비트 정수 하나로 표현할 수 있습니다.
정수 mask의 \(i\)번째 비트가 1이면 "\(i\)번 원소를 포함"입니다.

int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

int best = 0;
for (int mask = 0; mask < (1 << n); mask++) {   // 0 ~ 2^n - 1
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) sum += a[i];         // i번째 비트가 켜졌으면 포함
    best = max(best, sum);
}
cout << best << '\n';

n = int(input())
a = list(map(int, input().split()))
best = 0
for mask in range(1 << n):
    s = sum(a[i] for i in range(n) if mask & (1 << i))
    best = max(best, s)
print(best)

복잡도 \(O(2^N \cdot N)\). 바깥 루프가 모든 부분집합, 안쪽이 그 부분집합의 원소
확인입니다. 공집합(mask=0) 도 포함되니, 문제가 "공집합 제외"면 mask를
1부터 돌리세요.

3. 순열 — 모든 순서 나열

\(N\)개를 줄 세우는 모든 방법입니다. C++은 next_permutation 이 표준입니다.
반드시 정렬된 상태에서 시작해야 전체를 사전순으로 빠짐없이 만듭니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i + 1;     // 1..N, 이미 정렬됨
    do {
        for (int x : a) cout << x << ' ';
        cout << '\n';
    } while (next_permutation(a.begin(), a.end()));
}

from itertools import permutations
n = int(input())
for p in permutations(range(1, n + 1)):
    print(*p)

복잡도 \(O(N! \cdot N)\). next_permutation은 현재보다 사전순으로 바로 다음
순열을 만들고, 더 없으면 false를 반환하며 배열을 다시 오름차순으로
되돌립니다.

정리

  • 완전 탐색의 세 축: 부분집합 \(2^N\), 순열 \(N!\), 조합 \(\binom{N}{k}\).
  • 열거할 경우의 수를 \(10^8\)과 비교해 가능 여부를 판단(\(N \le 20\)이면 청신호).
  • 부분집합은 비트마스크, 순열은 next_permutation/permutations. 다음 강의에서
    조합과 재귀 열거를 다룹니다.
Lesson 조합 열거와 재귀 DFS 선택 8m

조합 열거와 재귀 DFS

앞 강의의 부분집합·순열에 이어, 조합과 이 모두를 통합하는 재귀 DFS
열거를 익힙니다. 라이브러리가 없거나 조건이 붙을 때 재귀가 만능 열쇠입니다.

1. 조합 — \(N\)개 중 \(k\)개 고르기

순서 없이 \(k\)개를 고르는 모든 방법입니다. 파이썬은 itertools.combinations가
바로 해 줍니다.

from itertools import combinations
n, k = map(int, input().split())
a = list(range(1, n + 1))
for c in combinations(a, k):
    print(*c)

C++엔 조합 전용 함수가 없어, 0/1 마스크로 정확히 \(k\)개 켜진 것만 고르는
방법이 간단합니다.

int n, k; cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = i + 1;

// 뒤 k개를 1, 앞 N-k개를 0으로 두고 next_permutation
vector<int> pick(n, 0);
for (int i = n - k; i < n; i++) pick[i] = 1;
do {
    for (int i = 0; i < n; i++) if (pick[i]) cout << a[i] << ' ';
    cout << '\n';
} while (next_permutation(pick.begin(), pick.end()));

next_permutation은 정렬된 0...01...1에서 시작하므로 \(\binom{N}{k}\)개의 서로
다른 선택을 모두 만듭니다. 복잡도 \(O(\binom{N}{k} \cdot N)\).

2. 재귀 DFS — 조합 열거의 정석

라이브러리 없이, 그리고 나중에 백트래킹으로 확장하기 좋은 형태가 재귀입니다.
"시작 인덱스부터 하나 고르고, 다음은 그 뒤에서 고른다"로 오름차순 조합을
만듭니다.

int n, k;
int a[20], chosen[20];
void dfs(int start, int depth) {
    if (depth == k) {                       // k개 다 골랐다
        for (int i = 0; i < k; i++) cout << chosen[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = start; i < n; i++) {        // 뒤로만 진행 → 중복 없음
        chosen[depth] = a[i];
        dfs(i + 1, depth + 1);               // 다음은 i+1부터
    }
}

def dfs(start, chosen):
    if len(chosen) == k:
        print(*chosen)
        return
    for i in range(start, n):
        dfs(i + 1, chosen + [a[i]])

dfs(i + 1, ...)이 뒤로만 나아가는 것이 조합의 핵심입니다. dfs(0, ...)으로
매번 처음부터 다시 고르면 순서쌍(중복 포함)이 됩니다.

3. 재귀로 순열·부분집합도 통일하기

같은 재귀 틀로 셋 다 만들 수 있습니다. 차이는 "다음에 무엇을 고를 수 있나"뿐:

  • 부분집합: 각 원소마다 "넣는다 / 뺀다" 두 갈래.
  • 순열: used[]로 안 쓴 원소 전부가 후보(그래서 start가 아니라 매번 0부터).
  • 조합: start부터 뒤로만.
// 순열: used로 중복 사용 방지
int n, perm[10]; bool used[10];
void permute(int depth) {
    if (depth == n) { /* perm 출력 */ return; }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true;  perm[depth] = i;
        permute(depth + 1);
        used[i] = false;                     // 되돌리기
    }
}

이 "고르기 → 재귀 → 되돌리기" 구조가 바로 다음 단원 백트래킹의 뼈대입니다.
완전 탐색을 재귀로 짤 줄 알면 가지치기만 얹어 백트래킹으로 자연스럽게
확장됩니다.

4. 파이썬 product — 중복 순열 / 진법 열거

"각 자리에 \(0\sim m-1\)을 자유롭게" 같은 \(m^n\)가지 열거는 product가 편합니다.

from itertools import product
# n자리, 각 자리 0..m-1 (중복 허용) — 총 m^n 가지
for combo in product(range(m), repeat=n):
    print(combo)

\(N\)진법 카운팅, 각 칸의 색 정하기 등 "칸마다 독립 선택" 문제에 딱 맞습니다.
C++에선 재귀나 다중 루프로 같은 것을 만듭니다.

정리

  • 조합: 파이썬 combinations, C++ 0/1 마스크 next_permutation 또는 재귀 DFS.
  • 재귀 하나로 부분집합·순열·조합을 통일 — 차이는 "다음 후보 집합"뿐.
  • product는 \(m^n\) 독립 선택 열거. 이 재귀 틀이 백트래킹으로 이어진다.
Lesson 완전 탐색 실전: 함정과 문제 유형 선택 8m

완전 탐색 실전: 함정과 문제 유형

완전 탐색은 "무엇을 열거할지"만 정확히 잡으면 절반은 끝납니다. 실전에서
자주 나오는 유형과, 걸려 넘어지는 함정을 정리합니다.

1. 문제 유형별 대응표

문제 말투 열거 대상 도구
"부분집합 중 …" / "몇 개를 골라" \(2^N\) 비트마스크
"\(N\)개를 일렬로 / 순서대로" \(N!\) next_permutation / permutations
"\(k\)개를 고르는 방법" \(\binom{N}{k}\) 재귀 DFS / combinations
"각 칸/자리를 정한다" \(m^N\) product / 다중 루프 / 재귀
"N과 M" 시리즈 순열·조합·중복 재귀 열거

가장 흔한 실전 유형은 "\(N\)개 중 몇 개를 골라 두 팀으로 나눈다"(부분집합),
"모든 방문 순서를 시도"(외판원류 순열), "각 스위치의 on/off"(비트마스크)
입니다.

2. 함정 1 — 경우의 수 폭발

\(N\)이 조금만 커도 지수·계승은 순식간에 터집니다.

$$ 2^{30} \approx 10^9, \quad 13! \approx 6\times10^9, \quad 20! \approx 2\times10^{18} $$

\(N \le 20\)이면 \(2^N\), \(N \le 11\)이면 \(N!\)까지가 현실적인 한계입니다. 이 선을
넘으면 완전 탐색 대신 DP·그리디·수학으로 넘어가야 한다는 신호입니다. 특히
순열은 \(N=13\)부터 이미 위험하니 상한을 꼭 확인하세요.

3. 함정 2 — 중복 답 / 대칭

같은 값이 여러 개이거나 문제에 대칭이 있으면 같은 답을 여러 번 셀 수
있습니다.

  • 같은 원소 중복: 입력에 같은 수가 있으면 순열/조합이 중복 출력됩니다.
    정렬 후, 같은 깊이에서 직전과 같은 값은 건너뛰기로 막습니다.
sort(a, a + n);
for (int i = start; i < n; i++) {
    if (i > start && a[i] == a[i - 1]) continue;   // 같은 값 스킵
    /* 고르고 재귀 */
}
  • 팀 나누기 대칭: "두 팀으로 나눈다"에서 (A팀, B팀)과 (B팀, A팀)이 같은
    분할이면, 한쪽 원소(예: 0번)를 항상 A팀에 고정해 절반만 세는 식으로 중복을
    없앱니다.

4. 함정 3 — 사전순 출력

"사전순으로 출력하라"는 조건은 후보를 오름차순으로 순회하면 자동 충족됩니다.
next_permutation은 정렬 상태에서 시작하면 이미 사전순, 재귀는 후보를 작은
것부터 고르면 됩니다. 순서를 뒤섞어 놓고 정렬 없이 시작하면 일부 순열이
누락되니 주의하세요.

5. 함정 4 — 비트 연산 실수

  • 연산자 우선순위: mask & 1 << i는 mask & (1 << i)가 아니라
    (mask & 1) << i로 해석됩니다. 반드시 괄호: mask & (1 << i).
  • int 시프트 한계: 1 << 31 이상이면 int 오버플로. \(N \ge 31\)이면
    1LL << i(long long)를 쓰세요.
  • 비트 개수 세기: 켜진 비트 수는 C++ __builtin_popcount(mask), 파이썬
    bin(mask).count('1').

6. 완전 탐색 → 백트래킹으로 승격

완전 탐색이 "만들고 나서" 검사한다면, 만드는 도중에 규칙 위반을 발견하고
가지를 잘라 내는 것이 백트래킹입니다. 다음 신호면 백트래킹으로 넘어가세요.

  • \(N\)은 작지만 순수 \(2^N\)/\(N!\)가 살짝 빡빡하다.
  • 부분 답이 일찍 규칙을 위반해 더 볼 필요가 없는 구조(합 초과, 충돌 등).

같은 재귀 골격에 "재귀 호출 전 유효성 검사(가지치기)"만 얹으면 됩니다.

정리

  • 유형을 말투로 판별해 열거 대상(\(2^N\)·\(N!\)·\(\binom{N}{k}\)·\(m^N\))을 고른다.
  • 경우의 수 폭발, 중복/대칭, 사전순, 비트 우선순위 — 네 함정을 항상 점검.
  • 규칙 위반을 일찍 자를 수 있으면 백트래킹으로 승격하라.
Practice problem 먼 카드 선택 25m
KOI00001

먼 카드

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Bronze III 브론즈 III 지금 풀기
Practice problem Debug 선택 25m
COCI00006

Debug

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Lesson 재귀의 개념: 자기 자신을 부르는 함수 필수 8m

재귀란?

재귀(recursion) 는 함수가 자기 자신을 다시 호출해서 문제를 푸는 방법입니다.
큰 문제를 똑같은 모양의 더 작은 문제로 쪼갤 수 있을 때 자연스럽게 쓰입니다.

"\(n\)의 팩토리얼 = \(n \times (n-1)\)의 팩토리얼" 처럼, 답을 자기보다 작은
같은 종류의 답으로 표현할 수 있으면 재귀입니다.

1. 재귀의 두 기둥

모든 재귀 함수는 반드시 다음 두 가지를 가져야 합니다.

  • 기저 조건(base case): 더 이상 쪼개지 않고 바로 답을 주는 가장 작은 경우. 재귀를 멈추는 브레이크입니다.
  • 재귀 식(recursive case): 문제를 더 작은 문제로 줄여 자기 자신을 부르는 부분.

기저 조건이 없거나 잘못되면 함수가 영원히 자신을 불러 스택 오버플로로 죽습니다.

2. 팩토리얼 — 가장 기본

\(n! = n \times (n-1) \times \cdots \times 1\), 그리고 \(0! = 1\).

long long factorial(int n) {
    if (n <= 1) return 1;          // 기저 조건
    return n * factorial(n - 1);   // 재귀 식: n! = n * (n-1)!
}

def factorial(n):
    if n <= 1:          # 기저 조건
        return 1
    return n * factorial(n - 1)   # n! = n * (n-1)!

factorial(4) 는 4 * factorial(3) → 4 * (3 * factorial(2)) → … 로 펼쳐지고,
factorial(1) 에서 멈춰 1 을 돌려주면 그 값이 위로 곱해지며 되돌아옵니다.

3. 콜 스택 — 재귀가 도는 원리

함수를 부르면 그 호출 정보(지역 변수, 돌아올 위치)가 콜 스택에 쌓입니다.
재귀는 기저 조건까지 쌓였다가, 거기서부터 하나씩 정리되며 값을 되돌립니다.

factorial(4)  →  factorial(3)  →  factorial(2)  →  factorial(1)=1
     24       ←       6        ←       2         ←   (되돌아옴)

1부터 \(n\)까지의 합도 똑같은 구조입니다.

int sum(int n) {
    if (n == 0) return 0;      // 기저 조건
    return n + sum(n - 1);     // n까지 합 = n + (n-1)까지 합
}

4. 언제 재귀를 쓰나 · 복잡도

  • "답 = 더 작은 같은 문제의 답" 으로 관계식이 세워질 때.
  • 트리·그래프 탐색, 분할 정복, 백트래킹처럼 가지가 갈라지는 구조.

호출이 \(n\)번이면 시간은 \(O(n)\), 콜 스택 깊이(메모리)도 \(O(n)\)입니다.
반복문과 달리 깊이만큼 스택을 쓴다는 점을 늘 기억하세요.

정리

재귀 = 기저 조건 + 자기보다 작은 문제로의 호출. 팩토리얼·합처럼 관계식이
보이면 재귀가 가장 깔끔합니다. 다음 강의에서 피보나치·거듭제곱·하노이 같은
대표 예제와 재귀↔반복 변환을 코드로 익힙니다.

Lesson 재귀 구현: 피보나치·거듭제곱·하노이 선택 8m

대표 재귀 예제

재귀의 감을 잡는 가장 좋은 방법은 표준 예제를 직접 써 보는 것입니다.
관계식을 세우고 → 기저 조건을 정하고 → 그대로 코드로 옮깁니다.

1. 피보나치 수열

\(F_0 = 0,\ F_1 = 1,\ F_n = F_{n-1} + F_{n-2}\).

long long fib(int n) {
    if (n <= 1) return n;          // F0=0, F1=1
    return fib(n - 1) + fib(n - 2);
}

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

이 순수 재귀는 같은 값을 몇 번씩 다시 계산해 \(O(\varphi^n)\) (약 \(1.6^n\))로
매우 느립니다 — 다음 강의의 메모이제이션으로 \(O(n)\)이 됩니다.

2. 빠른 거듭제곱 (분할 정복)

\(a^b\) 를 \(O(b)\) 대신 \(O(\log b)\) 로: \(a^b = (a^{b/2})^2\) 를 이용합니다.

long long power(long long a, long long b) {
    if (b == 0) return 1;              // a^0 = 1
    long long half = power(a, b / 2);  // 절반을 한 번만 계산
    if (b % 2 == 0) return half * half;
    return half * half * a;            // b가 홀수면 a를 한 번 더
}

def power(a, b):
    if b == 0:
        return 1
    half = power(a, b // 2)
    if b % 2 == 0:
        return half * half
    return half * half * a

half 를 변수에 담아 한 번만 계산하는 것이 핵심입니다.
power(a, b/2) * power(a, b/2) 로 두 번 부르면 다시 \(O(b)\)가 됩니다.

3. 하노이 탑

원판 \(n\)개를 from → to 로 옮기기: (1) 위 \(n-1\)개를 via 로, (2) 가장 큰 것을
to 로, (3) via 의 \(n-1\)개를 to 로. 이동 횟수는 \(2^n - 1\)입니다.

void hanoi(int n, int from, int to, int via) {
    if (n == 0) return;                 // 옮길 원판이 없으면 끝
    hanoi(n - 1, from, via, to);        // 1) 위 n-1개를 via로
    cout << from << ' ' << to << '\n';  // 2) 큰 원판 이동
    hanoi(n - 1, via, to, from);        // 3) via의 n-1개를 to로
}

def hanoi(n, frm, to, via):
    if n == 0:
        return
    hanoi(n - 1, frm, via, to)
    print(frm, to)
    hanoi(n - 1, via, to, frm)

4. 재귀 ↔ 반복 변환

꼬리에서 한 번만 자신을 부르는(선형) 재귀는 반복문으로 바꿀 수 있고,
그러면 콜 스택을 안 쓰므로 깊이 제한과 오버헤드가 사라집니다.

long long factorial(int n) {   // 위 강의의 재귀를 반복으로
    long long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

가지가 여러 개로 갈라지는 재귀(트리 탐색 등)는 반복으로 바꾸기 어렵고,
그럴 땐 재귀가 훨씬 읽기 좋습니다.

정리

관계식 → 기저 조건 → 코드 순으로 옮기면 됩니다. 거듭제곱은 절반을
변수에 담아 \(O(\log b)\), 하노이는 "위 \(n-1\)개 → 큰 것 → 다시 \(n-1\)개"
3단계. 선형 재귀는 반복으로도 쓸 수 있음을 기억하세요.

Lesson 재귀 심화: 중복 호출·메모이제이션·스택 한계 선택 8m

재귀에서 진짜 조심할 것들

재귀는 짧고 우아하지만 느려지거나 죽는 함정이 뚜렷합니다. 성능과 안정성
문제를 하나씩 정리합니다.

1. 지수적 중복 호출 → 메모이제이션

순수 재귀 피보나치는 fib(n-2) 를 수없이 다시 계산합니다. 한 번 구한 답을
저장(메모) 해 두고 재사용하면 \(O(\varphi^n)\)이 \(O(n)\) 으로 줄어듭니다.

long long memo[91];   // 0이면 "아직 안 구함". fib(90)까지 long long에 들어감
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];          // 이미 구했으면 재사용
    return memo[n] = fib(n - 1) + fib(n - 2);
}

import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

@lru_cache(maxsize=None)     # 자동 메모이제이션
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

이 "재귀 + 메모"가 바로 DP(동적 계획법) 의 출발점입니다.

2. 스택 오버플로 · 깊이 한계

재귀 깊이만큼 콜 스택을 쓰므로, 너무 깊으면 스택이 터집니다.

  • C++: 보통 수십만 깊이까지는 버티지만, 큰 배열을 지역 변수로 두고
    깊이 들어가면 위험합니다. 깊은 선형 재귀는 반복문으로 바꾸세요.
  • 파이썬: 기본 재귀 한도가 1000 이라 조금만 깊어도 RecursionError.
    깊은 재귀 문제는 맨 위에 반드시 다음을 넣습니다.
import sys
sys.setrecursionlimit(10**6)   # 재귀 한도 늘리기 (깊은 DFS 필수)

3. 기저 조건 함정

int bad(int n) {
    return n + bad(n - 1);   // 기저 조건이 없다 → 영원히 내려가 스택 터짐
}
  • 기저 조건 누락/도달 불가: n이 음수로도 갈 수 있으면 if (n == 0) 만으론
    안 멈춥니다. if (n <= 0) 처럼 반드시 걸리도록 범위로 막으세요.
  • 인자를 줄이지 않음: rec(n) 안에서 또 rec(n) 을 부르면 무한 재귀입니다.
    매 호출마다 문제가 분명히 작아지는지 확인하세요.

4. 값 전달과 되돌리기

재귀에 상태를 넘길 때, 값으로 넘기면 각 호출이 독립적이라 안전하지만,
참조/전역을 고쳐 가며 내려가면 돌아올 때 원상 복구해야 합니다
(백트래킹의 "선택 취소"). 헷갈리면 일단 값으로 넘겨 보세요.

def rec(depth, path):          # path를 값처럼 새로 만들어 넘기면 복구 불필요
    if depth == n:
        answer.append(path[:])
        return
    for x in candidates:
        rec(depth + 1, path + [x])   # 새 리스트를 넘김 → 되돌리기 없음

5. 흔한 실수 총정리

증상 원인 해결
답이 느림(시간 초과) 같은 부분문제 재계산 메모이제이션
RecursionError(파이썬) 기본 재귀 한도 1000 setrecursionlimit
무한 재귀/스택 터짐 기저 조건 누락, 인자 안 줄임 멈추는 조건을 범위로
답이 뒤섞임 전역/참조 상태 복구 안 함 되돌리기 or 값 전달

정리

느리면 메모이제이션, 깊으면 한도 상향/반복 전환, 안 멈추면 기저 조건을
의심하세요. 재귀 + 메모가 곧 DP로 이어진다는 것이 이 단원의 큰 그림입니다.

Practice problem 하노이 탑 이동 횟수 선택 25m
R00122

하노이 탑 이동 횟수

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 참외 나누기 선택 25m
R01297

참외 나누기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Lesson 가지치기로 똑똑해진 완전 탐색 필수 8m

백트래킹이란?

백트래킹(backtracking) 은 가능한 답을 하나씩 만들어 가다가, 더 진행해도
답이 될 수 없다고 판단되면 즉시 되돌아와(back-track) 다른 선택을 시도하는
탐색 기법입니다. 한마디로 가지치기(pruning)가 들어간 완전 탐색입니다.

미로에서 막다른 길을 만나면 마지막 갈림길로 돌아가 다른 길을 택하는 것과
같습니다.

1. 완전 탐색과 무엇이 다른가

순수 완전 탐색은 모든 후보를 끝까지 다 만들어 봅니다. 백트래킹은 만드는 도중에
"이 선택은 규칙을 어긴다"고 알면 그 가지를 통째로 잘라 냅니다.

N-Queen: 같은 열/대각선에 퀸이 있으면 더 놓아 볼 필요 없이 되돌아간다.

이 가지치기 덕분에 이론상 \(N!\)인 탐색이 실제로는 훨씬 적은 경우만 보고 끝납니다.
가지치기가 강할수록 탐색량이 극적으로 줄어드는 것이 백트래킹의 힘입니다.

2. 백트래킹의 3요소

모든 백트래킹은 다음 세 가지로 구성됩니다.

  • 선택(choice): 현재 단계에서 시도할 수 있는 후보들.
  • 제약(constraint): 만족해야 하는 규칙 — 어기면 가지치기.
  • 목표(goal): 답이 완성되는 조건 — 도달하면 기록.

재귀로 한 단계 내려가며 선택하고, 막히면 선택을 취소(되돌리기)하고 다음 후보를
시도합니다.

3. 상태 공간 트리

백트래킹은 상태 공간 트리를 깊이 우선(DFS)으로 탐색하는 것과 같습니다.

            (시작)
          /   |   \
        선택A 선택B 선택C
        / \         (제약 위반 -> 가지치기)
      ...  ...

각 노드는 "부분적으로 만들어진 답"이고, 잎(leaf)에 도달하면 완성된 답입니다.
중간에 제약을 어기는 노드는 그 아래를 통째로 자릅니다. 잘린 부분만큼 계산을
아끼는 셈입니다.

4. 대표 문제들

문제 선택 제약
N-Queen 각 행에 퀸의 열 같은 열·대각선 금지
순열/조합 (N과 M) 다음에 고를 원소 이미 고른 것 제외 등
부분집합 합 각 원소 포함 여부 합이 목표 초과 금지
스도쿠 빈 칸의 숫자 행·열·박스 중복 금지

5. 가지치기가 전부다

백트래킹의 성능은 얼마나 빨리, 많이 가지치기하느냐로 결정됩니다. 좋은
가지치기 아이디어:

  • 제약 위반 즉시 중단 — 규칙을 어기는 순간 되돌아간다.
  • 하한/상한 추정 — "남은 걸 다 더해도 목표에 못 미친다"면 포기.
  • 유망성 판단 — 현재까지의 부분 답이 최선의 답을 갱신할 가능성이 없으면 중단.

가지치기 없는 백트래킹은 그냥 느린 완전 탐색입니다. 최악의 경우 복잡도는
여전히 \(O(N!)\)이나 \(O(2^N)\)이지만, 좋은 가지치기는 실제 실행을 수백~수만 배
빠르게 만듭니다.

정리

백트래킹 = 완전 탐색 + 되돌리기 + 가지치기. 선택·제약·목표를 정의하고, 재귀로
내려가며 막히면 되돌아옵니다. 다음 강의에서 표준 구현 골격과 N-Queen, 순열
생성을 코드로 만듭니다.

Lesson 백트래킹 구현 골격과 N-Queen 선택 8m

백트래킹 구현 골격과 N-Queen

백트래킹은 거의 항상 같은 재귀 골격을 따릅니다. 그 틀을 익히고 대표 문제에
적용합니다.

1. 표준 골격

void backtrack(상태) {
    if (목표 도달) { 답 기록; return; }
    for (각 선택지 c) {
        if (!유효(c)) continue;     // 제약 위반 -> 가지치기
        선택(c);                    // 상태에 c 반영
        backtrack(다음 상태);
        선택취소(c);                // 되돌리기 (중요!)
    }
}

선택취소(되돌리기) 가 백트래킹의 심장입니다. 다음 후보를 깨끗한 상태에서
시도하려면 방금 한 선택을 반드시 원래대로 돌려놓아야 합니다.

2. 순열 생성 (N개를 줄 세우기)

int n, perm[10];
bool used[10];
void rec(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; i++) cout << perm[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;       // 이미 쓴 수는 건너뜀
        used[i] = true;              // 선택
        perm[depth] = i;
        rec(depth + 1);
        used[i] = false;             // 선택취소
    }
}

import sys
sys.setrecursionlimit(10000)
def rec(depth, perm, used, n):
    if depth == n:
        print(*perm)
        return
    for i in range(1, n + 1):
        if used[i]:
            continue
        used[i] = True               # 선택
        perm.append(i)
        rec(depth + 1, perm, used, n)
        perm.pop()                   # 선택취소
        used[i] = False

3. N-Queen (가지치기의 정수)

\(N \times N\) 체스판에 서로 공격하지 못하게 퀸 \(N\)개를 놓는 방법의 수.

int n, cnt = 0;
int col[15];                         // col[r] = r행 퀸의 열
bool ok(int r, int c) {
    for (int i = 0; i < r; i++) {
        if (col[i] == c) return false;                    // 같은 열
        if (abs(col[i] - c) == abs(i - r)) return false;  // 대각선
    }
    return true;
}
void solve(int r) {
    if (r == n) { cnt++; return; }   // 모든 행에 다 놓음
    for (int c = 0; c < n; c++) {
        if (!ok(r, c)) continue;     // 공격받으면 가지치기
        col[r] = c;                  // 선택
        solve(r + 1);
        // 배열 덮어쓰기라 별도 선택취소 불필요
    }
}

행마다 퀸 하나씩만 놓는 것으로 탐색 공간을 \(N^N\)에서 \(N!\)로 줄이고, ok의
가지치기로 실제 탐색량을 더 크게 줄입니다.

\(O(1)\) 유효성 검사로 가속

매번 ok로 이전 행을 훑으면 검사가 \(O(N)\)입니다. 열/두 대각선의 사용 여부를
배열로 들고 있으면 \(O(1)\)이 됩니다. 대각선은 r+c(↘)와 r-c+N(↗)로 번호를
매깁니다.

bool usedCol[15], diag1[30], diag2[30];   // diag2는 r-c+N (음수 방지)
void solve(int r) {
    if (r == n) { cnt++; return; }
    for (int c = 0; c < n; c++) {
        if (usedCol[c] || diag1[r + c] || diag2[r - c + n]) continue;
        usedCol[c] = diag1[r + c] = diag2[r - c + n] = true;      // 선택
        solve(r + 1);
        usedCol[c] = diag1[r + c] = diag2[r - c + n] = false;     // 선택취소
    }
}

4. 부분집합 합 (가지치기 예)

bool rec(int idx, int sum, int target) {
    if (sum == target) return true;
    if (idx == n || sum > target) return false;         // 초과하면 가지치기
    if (rec(idx + 1, sum + a[idx], target)) return true; // 포함
    return rec(idx + 1, sum, target);                    // 미포함
}

sum > target이면 더 진행할 필요 없이 즉시 중단하는 것이 가지치기입니다.
(단, 음수가 섞이면 이 가지치기는 성립하지 않으니 조건을 문제에 맞게 조정하세요.)

5. 흔한 실수

  • 선택취소 누락 — 되돌리기를 빠뜨리면 상태가 오염되어 답이 틀립니다.
    (단, 배열을 통째로 덮어쓰는 경우는 예외.)
  • 가지치기 부재 — 제약 검사를 안 하면 그냥 느린 완전 탐색이 됩니다.
  • used 배열 안 씀 — 순열에서 중복 사용 방지를 빠뜨림.
  • 파이썬 깊이/속도 — 깊은 백트래킹은 setrecursionlimit와 효율적 가지치기 필수.

6. 패턴 알아보기

  • "가능한 모든 경우를 나열/세라" + 제약이 있다 → 백트래킹.
  • "조건을 만족하는 배치/조합/순열" → 백트래킹.
  • \(N\)이 작고(\(\le 15\) 부근) 완전 탐색이지만 제약으로 가지치기가 가능 → 백트래킹.
Lesson 실전 가이드 — 상태 복원과 가지치기 설계 선택 8m

실전 가이드 — 상태 복원과 가지치기 설계

백트래킹 문제는 골격이 거의 같아서, 승부는 상태 설계와 가지치기에서
갈립니다. 실수 없이 골격을 찍어 내는 절차를 정리합니다.

1. 출제 신호

  • "조건을 만족하는 모든 수열을 사전순으로 출력" — N과 M 시리즈류.
    생성 + 제약이면 백트래킹입니다.
  • 배치 문제 — N-Queen, 스도쿠, 알파벳 격자 탐험처럼 "서로 공격하지 않게 /
    겹치지 않게 놓기".
  • \(N \le 15\) 안팎인데 단순 \(2^N\)/\(N!\) 완전 탐색은 살짝 빡빡 — 가지치기로
    깎으라는 신호입니다.
  • 부분 수열의 합·조합이 조건을 일찍 위반하면 더 볼 필요가 없는 구조.

2. 풀이 결정 절차

  1. 상태를 정합니다 — 지금까지 고른 것(경로)과, 유망성 검사를 \(O(1)\)로
    만들어 줄 보조 표시(열 사용 여부, 대각선 사용 여부 등).
  2. 선택지를 나열하는 순서를 정합니다 — 사전순 출력이 요구되면 선택지를
    정렬된 순서로 순회해야 합니다.
  3. 가지치기 조건을 적습니다 — "여기서 이미 합이 목표를 넘으면 중단"처럼,
    재귀 호출 전에 검사할 수 있는 형태로.
  4. 표시 → 재귀 → 해제가 짝을 이루는지 골격에서 확인합니다.

3. 자주 하는 실수

  • 방문 해제 누락. 표시만 하고 해제를 잊으면 두 번째 가지부터 후보가
    사라집니다. 표시와 해제는 같은 들여쓰기 깊이에서 짝으로 쓰세요.
void rec(int depth) {
    if (depth == m) { print(); return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;       // 유망성 검사는 호출 "전"에
        used[i] = true;              // 1) 표시
        path[depth] = a[i];
        rec(depth + 1);              // 2) 재귀
        used[i] = false;             // 3) 해제 — 표시와 반드시 짝!
    }
}
  • N-Queen에서 격자 전체 검사. 매번 보드를 훑으면 너무 느립니다. 열,
    두 대각선(r+c, r-c+N)의 사용 여부 배열로 \(O(1)\) 검사가 정석입니다.
  • 중복 값 처리. 같은 숫자가 여러 개인 입력에서 "같은 수열 중복 출력"을
    막으려면 정렬 후 i > start && a[i] == a[i-1]인 후보를 건너뜁니다.
  • 가지치기를 기저에서 함. 끝까지 내려간 뒤 검사하면 가지치기 효과가
    없습니다. 위반은 가능한 한 위쪽(호출 전) 에서 잘라야 합니다.
  • 전역 경로에 push 후 pop 누락. vector에 push_back했으면 재귀 후
    pop_back. 비대칭이면 경로가 오염됩니다.

4. 변형 다루기

  • 중복 순열/조합 (N과 M 4가지 변형): 순서 O·중복 X → 순열, 순서 X·중복 X →
    조합, 중복 허용은 used 대신 start 인덱스를 다음 후보로 넘기는 방식으로
    조절합니다. 순열은 매번 for i in 1..n, 조합·비내림차순은 for i in start..n.
  • 최적해 백트래킹(분기 한정): 답을 세는 대신 "가장 좋은 것"을 찾을 땐,
    현재까지 비용 + 낙관적 하한이 지금까지의 최적보다 나쁘면 가지치기합니다.
if (curCost + lowerBound(remaining) >= best) return;   // 유망성 가지치기
  • 스도쿠형: 빈 칸을 하나 골라 1~9를 시도하되, 행·열·박스 사용 표를 \(O(1)\)로
    검사하고 되돌립니다. "후보가 가장 적은 칸부터" 고르면 훨씬 빨라집니다.

5. 연습 방법

순열·조합 생성형(N과 M류)으로 골격을 손에 익힌 뒤 N-Queen형 배치 문제로
가세요. 같은 골격을 안 보고 5분 안에 쓸 수 있을 때까지 반복하는 것이 이
단원의 핵심 훈련입니다.

정리

  • 상태(경로 + \(O(1)\) 유망성 표시)를 먼저 설계하고, 가지치기는 호출 전에.
  • 표시와 해제는 반드시 짝. 배열 덮어쓰기 예외를 제외하면 되돌리기를 빠뜨리지 마라.
  • N과 M 4변형·최적해 분기한정·스도쿠형으로 변형을 확장하라.
Practice problem 외판원 순회 (정확해) 선택 25m
R00706

외판원 순회 (정확해)

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 사전순 수열 선택 25m
R00139

사전순 수열

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기