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만 개의 서로 다른 학교가 존재할 수 있어 데이터를 학교별로 효율적으로 그룹화하는 작업이 필요합니다.
2. 수열 정리하기 (초3/중2)
추가 예정
3. 산책로 (중3/고2)
추가 예정