들어가며

80분에 20~25문제 - 200점 만점
60개 이하의 직접 계산이 가능한 문제는 시도해봐도 됨
- 그 이상을 넘어가면 공식이나, 패턴을 찾기
10번 이후의 주관식은 난이도가 높다
인터랙티브가 점수가 높으니, 도전해보자

점수 분포

초등부

중등부

0. 특강 개요

분석 범위

대상: 2019~2025 KOI 1교시 초등부, 중등부, 고등부
총 문항 수: $21 \times 20 = 420$ 문항

기출에서 반복적으로 많이 보이는 축

주제	대략적 반복도	대표 예시
순열과 조합	약 140문항 이상	2024 중등 `두 개씩 곱하기`, 2025 고등 `투표 결과`
그래프, 트리	약 70문항 이상	2024 중등 `그래프의 중심`, `최소 신장 트리`, 2022 초등 `두 트리 연결하기`
순열, 사전순, 정렬	약 50문항 이상	2024 중등 `순열 찾기`, 2025 고등 `숫자 제거`
그리디, 시뮬레이션, 역추적	약 60문항 안팎	2025 고등 `마법 문자열`, 2024 중등 `최소 신장 트리`
확률	약 30문항 안팎	2020 중등 `가위바위보 확률`, 2021 중등 `동전과 확률`
이진 논리와 진법 변환, 비트	약 30문항 안팎	2024 중등 `진법 변환`, 2019 중등 `곱의 이진수 끝자리`
게임, 불변량	약 40문항 안팎	2025 고등 `돌 가져가기 게임`, 2022 초등 `게임`
스택과 큐	직접 명시 출제는 적지만 중요	2025 초/중/고 `스택`, BFS와 그래프 탐색의 핵심 도구

문제를 읽고 분류하는 1차 체크

flowchart TD
  A["문제를 읽고 핵심 단어 표시"] --> B{"무엇을 묻는가?"}
  B -->|"개수"| C["경우의 수 / 조합 / 포함배제"]
  B -->|"몇 번째 / 사전순"| D["순열 / 정렬 / 팩토리얼 묶음"]
  B -->|"연결 / 이동 / 경로"| E["그래프 / 트리 / BFS"]
  B -->|"push / pop / 순서"| F["스택 / 큐 / 시뮬레이션"]
  B -->|"최소 / 최대"| G["그리디 가능성 점검"]
  B -->|"이길 수 있는가"| H["게임 / W-L 분류 / 불변량"]

1. 진법, 2진수, 진법 변환

1-1. 왜 자주 나오는가

KOI에서는 진법 문제를 단순 계산으로 내기도 하지만, 실제로는 다음과 같은 사고를 묻는 경우가 많다.

수를 자리값의 합으로 표현할 수 있는가
2진수로 바꾼 뒤 규칙을 더 쉽게 볼 수 있는가
비트 단위의 규칙이 반복되는가

1-2. 기초 이론

자리값 표현

$b$ 진수 $a_{k} a_{k - 1} \dots a_{1} a_{0}$ 는 다음과 같다.

(a_{k} a_{k - 1} \dots a_{1} a_{0})_{b} = i = 0 \sum k a_{i} b^{i}

예를 들어

(4321)_{5} = 4 \cdot 5^{3} + 3 \cdot 5^{2} + 2 \cdot 5 + 1

이다.

$10$ 진수 $\to b$ 진수 변환

반복해서 $b$ 로 나누고 나머지를 기록한다.

예를 들어 $345$ 를 $3$ 진수로 바꾸면

345 \div 3 = 115 remainder 0

115 \div 3 = 38 remainder 1

38 \div 3 = 12 remainder 2

12 \div 3 = 4 remainder 0

4 \div 3 = 1 remainder 1

1 \div 3 = 0 remainder 1

따라서

34 5_{10} = 11021 0_{3}

이다.

$2$ 진수와 $8$ 진수, $16$ 진수의 관계

$8 = 2^{3}$ 이므로 $8$ 진수 한 자리는 $2$ 진수 세 자리와 대응
$16 = 2^{4}$ 이므로 $16$ 진수 한 자리는 $2$ 진수 네 자리와 대응

예:

A 6 E 4 F 3_{16}

에서 각 자리를 $2$ 진수 네 자리로 바꾸면

101001101110010011110011

이고, 이를 세 자리씩 끊으면 $8$ 진수로 바로 갈 수 있다.

비트 사고의 핵심

짝수/홀수는 맨 마지막 비트만 보면 된다.
어떤 연산이 반복되면 나머지나 비트 패턴의 주기를 찾는다.
AND, OR, XOR는 자리별로 독립적으로 생각할 수 있다.

1-3. KOI에서 자주 나오는 포인트

진법 문제를 보면 중간에 $2$ 진수로 가는 것이 가장 안전하다.
마지막 자리, 자릿수 합, 연속된 $1$ 의 개수처럼 “전체가 아니라 일부 정보”를 묻는 경우가 많다.
매우 큰 수가 나오면 실제 값을 계산하지 말고 주기, 자리값, 나머지를 본다.

1-4. 실수 포인트

묶음이 맞지 않을 때 왼쪽에 $0$ 을 채우는 것을 빼먹음
$10$ 진수로 환산할 때 지수 위치를 하나씩 밀림
“나머지”와 “몫”을 뒤섞음

1-5. 연습 문제

$34 5_{10}$ 을 $3$ 진수로 바꾸어라.

1-6. 기출 문제

2. 경우의 수, 조합, 순열, 사전순

2-1. 왜 가장 중요하나

기출 분석에서 가장 많이 반복된 축이 바로 경우의 수와 조합이다. KOI 1교시에서는 “브루트포스로 세는 척하지만 실제로는 구조를 잡아야 빠른” 문제가 계속 나온다.

2-2. 가장 기본이 되는 원리

덧셈 원리

겹치지 않는 경우들이 여러 묶음으로 나뉘면 더한다.

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ (if A \cap B = \emptyset)

편의점에 갔는데 간식을 딱 하나만살 수 있는 경우
- 살 수 있는 간식
  - 과자 3종류
  - 아이스크림 2종류
  - 빵 4종류
과자를 고르거나, 아이스크림을 고르거나 빵을 고른다
또는, or 키워드

곱셈 원리

선택이 단계별로 이어지면 곱한다.

예를 들어 첫 번째 선택이 $m$ 가지, 두 번째가 $n$ 가지면 전체는 $mn$ 가지다.

편의점에서 세트로 사려는 경우
- 세트는 다음처럼 구성되어야함
  - 과자 1개 + 음료 1개
- 살 수 있는 간식 종류
  - 과자 3종류
  - 음료 2종류
과자를 1개 고르고, 음료도 1개 고른다
그리고, and 키워드

순열

$n$ 개 중 $r$ 개를 골라 순서를 세우는 경우:

순서가 중요함

_{n} P_{r} = \frac{n !}{( n - r )!}

5명이 달리기해서 1등부터 3등까지 정한다면 경우의 수는?

조합

$n$ 개 중 $r$ 개를 골라 순서를 무시하는 경우:

_{n} C_{r} = (r n) = \frac{n !}{r ! ( n - r )!}

5명의 회장 입후보 중, 2명에게 투표하는 경우의 수는?

2-3. KOI에서 특히 자주 쓰는 패턴

패턴 A: “앞부분만 정하면 뒤가 자동으로 정해지는” 경우

예:

회문
대칭 색칠
짝 맞추기

예를 들어 길이 $9$ 회문은 앞의 $5$ 자리만 정하면 뒤는 자동으로 정해진다.

패턴 B: “몇 자리를 지워서 얻는 수”

이때는 보통 부분수열이다. 즉, 고른 뒤 원래 순서를 유지한다.

이 조건 때문에 “조합처럼 고르되, 고른 뒤 순서를 다시 섞지는 않는다.”

패턴 C: “몇 번째 순열인가”

사전순 순열에서는 다음 묶음이 팩토리얼 크기로 움직인다.

예를 들어 $1, 2, 3, 4, 5, 6$ 의 순열을 사전순으로 나열하면

첫 자리가 $1$ 인 묶음은 $5!$ 개
첫 자리가 $2$ 인 묶음도 $5!$ 개
…

이다.

패턴 D: 대칭성 활용

2025 고등 투표 결과처럼

$A > B$
$A < B$
$A = B$

로 나눌 수 있다면, $A > B$ 와 $A < B$ 가 대칭일 수 있다. 그러면

∣ A > B ∣ = \frac{전체 - ∣ A = B ∣}{2}

처럼 계산이 짧아진다.

2-4. 사전순 $k$ 번째 순열 찾기 요약

$n$ 개의 수를 사전순으로 나열했을 때, $k$ 번째 순열을 찾으려면:

첫 자리를 $(n - 1)!$ 로 나누어 몇 번째 묶음인지 본다.
그 묶음에 해당하는 원소를 고른다.
나머지에 대해 반복한다.

2-5. 실수 포인트

조합인지 순열인지 구분을 안 하고 무조건 $n!$ 을 씀
중복을 허용하는지 안 하는지 확인 안 함
“몇 번째” 문제에서 $0$ 번째 기준으로 바꾸지 않아 계산이 꼬임
부분수열 문제에서 원래 순서를 깨뜨림

2-6. 연습 문제

$1, 2, 3, 4, 5$ 의 순열을 사전순으로 나열했을 때, $42$ 번째 순열을 구하여라.
(보류) 문자 a,b,c로 길이 $7$ 의 문자열을 만들 때, a가 정확히 $3$ 개이고 서로 이웃하지 않게 하는 경우의 수를 구하여라.

2-7 기출 문제

2021 초등 3번, 중등 1번 다른 모자 쓰기
- 직접 계산
- 교란순열(완전순열) 공식
  - 원래 위치에 있는 원소가 하나도 없는 순열
  - $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ (점화식)
    - $n! Σ_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !} = n! (\frac{1}{2 !} - \frac{1}{3 !} + \frac{1}{4 !} - \dots + \frac{( - 1 ) ^{n}}{n !})$ (포함배제의 원리)
  - $D_{1} = 0, D_{2} = 1, D_{3} = 2, D_{4} = 9, D_{5} = 44, D_{6} = 265$
2024 초등 2번, 중등 1번, 고등 1번 두 개씩 곱하기
2024 중등 6번 순열 찾기:
2025 초등 10번, 중등 6번, 고등 4번 숫자 제거
2025 중등 9번, 고등 6번 투표 결과
- $3^{7} = 2187$

3. 확률, 집합, 포함배제, 논리

3-1. 이 챕터가 필요한 이유

KOI에서 확률 문제는 단독으로도 나오지만, 실제로는 조합과 집합, 경우 분할, 논리 조건과 묶여서 자주 나온다.

3-2. 확률의 기본

동등하게 가능한 경우라면

Pr (A) = \frac{∣ A ∣}{∣Ω∣}

이다.

여기서

$Ω$ : 전체 경우의 집합
$A$ : 원하는 사건

이다.

조합형 확률

두 개를 고르는 문제에서 순서가 중요하지 않으면 조합이 가장 깔끔하다.

예를 들어 10개 동전 중 $x$ 개가 특별한 면을 가진다면, 두 개를 뽑아 둘 다 특별할 확률은

\frac{( 2 x )}{( 2 10 )}

이다.

3-3. 포함배제 원리

겹치는 조건은 단순히 더하면 중복된다.

두 집합

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

세 집합

∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣

- 세 집합의 개수에 대하여 다음이 성립
  - $∣ A \cup B \cup C ∣ =$
    - $+ ∣ A ∣ + ∣ B ∣ + ∣ C ∣$
    - $- (∣ A \cap B ∣ + ∣ A \cap C ∣ + ∣ B \cap C ∣)$
    - $+ ∣ A \cap B \cap C ∣$
Link to original

예를 들어

$3$ 의 배수
$4$ 의 배수
그런데 $5$ 의 배수는 제외

같은 문제는 포함배제를 두 번 적용하면 된다.

3-4. 논리 문제의 기본 변환

함축

P \to Q \equiv \neg P \lor Q

즉, “ $P$ 이면 $Q$ 이다”는 “ $P$ 가 아니거나 $Q$ 이다”와 같다.

숙제를 하면, 과자를 받는다 $\equiv$ 숙제를 안했거나, 과자를 받았다.
- T, T → T
- T, F → F (숙제를 했는데, 과자를 안 준 경우만 거짓)
- F, T → T
- F, F → T

대우

P \to Q \equiv \neg Q \to \neg P

증명 문제에서 매우 자주 쓴다.

과자를 받지 않았으면, 숙제를 안한 것이다.

경우 분할

논리 퍼즐은 종종 “ $Q$ 가 참인가 거짓인가”처럼 갈라 보면 더 빠르다.

3-5. KOI식 접근 요령

확률 문제를 보면 먼저 전체 경우의 수를 조합으로 셀 수 있는지 본다.
또는, 적어도 하나, 둘 다 아님 같은 말이 보이면 여집합과 포함배제를 떠올린다.
논리 문제는 복잡한 식보다 경우 분할이 더 빠를 때가 많다.

3-6. 실수 포인트

순서가 없는 추출을 순열로 셈
A 또는 B를 $∣ A ∣ + ∣ B ∣$ 로만 처리함
이미 게임이 끝났는데 뒤의 경우까지 포함해서 확률을 잘못 셈
논리에서 “또는”을 일상어처럼 배타적으로 해석함

3-7. 연습 문제

빨간 공 $6$ 개, 파란 공 $4$ 개가 들어 있는 주머니에서 공 $2$ 개를 동시에 뽑을 때, 둘 다 빨간 공일 확률을 구하여라.
- 확률로 구하기
  - 곱셉 원리
  - $\frac{6}{10} * \frac{5}{9}$
- 조합으로 확률 구하기
  - 빨간 공에서 2개 뽑는 경우의 수 / 전체에서 2개를 뽑는 경우의 수
  - $\frac{_{r} C _{2}}{_{r + b} C _{2}}$
- 다음을 표기해봅시다
  - 전체 경우의 수 :
  - 2개다 빨간공인 경우의 수 :
  - 2개다 파란공인 경우의 수 :
  - 1개 빨간공, 1개 파란공인 경우의 수 :

3-8. 기출 풀이

2020 중등 2번 가위바위보 확률
2021 중등 4번, 고등 1번 동전과 확률
2022 초등 2번 케이크 도난 사건
- $(p \lor r) \land (\neg p \lor q)$
2023 중등 6번 배수

4. 그래프와 트리

4-1. 왜 KOI에서 중요하나

그래프와 트리는 KOI 이산수학 문제의 구조 파트를 담당한다. 단순 계산 문제가 아니라 “연결”, “도달”, “차수”, “사이클”, “순회”를 읽는 능력을 묻는다.

4-2. 그래프 기초

그래프는 정점(vertex)과 간선(edge)으로 이루어진다.

정점: 점
간선: 점과 점을 잇는 선
차수: 한 정점에 연결된 간선 수
경로: 정점을 따라 이동하는 길
사이클: 출발점으로 되돌아오는 경로

악수 정리

모든 정점 차수의 합은 간선 수의 두 배다.

v \in V \sum de g (v) = 2∣ E ∣

이 식은 그래프 가능 여부를 판정할 때 매우 중요하다.

한붓그리기 조건

연결된 그래프에서 오일러 경로가 존재하려면 홀수 차수 정점의 수가 $0$ 개 또는 $2$ 개여야 한다.

- 한 붓 그리기
  - 평면 그래프를 그릴 때, 모든 선분이 한 번만 그려지도록 하는 것
  - 한붓그리기가 가능한 그래프를 플레이너 그래프(Planar Graph)라고 함
  - 한붓그리기 가능한 조건
    - 그래프의 꼭짓점 중에서 차수가 홀수인 것의 개수가 0 또는 2개일 때, 한붓그리기가 가능. 이를 오일러의 한붓그리기 정리라고 함
  - Q. 다음 도형에서 한붓그리기가 가능한 것을 고르시오
Link to original

4-3. 트리 기초

트리는 사이클이 없고 연결된 그래프다.

트리의 핵심 성질:

∣ E ∣ = ∣ V ∣ - 1

또한 트리에서는 임의의 두 정점 사이의 단순 경로가 정확히 하나다.

이 성질 때문에 거리 계산, 연결점 선택, 순회 문제가 자주 나온다.

4-4. 루트 트리와 순회

트리를 루트가 있는 구조로 보면 부모-자식 관계가 생긴다.

기본 순회:

전위 순회(preorder): 루트 $\to$ 왼쪽 $\to$ 오른쪽
- NLR
중위 순회(inorder): 왼쪽 $\to$ 루트 $\to$ 오른쪽
- LNR
후위 순회(postorder): 왼쪽 $\to$ 오른쪽 $\to$ 루트
- LRN

4-5. BFS와 DFS

BFS

가까운 정점부터 본다.
큐(queue)를 사용한다.
가중치가 없는 그래프의 최단거리와 궁합이 좋다.

DFS

한 방향으로 끝까지 간다.
재귀 또는 스택과 궁합이 좋다.
연결요소, 순회, 백트래킹에 자주 등장한다.

4-6. 최단거리

벨만포드 알고리즘

4-7. 최소 신장 트리

신장 트리는 모든 정점을 연결하면서 사이클이 없는 부분그래프다.

최소 신장 트리(MST)는 그중 간선 가중치 합이 최소인 것이다.

크루스칼 알고리즘:

가중치가 작은 간선부터 본다.
사이클이 생기지 않으면 넣는다.
정점이 모두 연결되면 끝낸다.

4-8. 기출 풀이

정리

시험장에서 바로 쓰는 체크리스트

개수를 묻는가: 곱셈 원리, 조합, 포함배제부터 본다.
몇 번째를 묻는가: 순열, 사전순, 팩토리얼 묶음을 본다.
연결, 경로, 도달을 묻는가: 그래프와 트리로 바꾼다.
push, pop, 순서, 반복 규칙이 보이는가: 스택/큐/시뮬레이션이다.
최소, 최대를 묻는가: 그리디가 되는지, 안 되면 왜 안 되는지 본다.
누가 이기는가를 묻는가: 작은 상태부터 $W / L$ 표를 만든다.
정방향이 너무 복잡한가: 역연산을 본다.

꼭 외울 핵심 공식

진법

(a_{k} a_{k - 1} \dots a_{0})_{b} = i = 0 \sum k a_{i} b^{i}

수열

등차 수열의 합

S n ​ = 2 n (a + l) ​

거듭 제곱의 합

Σ_{k = 1}^{n} k^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}

Σ_{k = 1}^{n} k^{3} = [\frac{n ( n + 1 )}{2}]^{2}

순열과 조합

_{n} P_{r} = \frac{n !}{( n - r )!}, (r n) = \frac{n !}{r ! ( n - r )!}

집합(포함과 배제)

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

논리

P \to Q \equiv \neg P \lor Q

확률

Pr (A) = \frac{∣ A ∣}{∣Ω∣}

한붓그리기

홀수 차수가 0개 또는 2개인 경우만 가능

트리 순회

N(중간) 노드의 위치에 따라 표기
- 전위 - NLR
- 중위 - LNR
- 후위 - LRN
루트 노드에서부터 해당 순번 노드 방문, N(중간)이면 체크

MST - 최소 신장 트리

가중치가 작은 간선부터 확인
사이클이 생기지 않으면 포함
- 1, 2번 반복
정점이 모두 연결되면 끝낸다.

잼코딩 - 용만쌤

Explorer

파이날 특강 자료