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

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

한국정보올림피아드(KOI) 기출 문제 풀이 모음

1. 이웃 (초1)

링크 추가 예정

📄 문제 개요

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

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

1. 같은 학교에 다니고, 집 사이의 거리가 K1 이하일 때
2. 다른 학교에 다니고, 집 사이의 거리가 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)

링크 추가 예정

📄 문제 개요

• 상황: 1번부터 N번까지 번호가 부여된 N명의 사람이 일렬로 서 있습니다. 각 사람은 가위(S), 바위(R), 보(P) 중 하나의 카드를 가집니다.
• 규칙: 인접한 두 사람을 골라 계속해서 대결을 시킵니다. 카드가 다르면 가위바위보 규칙에 따라 승패가 나뉘고, 카드가 같으면 임의로 승자를 정할 수 있습니다. 패자는 퇴장하고 승자만 남습니다.
• 목표: 정확히 N-1번의 대결 후, 각 사람이 최종 단 한 명의 우승자가 될 수 있는지 판별해야 합니다.

💡 문제 풀이 시뮬레이션

주어진 제약조건을 보면 제한시간 1초, 1 <= 사람 수 N <= 200,000 입니다.

따라서 각 사람마다 모든 대결 경우의 수를 다 해보는 것은 시간이 초과될 확률이 매우 높습니다.

발상을 바꾸어 특정 위치의 한 사람이 끝까지 살아남기 위한 조건이 무엇인지 생각해 보아야 합니다.

📌생존 조건

내 위치를 기준으로 왼쪽과 오른쪽 무리를 나누어 생각해봅시다.

왼쪽 무리와 오른쪽 무리를 모두 이길 수 있다면 최종 우승자가 될 수 있습니다.

편의를 위해 나를 이기는 카드는 "천적", 천적을 이겨줄 카드를 "구원자"라고 하겠습니다.

만약 내가 가위라면 천적은 바위, 구원자는 보가 됩니다. 이 때 중요한 포인트는 나는 반드시 구원자를 이긴다는 것입니다.

1. 어느 방향에 천적이 하나도 없다면 그 쪽 방향은 내가 모두 이길 수 있습니다.



2. 어느 방향에 천적이 있더라도 그 쪽에 구원자가 있다면 구원자와 천적을 먼저 싸우게 하여 천적을 없애면 그 쪽 방향을 모두 이길 수 있습니다.

※ 천적이 있는데, 구원자가 없는 경우는 우승할 수 없습니다.

결론적으로 각 위치의 사람을 기준으로 왼쪽 구간과 오른쪽 구간을 각각 확인했을 때, 양쪽 방향 모두 해당 방향에 천적이 없거나, 천적이 있더라도 구원자가 1명 이상 존재한다면 그 사람은 최종 우승자가 될 수 있습니다.

📈 알고리즘 설계

우승을 위한 조건은 확인했지만 여전히 매 사람마다 양쪽 구간의 R, S, P 개수를 처음부터 다시 센다면 시간이 너무 오래 걸립니다.

이런 상황에 적합한 것이 누적합(Prefix Sum)입니다. 처음 한 번만 문자열을 돌면서 지금까지 나온 R, S, P의 개수를 표에 기록해 두는 것입니다.

예시를 통해 정확하게 알아보겠습니다.



① 왼쪽 무리 검사

내가 2번 인덱스에 있으니, 내 왼쪽은 1번의 누적 개수 (1, 0, 1)을 확인해보면 됩니다.

누적 개수를 보면 내 왼쪽에 R이 1개, P가 1개 있습니다. 천적(R)이 있지만 구원자(P)도 존재하기 때문에 왼쪽은 내가 이길 수 있습니다.

② 오른쪽 무리 검사

아래 그림과 같이 (1, 2, 3, 4, 5)라는 수열이 주어졌을 때, 마지막 두 개의 합은

전체 합(파란색 박스) - 구하고자 하는 구간 이전 부분의 합(빨간 박스)로 구할 수 있습니다.



따라서 내 오른쪽 무리(3 ~ 4번 구간)을 파악하는 방법은 전체 누적합(마지막 인덱스)에서 내 위치까지의 누적합을 빼는 것입니다.

전체 누적합 (2, 1, 2)에서 내 위치 누적합 (1, 1, 1)을 빼면 (1, 0, 1)이 되어 내 오른쪽에는 R이 1개, P가 1개 존재한다는 것을 알 수 있습니다.

오른쪽에도 천적(R)이 있지만 구원자(P)도 존재하기 때문에 내가 이길 수 있습니다.

이처럼 누적합을 활용하면 처음에 한 번만 누적합을 계산하고 나면

줄이 아무리 길어도 한 번의 계산(시간 복잡도 O(1))으로 생존 가능성을 파악할 수 있습니다.

💻 코드 구현

import sys
input = sys.stdin.readline

n = int(input())
arr = input().strip()

# 상성 관계 및 인덱스 매핑 테이블
win = {'R': 'S', 'S': 'P', 'P': 'R'}
lose = {'R': 'P', 'S': 'R', 'P': 'S'}
tran = {'R': 0, 'S': 1, 'P': 2}

# 1. 3가지 모양(R, S, P)의 누적합 계산
ps = []
s = [0, 0, 0]
for char in arr:
    s[tran[char]] += 1
    ps.append(tuple(s))

ans = []

# 2. 각 위치별로 우승 가능 여부 판단
for i in range(n):
    me = arr[i]
    loseidx = tran[lose[me]]
    winidx = tran[win[me]]
    
    # [왼쪽 구간 검사] 내 왼쪽에 천적이 없거나, 나를 구해줄 구원자가 있으면 통과
    left_canwin = True
    if i > 0:
        left_lose = ps[i-1][loseidx]
        left_win = ps[i-1][winidx]
        if left_lose == 0 or left_win >= 1:
            left_canwin = True
        else:
            left_canwin = False
        
    # [오른쪽 구간 검사] 내 오른쪽에 천적이 없거나, 나를 구해줄 구원자가 있으면 통과
    right_canwin = True
    if i < n-1:
        right_lose = ps[-1][loseidx] - ps[i][loseidx]
        right_win = ps[-1][winidx] - ps[i][winidx]
        if right_lose == 0 or right_win >= 1:
            right_canwin = True
        else:
            right_canwin = False
        
    # 양방향 모두 안전하게 정리가 가능하다면 우승자가 될 수 있음.
    if left_canwin == True and right_canwin == True:
        ans.append(1)
    else:
        ans.append(0)

for i in ans:
    print(i, end="")

📊 정답률

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

추가 예정