2024 한국정보올림피아드(KOI) 2차 대회 초등부
한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.
1. 보물찾기 (초1)
제목 링크를 통해 문제를 확인해주세요.
📄 문제 개요
다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다. 보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.
다빈이는 다음과 같은 규칙으로 이동합니다.
- 1단계: 제자리(S) 조사
- 2단계: 오른쪽으로 1칸 떨어진 곳(S+1) 조사
- 3단계: 왼쪽으로 1칸 떨어진 곳(S-1) 조사
- 4단계: 오른쪽으로 2칸 떨어진 곳(S+2) 조사
- ...
이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 가장 먼저 보물을 찾게 되는 단계를 구하는 문제입니다.
💡 첫 번째 접근 - 직접 이동해보기
가장 직관적인 방법은 시작 위치(S)부터 한 단계씩 직접 움직여보면서 L 또는 R에 도착하는 상황을 확인하는 것입니다.
예를 들어 왼쪽 보물이 2(L=2), 오른쪽 보물이 9(R=9)에 있고 다빈이가 5(S=5)에서 출발한다고 가정해 보겠습니다.
| 단계 | 이동 방향 | 다빈이의 위치 | 확인 결과 |
|---|---|---|---|
| 1 | 제자리 | 5 | 꽝 |
| 2 | 오른쪽 | 6 (5+1) | 꽝 |
| 3 | 왼쪽 | 4 (5-1) | 꽝 |
| 4 | 오른쪽 | 7 (5+2) | 꽝 |
| 5 | 왼쪽 | 3 (5-2) | 꽝 |
| 6 | 오른쪽 | 8 (5+3) | 꽝 |
| 7 | 왼쪽 | 2 (5-3) | 왼쪽 보물 찾음 |
이렇게 단계(step)를 1씩 늘려가며 짝수일 때는 오른쪽, 홀수일 때는 왼쪽을 확인하다가,
다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다.
💻 코드 구현 - 하나씩 모두 비교하기
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
l, r, s = map(int, input().split())
step = 1
k = 0
while True:
# step이 짝수면 오른쪽(+k), 홀수면 왼쪽(-k)
if step % 2 == 0:
pos = s + k
else:
pos = s - k
# 보물을 찾으면 종료
if pos == l or pos == r:
print(step)
break
# 다음 단계를 위한 설정
step += 1
if step % 2 == 0:
k += 1
이 방식은 구현이 쉽다는 장점이 있지만, 제약 조건에 따라 보물이 시작점으로부터 1억 칸(100,000,000) 떨어져 있다면
반복문도 수억 번을 돌아야 합니다. 따라서 제한 시간 내에 모든 테스트 케이스를 통과하지 못하고 부분 점수(48점)를 받게 됩니다.
💡 두 번째 접근 - 수학적 규칙 찾기
반복문으로 인한 시간 초과를 피하려면 종이 위에서 다빈이의 이동 패턴을 차분하게 수식으로 전개해 보아야 합니다.
| 단계 | 이동 방향 | 다빈이의 위치 | 목표 지점 |
|---|---|---|---|
| 1(홀수) | 제자리 | S | d |
| 2(짝수) | 오른쪽 | S + 1 | R(오른쪽 보물) |
| 3(홀수) | 왼쪽 | S - 1 | L(왼쪽 보물) |
| 4(짝수) | 오른쪽 | S + 2 | R(오른쪽 보물) |
| 5(홀수) | 왼쪽 | S - 2 | L(왼쪽 보물) |
가장 중요한 핵심은 오른쪽, 왼쪽을 번갈아 가며 확인하기 때문에 두 단계를 거쳐야 어느 한 방향으로 한 칸씩 전진이 가능하다는 점입니다.
- 오른쪽 보물(R)을 찾는 규칙
오른쪽으로 1칸 전진하려면 (오른쪽) 👉 2단계 소요
오른쪽으로 2칸 전진하려면 (오른쪽, 왼쪽, 오른쪽) 👉 4단계 소요
오른쪽으로 떨어진 거리(R - S)를 가기 위해서는 두 단계씩 거쳐야 하므로 거리에 2를 곱하면 됩니다. 👉 수식: 2 * (R - S)
- 왼쪽 보물(L)을 찾는 규칙
왼쪽으로 1칸 전진하려면 (오른쪽, 왼쪽) 👉 3단계 소요
왼쪽으로 2칸 전진하려면 (오른쪽, 왼쪽, 오른쪽, 왼쪽) 👉 5단계 소요
항상 오른쪽을 먼저 확인한 뒤 왼쪽을 확인하기 때문에 왼쪽으로 떨어진 거리(S - L)에 2를 곱한 뒤, 처음에 썼던 1단계를 더해주면 됩니다.
👉 수식: 2 * (S - L) + 1
💻 코드 구현 - 카드 번호 처음 등장 위치 메모해두기
t = int(input())
for i in range(t):
l, r, s = map(int, input().split())
r_step = 2 * (r - s) # 오른쪽 보물(R)을 찾는 단계
l_step = 2 * (s - l) + 1 # 왼쪽 보물(L)을 찾는 단계
# 둘 중 더 빨리 찾는(작은) 단계 출력
print(min(r_step, l_step))
이렇게 수학적인 규칙을 찾아 수식을 잘 생각해내었다면 보물이 아주 멀리있더라도 단 한 번의 사칙연산으로 정답을 구할 수 있습니다.
따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 100점을 받을 수 있습니다.
📊 정답률
2차에 진출한 80% 이상의 초등부 학생들이 100점을 받아낸 비교적 난이도가 쉬운 문제였습니다.
100점을 받지 못했더라도 거의 모든 학생들이 48점을 받을 수 있는 풀이는 해낸 모습입니다.
2. 가로등 (초2/중1/고1)
제목 링크를 통해 문제를 확인해주세요.
📄 문제 개요
수직선 도로 위에 N개의 가로등이 켜져 있습니다. 도로의 끝은 L로 아주 깁니다.
어떤 위치의 어두운 정도는 그 위치에서 가장 가까운 가로등까지의 거리를 뜻합니다.
예를 들어 3, 6번 위치에 가로등이 있다면 그림과 같이 가로등이 있는 위치(p=0)을 시작으로 어두운 정도를 표시하게 됩니다.
0부터 L까지 모든 위치의 어두운 정도를 구했을 때, 가장 작은 값부터 K번째로 작은 값까지 차례대로 출력해야 합니다.
💡 첫 번째 접근 - 모든 위치 직접 탐색하기
가장 먼저 떠올릴 수 있는 직관적인 방법은 0부터 L까지 도로 위를 직접 걸어가며, 각 위치마다 모든 가로등과의 거리를 계산해 보는 것입니다.
예를 들어 각 위치(pos)에서 가로등까지의 거리들을 모두 구한 뒤, 그중 가장 짧은 거리가 그 위치의 어두운 정도가 됩니다.
이 값들을 리스트에 모아 오름차순으로 정렬한 뒤 앞에서부터 K개를 출력하는 방식입니다.
💻 코드 구현 - 모든 위치 직접 탐색하기
import sys
input = sys.stdin.readline
l, n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = []
# 0부터 L까지 모든 위치 확인
for pos in range(l + 1):
# 현재 위치에서 모든 가로등과의 거리 중 최솟값(어두운 정도) 찾기
m = 1000000000000000000 # 이론상 가능한 최대 거리
for i in a:
m = min(m, abs(pos - i))
ans.append(m)
ans.sort() # 오름차순 정렬
# 가장 어두운 정도가 작은 K개 출력
for i in range(k):
print(ans[i])
위 코드는 L칸을 일일이 확인하며 N개의 가로등을 매번 비교하므로,
가로등 개수(N)와 도로 길이(L)가 모두 작은 부분문제 2번(N <= 2500, L <= 2500)까지만 무사히 통과하여 20점을 받게 됩니다.
만약 도로 길이가 부분문제 4번(L <= 5,000,000)이나, 사실상 무한하게 커질 수 있는 부분문제 5번의 데이터가 들어오면
이런 방식은 '시간 초과'가 발생할 수밖에 없습니다. 따라서 100점을 받기 위해서는 탐색 방식을 바꾸어야 합니다.
💡 두 번째 접근 - 너비 우선 탐색(BFS)
우리가 출력해야할 것은 가장 밝은(어두운 정도가 가장 낮은) K개의 값입니다.
따라서 가장 밝은 곳(가로등이 있는 위치)부터 영역을 점점 넓혀나가면서 탐색하는 방법을 생각해봅시다.
잔잔한 호수에 돌멩이를 던졌을 때 퍼져나가는 물결을 상상해봅시다.
가로등이 서 있는 위치를 물결의 중심(거리 0)이라고 생각하고, 양옆으로 동시에 1칸씩 영역을 넓혀가는 겁니다.
- 거리 0인 곳: 가로등이 있는 중심 위치들
- 거리 1인 곳: 중심에서 양옆으로 1칸 퍼져나간 위치들
- 거리 2인 곳: 거기서 다시 양옆으로 1칸 더 퍼져나간 위치들
도로의 길이와 무관하게 가장 밝은 곳부터 점점 범위를 넓혀나가다가 가장 밝은 K개 값을 찾는 순간 탐색을 종료합니다.
이처럼 가까운 곳부터 동심원처럼 영역을 넓혀가는 방식을 컴퓨터 공학에서는 너비 우선 탐색(BFS)이라고 부릅니다.
💻 코드 구현 - 너비 우선 탐색(BFS)
l, n, k = map(int, input().split())
# 가로등 위치는 탐색 중 변하지 않으므로, 리스트보다 가볍고 빠른 튜플(tuple) 사용
a = tuple(map(int, input().split()))
# 100경 크기의 방문 배열 대신, 밟은 좌표만 세트(set) 활용 (메모리 초과 방지)
visit = set()
q = deque()
# 1단계: 초기 가로등 위치들을 어두운 정도(거리) 0으로 큐에 모두 삽입, 방문 처리
for i in a:
q.append((i, 0))
visit.add(i)
# 2단계: 딱 K번만 정답을 출력하도록 while 조건 설정
while k > 0:
x, p = q.popleft() # x: 현재 위치, p: 어두운 정도(거리)
# 거리가 짧은 곳부터 순서대로 출력됨
print(p)
k -= 1 # 정답을 출력할 때마다 목표 개수(K)를 1씩 감소
# 3단계: 현재 위치 기준 양옆(왼쪽 1칸, 오른쪽 1칸) 탐색
for cx in [(x - 1), (x + 1)]:
if 0 <= cx <= l: # 도로 범위(0 ~ L) 안에 포함되고
if cx not in visit: # 아직 방문하지 않은 위치라면
visit.add(cx) # 방문 처리한 후
q.append((cx, b + 1)) # 거리를 1 늘려서 큐에 삽입
일반적으로 BFS 코드를 작성할 때, 방문 배열(visit = [False] * (L + 1) 형태)를 활용합니다.
하지만 지금의 경우 L 최대 크기(100경)이 너무 크기 때문에 리스트를 활용하면 메모리 초과가 발생합니다.
그래서 이번에는 set 자료구조를 사용해 우리가 실제로 방문한 좌표만 기록함으로써 메모리 낭비를 최소한으로 처리했습니다.
이렇게 아주 큰 데이터 범위로 인한 몇 가지 함정을 피해서 완성하면, 100점을 획득할 수 있습니다.
📊 정답률
초등부에서는 10% 미만이 100점, 조금이라도 부분점수를 받은 학생은 반 이상이었습니다. 중, 고등부에서는 1번 문제로 출제되어 100점을 받은 학생이 50% 이상, 부분 점수는 대부분 획득한 모습입니다.
아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.
3. 색깔 모으기 (초3/중2)
추가 예정
4. 양손에 V (초4)
추가 예정