2024 한국정보올림피아드(KOI) 2차 대회 중등부
한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.
1. 가로등 (초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점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.
2. 색깔 모으기 (초3/중2)
추가 예정
3. XOR 최대 (중3/고2)
추가 예정
4. 트리 뽑아내기 (중4/고3)
추가 예정