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

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

1. 등교 (초1)

제목 링크를 통해 문제를 확인해주세요.

📄 문제 개요

1부터 N까지의 숫자가 각각 두 번씩 적힌 2N장의 카드가 일렬로 주어졌을 때,

① 같은 숫자가 적힌 두 카드를 한 쌍으로 짝지어

② 두 카드 사이에 놓인 다른 카드의 개수를 계산하고

그 중 두 카드 사이에 있는 카드 개수의 최댓값을 구하는 문제입니다.

문제에 적힌 내용을 조금 더 정확하게 이해해봅시다.

1이 적힌 두 카드 사이에는 차례로 2, 2, 4, 3이 적힌 카드가 있으므로, "1 사이 카드 수"는 4이다.
2가 적힌 두 카드 사이에는 아무 카드도 없으므로, "2 사이 카드 수"는 0이다.
3이 적힌 두 카드 사이에는 1이 적힌 카드만 있으므로, "3 사이 카드 수"는 1이다.
4가 적힌 두 카드 사이에는 차례로 3, 1, 3이 적힌 카드가 있으므로, "4 사이 카드 수"는 3이다.

위 그림을 보면 1과 1 사이 카드가 4장있는 경우가 가장 카드가 많은 경우이므로 정답은 4가 됩니다.

💡 첫 번째 접근 - 하나씩 모두 비교하기

가장 쉽게 먼저 떠오르는 방법은 카드를 하나 잡고 뒤에 있는 카드들을 일일이 뒤집어보며 똑같은 숫자를 찾는 것입니다.

그림을 보면 처음 숫자 1의 위치(인덱스)는 0, 이후 뒤를 찾아보면 5번 위치(인덱스)에 1이 한 번 더 있는 것을 확인할 수 있습니다.

뒤에 숫자 위치(5)에서 처음 숫자 위치(0)을 빼고, 양 끝 숫자가 모두 포함이 안 되기 때문에 1을 한 번 더 빼면 카드의 개수가 나옵니다.

위와 같은 방법으로 코드를 짜보면 다음과 같습니다.

💻 코드 구현 - 하나씩 모두 비교하기

n = int(input())
arr = list(map(int, input().split()))

ans = 0
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번 문제인 만큼 N의 최대 크기가 작기 때문에(1 <= N <= 2000) 이렇게 중첩반복의 형태로 풀어도 100점을 받을 수 있습니다.

하지만 여기에서 N의 범위가 조금만 넓어지게 되면 지금처럼 시간복잡도 O(N^2)의 방법으로는 시간초과가 나올 수 있습니다.

따라서 정보올림피아드에 도전하는 학생들이라면 조금 더 좋은 방법을 생각해볼 필요가 있습니다.

💡 두 번째 접근 - 카드 번호 처음 등장 위치 메모해두기

이번에는 카드를 왔다갔다 여러 번 뒤집지 않고, 카드 번호마다 처음 등장한 위치를 메모해두는 방법입니다.

해당 카드 숫자를 처음 찾았을 때 위치를 메모해두고, 이후에 그 숫자를 다시 찾았을 때는

메모를 보고 숫자 사이에 카드가 몇 개 있었는지 바로 확인할 수 있습니다.

숫자 사이의 카드 개수 = 다시 찾았을 때 위치 - 메모에 기록된 처음 위치 - 1

💻 코드 구현 - 카드 번호 처음 등장 위치 메모해두기

n = int(input())

arr = list(map(int, input().split()))
memo = [-1] * (n+1) # 카드 번호 처음 위치 메모
ans = 0

for i in range(2*n):
    if memo[arr[i]] == -1: # -1: 처음 찾은 숫자
        memo[arr[i]] = i # 처음 찾은 숫자의 위치 메모
    else: # 이미 찾았던 숫자
        ans = max(ans, i - memo[arr[i]] - 1) # 두 위치 사이 카드 개수의 최대값 계산
        
print(ans)

카드 개수는 N개이지만 메모 칸 수를 N+1로 설정했습니다.

원래는 없는 가상의 0번 카드 자리를 만들어 실제 숫자와 인덱스를 똑같이 맞춰주었습니다.

이 방법으로 문제를 풀게 되면 시간 복잡도는 O(N)으로 카드 리스트를 한 바퀴만 돌아도 답을 바로 구해낼 수 있게 됩니다.

실제로 두 방법으로 코드를 제출해보면 어마어마한 시간 차이를 확인할 수 있습니다.

아래 : 첫 번째 접근 방식 / 위 : 두 번째 접근 방식

📊 정답률

2. 두 배 (초2/중1)

제목 링크를 통해 문제를 확인해주세요. 추가 예정

3. 반품 회수 (초3/고1)

추가 예정