2026 한국정보올림피아드(KOI) 1차 대회 2교시 중등부: 두 판 사이의 차이

시각위키텍스트

2026년 6월 8일 (월) 16:44 판

한국 정보올림피아드(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)

추가 예정

@@ 10번째 줄: / 10번째 줄: @@
 === 📄 문제 개요 ===
+<mark>일직선 도로 위에 N명의 학생이 각각 1번부터 N번 위치의 집에 살고 있습니다.</mark>
+<mark>학생들은 S번 학교 중 하나에 다닙니다. 다음 조건 중 하나를 만족하면 두 학생은 서로 '친구'가 됩니다.</mark>
+# <mark>'''같은 학교에 다니고, 집 사이의 거리가 K1 이하일 때'''</mark>
+# <mark>'''다른 학교에 다니고, 집 사이의 거리가 K2 이하일 때'''</mark>
+* <mark>'''목표:''' 각 학생마다 본인과 '''친구인 학생의 수'''를 계산하여 차례대로 출력해야 합니다. (단, 자기 자신은 이웃에서 제외합니다.)</mark>
+<mark>2026년도 1차대회 초등부 1번 "이웃" 문제와 내용은 거의 동일한 문제입니다.</mark>
+<mark>하지만 문제에 주어진 제약 조건의 차이가 커 난이도가 많이 높아졌습니다.</mark>
+<mark>'''1. 매우 커진 데이터 크기 (N)'''</mark>
+* <mark>'''초등부:''' 학생 수 N은 3,000 이하. (이중 반복문 사용 시 최대 900만 번 연산 ➔ 1초 내 통과)</mark>
+* <mark>'''중등부:''' 학생 수 N은 500,000 이하. (이중 반복문 사용 시 최대 '''2,500억 번 연산''' ➔ 시간 초과 발생)</mark>
+<mark>'''2. 학교의 개수 확장'''</mark>
+* <mark>'''초등부:''' 학교가 단 2개로 고정</mark>
+* <mark>'''중등부:''' 학교 번호가 최대 N개까지 주어질 수 있습니다. 최악의 경우 50만 개의 서로 다른 학교가 존재할 수 있어 데이터를 학교별로 효율적으로 그룹화하는 작업이 필요합니다.</mark>
 == '''2. 수열 정리하기 (초3/중2)''' ==