2026 한국정보올림피아드(KOI) 1차 대회 2교시 중등부
한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.
1. 이웃 (중1/고1)
링크 추가 예정
📄 문제 개요
일직선 도로 위에 N명의 학생이 각각 1번부터 N번 위치의 집에 살고 있습니다.
학생들은 S번 학교 중 하나에 다닙니다. 다음 조건 중 하나를 만족하면 두 학생은 서로 '친구'가 됩니다.
- 같은 학교에 다니고, 집 사이의 거리가 K1 이하일 때
- 다른 학교에 다니고, 집 사이의 거리가 K2 이하일 때
- 목표: 각 학생마다 본인과 친구인 학생의 수를 계산하여 차례대로 출력해야 합니다. (단, 자기 자신은 이웃에서 제외합니다.)
2026년도 1차대회 초등부 1번 "이웃" 문제와 내용은 거의 동일한 문제입니다.
하지만 문제에 주어진 제약 조건의 차이가 커 난이도가 많이 높아졌습니다.
1. 매우 커진 데이터 크기 (N)
- 초등부: 학생 수 N은 3,000 이하. (이중 반복문 사용 시 최대 900만 번 연산 ➔ 1초 내 통과)
- 중등부: 학생 수 N은 500,000 이하. (이중 반복문 사용 시 최대 2,500억 번 연산 ➔ 시간 초과 발생)
2. 학교의 개수 확장
- 초등부: 학교가 단 2개로 고정
- 중등부: 학교 번호가 최대 N개까지 주어질 수 있습니다. 최악의 경우 50만 개의 서로 다른 학교가 존재할 수 있어 데이터를 학교별로 효율적으로 그룹화하는 작업이 필요합니다.
💡 문제 풀이 시뮬레이션
초등부 문제 풀이처럼 N명의 학생 각각을 나머지 모든 학생들과 거리를 재어 친구 수를 센다면 시간이 부족합니다.
초등부 문제 풀이가 궁금하신 분들은 아래 링크를 참고해주세요.
2026 한국정보올림피아드(KOI) 1차 대회 2교시 초등부 1번 이웃 문제 풀이 보러가기
이번 문제의 핵심은 필요한 구간의 개수만 파악하는 것입니다.
이를 위해서 주어진 자료의 구조를 잘 설계하여 활용하는 것이 중요합니다.
문제에 주어진 예제1 입력을 보겠습니다.
| 예제1 입력 |
|---|
| 7 3 5 9 2 1 1 14 3 6 2 17 3 4 1 8 1 |
7명의 학생이 주어지며, K1 = 3, K2 = 5 입니다.
아래로는 각 학생들의 집 위치, 학교 번호가 주어집니다.
주어진 자료들을 정리해보면 아래와 같습니다.
이제 정리한 자료들을 가지고 각 학생들의 친구가 몇 명인지 효율적으로 확인해보겠습니다.
친구의 조건은 다음과 같습니다.
- 같은 학교에 다니고, 집 사이의 거리가 K1 이하일 때
- 다른 학교에 다니고, 집 사이의 거리가 K2 이하일 때
우리는 이미 학교별로 어느 학생들이 소속되어있는지 자료에 정리해두었습니다.
따라서 같은 학교에 다니는 학생들의 정보를 활용하는 것이 편하기 때문에 다음과 같이 계산해보겠습니다.
(1번 조건)
* C = 같은 학교 학생 중 기준 학생과 집 사이의 거리가 K1 이하인 인원 수
기준 학생의 위치를 xi라고 할 때, 같은 학교 학생 중 xi - K1 이상, xi + K1 이하 범위에 위치한 학생 수를 찾아야 합니다.
(2번 조건)
* A = 전체 학생들 중 기준 학생과 집 사이의 거리가 K2 이하인 인원 수
기준 학생의 위치를 xi라고 할 때, 모든 학생들의 위치가 정리된 리스트에서 xi - K2 이상, xi + K2 이하 범위에 위치한 학생 수를 찾습니다.
* B = 같은 학교 학생 중 기준 학생과 집 사이의 거리가 K2 이하인 인원 수
기준 학생의 위치를 xi라고 할 때, 같은 학교 학생 중 xi - K2 이상, xi + K2 이하 범위에 위치한 학생 수를 찾습니다.
실제 조건은 다른 학교를 기준으로 하기 때문에 전체(A)에서 같은 학교(B)를 뺀 값이 2번 조건을 만족하는 결과가 됩니다.
1번 조건과 2번 조건을 종합해보면 친구 수는 C + (A-B)이고, 계산 과정에서 나 자신이 포함되므로 1를 빼주어야 합니다.
※ 최종 : C + (A-B) - 1
📌이분 탐색의 활용
우리가 찾아야 하는 것은 특정 값 하나가 아니라, xi - K부터 xi + K라는 특정 범위 안에 속한 데이터의 개수입니다.
예를 들어 [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5] 와 같은 자료가 주어졌을 때 2 이상 4 이하 범위의 데이터 개수는
(4를 처음으로 넘는 위치) - (2가 처음으로 나오는 위치)로 계산할 수 있습니다.
정렬된 데이터에서 특정 값을 빠르게 찾기 위해 사용할 수 있는 알고리즘이 바로 이분 탐색(binary search)입니다.
정렬된 데이터의 중앙 값을 목표 값과 비교하면서 탐색 범위를 절반씩 줄여나가는 효율적인 방법입니다.
한 번 계산마다 탐색 범위가 절반이 되기 때문에 시간 복잡도는 O(logN) 입니다.
우리도 미리 정리해둔 자료들(전체 학생 위치, 학교별 학생 위치)을 오름차순으로 정렬해 둔다면 어떨까요?
똑같이 (xi + K를 처음으로 넘는 위치) - (xi - K가 처음으로 나오는 위치)로 친구 수를 계산할 수 있게 됩니다.
💻 코드 구현
n, k1, k2 = map(int, input().split())
school = [[] for _ in range(n+1)] # 각 학교별 학생들의 집 위치를 저장할 2차원 리스트
x = [] # 출력 순서를 유지하기 위한 원본 데이터 리스트 (위치, 학교)
xa = [] # 전체 학생들의 집 위치만 저장할 리스트
for i in range(n):
xi, si = map(int, input().split())
school[si].append(xi)
x.append((xi, si))
xa.append(xi)
xa.sort() # 1. 전체 학생 위치 오름차순 정렬
for i in school:
i.sort() # 2. 각 학교별 학생 위치 오름차순 정렬
# 하한선(Lower Bound): 찾고자 하는 값(g) '이상'이 처음 나타나는 위치
def lower(arr, g):
left = 0
right = len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] < g:
left = mid + 1
else:
right = mid - 1
return left
# 상한선(Upper Bound): 찾고자 하는 값(g)을 '초과'하는 값이 처음 나타나는 위치
def upper(arr, g):
left = 0
right = len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] <= g:
left = mid + 1
else:
right = mid - 1
return left
for i, s in x: # i는 기준 학생 위치, s는 기준 학생 학교 번호
# C: 같은 학교 학생 중 나와 거리가 K1 이하인 인원 수
C = upper(school[s], i + k1) - lower(school[s], i - k1)
# A: 전체 학생 중 나와 거리가 K2 이하인 인원 수
A = upper(xa, i + k2) - lower(xa, i - k2)
# B: 같은 학교 학생 중 나와 거리가 K2 이하인 인원 수
B = upper(school[s], i + k2) - lower(school[s], i - k2)
# 최종 공식: 같은학교 K1 + (전체 K2 - 같은학교 K2) - 자기 자신(1)
print(C + (A - B) - 1, end=" ")
파이썬의 경우 bisect 라이브러리를 활용하면 쉽게 이분 탐색을 할 수 있지만, 프로그래밍을 공부하는 학생 여러분들은 일반적인 이분 탐색과 함께 지금 활용한 Upper bound, Lower bound까지 다양하게 직접 구현하는 연습을 해보시기 바랍니다.
📊 정답률
2. 수열 정리하기 (초3/중2)
추가 예정
3. 산책로 (중3/고2)
추가 예정