2026 한국정보올림피아드(KOI) 1차 대회 2교시 초등부

한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.

1. 이웃 (초1)

링크 추가 예정

📄 문제 개요

일직선 도로 위에 N명의 학생이 각각 1번부터 N번 위치의 집에 살고 있습니다.

학생들은 1번 학교 또는 2번 학교 중 하나에 다닙니다. 다음 조건 중 하나를 만족하면 두 학생은 서로 '이웃'이 됩니다.

같은 학교에 다니고, 집 사이의 거리가 K1 이하일 때
다른 학교에 다니고, 집 사이의 거리가 K2 이하일 때

목표: 각 학생마다 본인과 이웃인 학생의 수를 계산하여 차례대로 출력해야 합니다. (단, 자기 자신은 이웃에서 제외합니다.)

💡 문제 풀이 시뮬레이션

알고리즘 문제 풀이에 아직 경험이 적은 초등부 학생들은 학생 한 명마다 나머지 모든 학생을 일일히 확인해도 괜찮은지 판단이 어려울 수 있습니다.

이때 가장 중요한 것이 바로 제약 조건(데이터의 크기, 실행 시간 제한, 메모리 제한 등)을 확인하는 것입니다.

문제에서 주어진 학생 수 N의 최댓값은 3000입니다.
모든 학생이 서로를 한 번씩 다 확인하는 이중 반복문을 사용하면 총 연산 횟수는 N x N, 즉 최대 3000 X 3000 = 9,000,000번입니다.
상황에 따라 조금씩 다를 수 있지만 PyPy3를 사용할 때 1초에 약 1억 번의 연산이 가능하다고 기준을 잡겠습니다.
그렇다면 주어진 실행 시간 제한(2초) 내에 9백만 번의 계산은 거뜬히 수행할 수 있습니다.

따라서 이 문제는 복잡한 알고리즘을 쓸 필요 없이, 이중 반복문을 사용해 문제에 적힌 조건을 그대로 정직하게 구현하는 방법 사용이 가능합니다.

예제 1번을 보겠습니다.

학생 번호	1	2	3	4	5
집 위치	1	2	3	4	5
학교	1	1	1	2	2

1번 학생은 집 위치가 1이며, 1번 학교를 다니고 있습니다.

이제부터 1번 학생이 되어 2, 3, 4, 5번 학생과 이웃 관계가 맞는지 확인해보겠습니다.

🧑‍🎓 2번 학생

학교: 동일함 (1번 학교), 거리: 1 (2 - 1)
판별 결과: 같은 학교 기준 거리인 1 이하이므로 이웃 조건 충족 (현재 이웃: 1명)

🧑‍🎓 3번 학생

학교: 동일함 (1번 학교), 거리: 2 (3 - 1)
판별 결과: 같은 학교 기준 거리 1을 초과하므로 조건 미충족

🧑‍🎓 4번 학생

학교: 다름 (2번 학교), 거리: 3 (4 - 1)
판별 결과: 다른 학교 기준 거리인 2를 초과하므로 조건 미충족

🧑‍🎓 5번 학생

학교: 다름 (2번 학교), 거리: 4 (5 - 1)
판별 결과: 다른 학교 기준 거리 2를 초과하므로 조건 미충족

으로 1번 학생의 이웃은 1명입니다.

위와 같은 과정으로 2번 학생은 1, 3, 4, 5번 학생, 3번 학생은 1, 2, 4, 5번 학생 ... 5번 학생까지 모두 확인하면 됩니다.

💻 코드 구현

# n: 전체 학생 수
# k1: 같은 학교일 때 이웃으로 인정하는 최대 거리
# k2: 다른 학교일 때 이웃으로 인정하는 최대 거리
n, k1, k2 = map(int, input().split())

# 학생들의 학교 정보를 리스트로 입력받기
s = list(map(int, input().split()))

# 주인공 학생(i)을 0번부터 N-1번까지 차례대로 선택
for i in range(n):
    ans = 0 # i번째 학생의 이웃 수를 세기 위한 변수 (새로운 주인공마다 0으로 초기화)
    
    # 비교 대상이 될 친구(j)를 0번부터 N-1번까지 차례대로 탐색
    for j in range(n):
        if i == j: # 자기 자신과는 이웃이 될 수 없으므로 건너뜀
            continue
        
        # 두 집 사이의 거리를 절댓값 함수(abs)를 사용하여 계산
        dist = abs(i - j)
        
        # 조건 1: 두 학생이 같은 학교에 다니고, 거리가 k1 이하인 경우
        if s[i] == s[j] and dist <= k1:
            ans += 1 # 이웃 발견
            
        # 조건 2: 두 학생이 다른 학교에 다니고, 거리가 k2 이하인 경우
        elif s[i] != s[j] and dist <= k2:
            ans += 1 # 이웃 발견
            
    # 주인공 학생(i)의 탐색이 끝나면 최종 이웃 수를 출력
    print(ans, end=" ")

📊 정답률

2. 가위바위보 (초2)

추가 예정

3. 수열 정렬하기 (초3, 중2)