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

시각위키텍스트

2026년 5월 29일 (금) 22:38 판

한국 정보올림피아드(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번 학생은 집 위치가 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=" ")

@@ 7번째 줄: / 7번째 줄: @@
 == '''1. 이웃 (초1)''' ==
-링크 추가 예
+링크 추가 예정
-=== '''📄 문제 개요''' ===
+===  ===
-부터 N까지의 숫자가 각각 두 번씩 적힌 2N장의 카드가 일렬로 주어졌을 때,
-① 같은 숫자가 적힌 두 카드를 한 쌍으로 짝지어
+=== 📄 문제 개요 ===
+일직선 도로 위에 N명의 학생이 각각 1번부터 N번 위치의 집에 살고 있습니다.
-② 두 카드 사이에 놓인 다른 카드의 개수를 계산하고
+학생들은 1번 학교 또는 2번 학교 중 하나에 다닙니다. 다음 조건 중 하나를 만족하면 두 학생은 서로 '이웃'이 됩니다.
-그 중 '''두 카드 사이에 있는 카드 개수의 최댓값'''을 구하는 문제입니다.
+# '''같은 학교'''에 다니고, '''집 사이의 거리가 K1 이하'''일 때
+# '''다른 학교'''에 다니고, '''집 사이의 거리가 K2 이하'''일 때
-[[파일:2025KOI먼카드1.png|center|class=coders70]]
+* '''목표:''' 각 학생마다 본인과 '''이웃인 학생의 수'''를 계산하여 차례대로 출력해야 합니다. (단, 자기 자신은 이웃에서 제외합니다.)
-'''문제에 적힌 내용을 조금 더 정확하게 이해해봅시다.'''
-* 1이 적힌 두 카드 사이에는 차례로 2, 2, 4, 3이 적힌 카드가 있으므로, "1 사이 카드 수"는 4이다.
-* 2가 적힌 두 카드 사이에는 아무 카드도 없으므로, "2 사이 카드 수"는 0이다.
-* 3이 적힌 두 카드 사이에는 1이 적힌 카드만 있으므로, "3 사이 카드 수"는 1이다.
-* 4가 적힌 두 카드 사이에는 차례로 3, 1, 3이 적힌 카드가 있으므로, "4 사이 카드 수"는 3이다.
-위 그림을 보면 1과 1 사이 카드가 4장있는 경우가 가장 카드가 많은 경우이므로 정답은 4가 됩니다.
+=== 💡 문제 풀이 시뮬레이션 ===
+알고리즘 문제 풀이에 아직 경험이 적은 초등부 학생들은 학생 한 명마다 나머지 모든 학생을 일일히 확인해도 괜찮은지 판단이 어려울 수 있습니다.
+이때 가장 중요한 것이 바로 '''제약 조건(데이터의 크기, 실행 시간 제한, 메모리 제한 등)을 확인'''하는 것입니다.
-=== '''💡 첫 번째 접근 - 하나씩 모두 비교하기''' ===
+* 문제에서 주어진 학생 수 N의 최댓값은 '''3000'''입니다.
-가장 쉽게 먼저 떠오르는 방법은 카드를 하나 잡고 뒤에 있는 카드들을 일일이 뒤집어보며 똑같은 숫자를 찾는 것입니다.
+* 모든 학생이 서로를 한 번씩 다 확인하는 이중 반복문을 사용하면 총 연산 횟수는 '''N x N''', 즉 최대 '''3000 X 3000 = 9,000,000번'''입니다.
+* 상황에 따라 조금씩 다를 수 있지만 PyPy3를 사용할 때 '''1초에 약 1억 번의 연산'''이 가능하다고 기준을 잡겠습니다.
+* 그렇다면 주어진 실행 시간 제한(2초) 내에 9백만 번의 계산은 거뜬히 수행할 수 있습니다.
-[[파일:2025KOI먼카드2.png|center|class=coders100]]
-그림을 보면 처음 숫자 1의 '''위치(인덱스)는 0''', 이후 뒤를 찾아보면 '''5번 위치(인덱스)'''에 1이 한 번 더 있는 것을 확인할 수 있습니다.
-뒤에 숫자 위치(5)에서 처음 숫자 위치(0)을 빼고, 양 끝 숫자가 모두 포함이 안 되기 때문에 1을 한 번 더 빼면 카드의 개수가 나옵니다.
+따라서 이 문제는 복잡한 알고리즘을 쓸 필요 없이, 이중 반복문을 사용해 '''문제에 적힌 조건을 그대로 정직하게 구현'''하는 방법 사용이 가능합니다.
+예제 1번을 보겠습니다.
+번 학생은 집 위치가 1이며, 1번 학교를 다니고 있습니다.
+이제부터 1번 학생이 되어 2, 3, 4, 5번 학생과 이웃 관계가 맞는지 확인해보겠습니다.
+'''🧑‍🎓 2번 학생'''
+* '''학교:''' 동일함 (1번 학교), '''거리:''' 1 (2 - 1)
+* '''판별 결과:''' 같은 학교 기준 거리인 1 이하이므로 '''이웃 조건 충족 (현재 이웃: 1명)'''
-위와 같은 방법으로 코드를 짜보면 다음과 같습니다.
-=== 💻 '''코드 구현 - 하나씩 모두 비교하기''' ===
-<syntaxhighlight lang="python3" line="1">
-n = int(input())
-arr = list(map(int, input().split()))
-ans = 0
+'''🧑‍🎓 3번 학생'''
-for i in range(2*n): # 카드 전체 돌아보기
-    for j in range(i+1, 2*n): # 현재 위치보다 뒤를 확인
-        if arr[i] == arr[j]: # 같은 숫자를 찾은 경우
-            ans = max(ans, j-i-1) # 숫자 사이 카드 개수의 최대값 계산
-            break
-print(ans)
+* '''학교:''' 동일함 (1번 학교), '''거리:''' 2 (3 - 1)
-</syntaxhighlight>이번 문제는 1번 문제인 만큼 N의 최대 크기가 작기 때문에'''(1 <= N <= 2000)''' 이렇게 중첩반복의 형태로 풀어도 100점을 받을 수 있습니다.
+* '''판별 결과:''' 같은 학교 기준 거리 1을 초과하므로 '''조건 미충족'''
-하지만 여기에서 N의 범위가 조금만 넓어지게 되면 지금처럼 '''시간복잡도 O(N^2)'''의 방법으로는 '''시간초과'''가 나올 수 있습니다.
-따라서 정보올림피아드에 도전하는 학생들이라면 조금 더 좋은 방법을 생각해볼 필요가 있습니다.
+'''🧑‍🎓 4번 학생'''
-=== '''💡 두 번째 접근 - 카드 번호 처음 등장 위치 메모해두기''' ===
+* '''학교:''' 다름 (2번 학교), '''거리:''' 3 (4 - 1)
-이번에는 카드를 왔다갔다 여러 번 뒤집지 않고, 카드 번호마다 처음 등장한 위치를 메모해두는 방법입니다.
+* '''판별 결과:''' 다른 학교 기준 거리인 2를 초과하므로 '''조건 미충족'''
-[[파일:2025KOI먼카드3.png|center|class=coders100]]
-해당 카드 숫자를 처음 찾았을 때 '''위치를 메모'''해두고, 이후에 그 숫자를 다시 찾았을 때는
-메모를 보고 숫자 사이에 카드가 몇 개 있었는지 바로 확인할 수 있습니다.
+'''🧑‍🎓 5번 학생'''
-'''숫자 사이의 카드 개수 = 다시 찾았을 때 위치 - 메모에 기록된 처음 위치 - 1'''
+* '''학교:''' 다름 (2번 학교), '''거리:''' 4 (5 - 1)
+* '''판별 결과:''' 다른 학교 기준 거리 2를 초과하므로 '''조건 미충족'''
-=== 💻 '''코드 구현 - 카드 번호 처음 등장 위치 메모해두기''' ===
-<syntaxhighlight lang="python3" line="1">
-n = int(input())
-arr = list(map(int, input().split()))
-memo = [-1] * (n+1) # 카드 번호 처음 위치 메모
-ans = 0
-for i in range(2*n):
+으로 1번 학생의 이웃은 1명입니다.
-    if memo[arr[i]] == -1: # -1: 처음 찾은 숫자
-        memo[arr[i]] = i # 처음 찾은 숫자의 위치 메모
-    else: # 이미 찾았던 숫자
-        ans = max(ans, i - memo[arr[i]] - 1) # 두 위치 사이 카드 개수의 최대값 계산
-print(ans)
-</syntaxhighlight>카드 개수는 N개이지만 메모 칸 수를 N+1로 설정했습니다.
-원래는 없는 가상의 0번 카드 자리를 만들어 실제 숫자와 인덱스를 똑같이 맞춰주었습니다.
+위와 같은 과정으로 2번 학생은 1, 3, 4, 5번 학생, 3번 학생은 1, 2, 4, 5번 학생 ... 5번 학생까지 모두 확인하면 됩니다.
-이 방법으로 문제를 풀게 되면 '''시간 복잡도는 O(N)'''으로 카드 리스트를 한 바퀴만 돌아도 답을 바로 구해낼 수 있게 됩니다.
+=== 💻 코드 구현 ===
+<syntaxhighlight lang="python3" line="1">
+# n: 전체 학생 수
+# k1: 같은 학교일 때 이웃으로 인정하는 최대 거리
+# k2: 다른 학교일 때 이웃으로 인정하는 최대 거리
+n, k1, k2 = map(int, input().split())
-실제로 두 방법으로 코드를 제출해보면 어마어마한 시간 차이를 확인할 수 있습니다.
+# 학생들의 학교 정보를 리스트로 입력받기
+s = list(map(int, input().split()))
-[[파일:2025KOI먼카드4.png|center|class=coders70]]
+# 주인공 학생(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=" ")
+</syntaxhighlight>
-아래 : 첫 번째 접근 방식 / 위 : 두 번째 접근 방식
-=== 📊 '''정답률''' ===
+=== 📊 정답률 ===
-[[파일:2025KOI먼카드5.png|center|class=coders70]]
+[[파일:2026KOI이웃.png]]
 == '''2. 가위바위보 (초2)''' ==

2026년 5월 29일 (금) 22:38 판

1. 이웃 (초1)

﻿﻿

﻿﻿📄 문제 개요﻿

💡 문제 풀이 시뮬레이션

﻿💻 코드 구현﻿

📊 정답률

2. 가위바위보 (초2)

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

📄 문제 개요

💻 코드 구현