2026년 8월 11일 (화) 17:12에 ArduWiki님의 편집

2026-08-11T17:12:29Z

← 이전 판		2026년 8월 12일 (수) 02:12 판
1번째 줄:		1번째 줄:
	{{#seo:\|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이\|title_mode=append\|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2026 KOI, 2026 ~~초등부~~ 2차 대회~~, 거리두기~~, 주사위 탑 쌓기, 간식 분배, 게임, ~~정올 거리두기~~, 정올 주사위 탑 쌓기, 정올 간식 분배, 정올 게임\|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.\|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}		{{#seo:\|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이\|title_mode=append\|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2026 KOI, 2026 중등부 2차 대회, 주사위 탑 쌓기, 간식 분배, 게임, 수열 연산, 정올 주사위 탑 쌓기, 정올 간식 분배, 정올 게임, 정올 수열 연산\|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.\|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}

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


	== '''1. ~~거리두기~~ (초1)''' ==		== '''1. 주사위 탑 쌓기 (초2, 중1)''' ==
	추가 예정		추가 예정

	~~== '''2. 주사위 탑 쌓기 (초2, 중1)''' ==~~
	~~추가 예정~~



	== '''3. 간식 분배 (초3, 중2, 고1)''' ==		== '''2. 간식 분배 (초3, 중2, 고1)''' ==

	=== 📄 문제 개요 ===		=== 📄 문제 개요 ===
189번째 줄:		185번째 줄:
	</syntaxhighlight>		</syntaxhighlight>

	== '''4. 게임 (초4, 중3)''' ==
			== '''3. 게임 (초4, 중3)''' ==
			추가 예정

			== '''4. 수열 연산 (중4)''' ==
	추가 예정		추가 예정

ArduWiki: 새 문서: {{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2026 KOI, 2026 초등부 2차 대회, 거리두기, 주사위 탑 쌓기, 간식 분배, 게임, 정올 거리두기, 정올 주사위 탑 쌓기, 정올 간식 분배, 정올 게임|des...

2026-08-11T17:10:19Z

새 문서: {{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2026 KOI, 2026 초등부 2차 대회, 거리두기, 주사위 탑 쌓기, 간식 분배, 게임, 정올 거리두기, 정올 주사위 탑 쌓기, 정올 간식 분배, 정올 게임|des...

새 문서

{{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2026 KOI, 2026 초등부 2차 대회, 거리두기, 주사위 탑 쌓기, 간식 분배, 게임, 정올 거리두기, 정올 주사위 탑 쌓기, 정올 간식 분배, 정올 게임|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}

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

[[파일:KOISolution.jpg|link=https://arduwiki.com/wiki/%ED%95%9C%EA%B5%AD%EC%A0%95%EB%B3%B4%EC%98%AC%EB%A6%BC%ED%94%BC%EC%95%84%EB%93%9C(KOI)|한국정보올림피아드(KOI) 기출 문제 풀이 모음|center|class=coders100]]

== '''1. 거리두기 (초1)''' ==
추가 예정

== '''2. 주사위 탑 쌓기 (초2, 중1)''' ==
추가 예정

== '''3. 간식 분배 (초3, 중2, 고1)''' ==

=== 📄 문제 개요 ===

* '''목표:''' N명의 학생이 순서대로 방에 들어가서 자신이 좋아하는 간식을 모두 가져갈 때, '''모든 학생이 정확히 1개의 간식만''' 가져가도록 하는 입장 순서를 찾아야 합니다. 불가능하다면 -1을 출력합니다.
* '''제약 조건:''' 학생 수(N)는 최대 200,000명입니다. 단순하게 모든 순서를 다 만들어보는 방식(순열)으로 접근하면 시간 초과가 발생합니다. 수십만 명의 학생을 빠르게 처리하기 위해서는 특정 조건에 맞는 학생들을 쏙쏙 골라내는 효율적인 자료구조가 필요합니다.

=== 💡 문제 풀이 시뮬레이션 ===
가장 눈여겨볼 부분은 '''방에 들어가면 좋아하는 걸 다 가져간다'''는 규칙입니다. 만약 내가 좋아하는 간식이 3개인데 첫 번째로 방에 들어간다면 3개를 모두 가져가게 되어 '''정확히 1개'''라는 조건을 즉시 어기게 됩니다. 그렇다면 '''가장 먼저 방에 들어가야 할 사람'''은 누구일까요? 바로 '''현재 방에 남아있는 간식 중, 좋아하는 간식이 딱 1개뿐인 학생'''입니다. 좋아하는 간식이 1개 초과인 학생은 우선 순위가 될 수 없습니다.

# 현재 좋아하는 간식이 '''딱 1개'''인 학생들을 찾아 줄을 세웁니다. (Queue의 형태)
# 줄 선 학생이 방에 들어가 간식을 가져갑니다.
# 간식이 하나 사라졌으므로, '''그 간식을 좋아했던 다른 학생들의 좋아하는 간식 개수'''가 1개씩 줄어듭니다.
# 간식이 하나 사라지면서 추가로 생긴 '''[좋아하는 간식이 딱 1개가 된 학생]'''을 고려하여 다시 줄을 세웁니다.
# 이 과정을 반복하여 N명이 모두 간식을 가져갔다면 성공, 중간에 멈췄다면 실패(-1)입니다.

과정 자체는 어렵지 않지만 시간 복잡도를 만족하기 위해 자료를 정리해놓는 방식이 중요합니다.

실제 배열들이 어떻게 움직이며 꼬리에 꼬리를 물고 정답을 찾아내는지 '''예제 3번'''을 통해 자세히 추적해 보겠습니다.

'''[예제 3 입력]'''

* N = 4 (학생 4명, 간식 4개)
* 1번 학생 : 3번 간식 선호
* 2번 학생 : 2번 간식 선호
* 3번 학생 : 4, 2, 3번 간식 선호
* 4번 학생 : 1, 2번 간식 선호

우선, 입력을 받으며 4개의 핵심 리스트를 만듭니다.

* cnt : 각 학생이 좋아하는 간식 중 '''남아있는 개수'''
* per : 각 학생이 좋아하는 '''간식 번호 리스트'''
* food : 각 간식을 좋아하는 '''학생 번호 리스트'''
* visit : 각 간식이 '''선택되었는지 여부''' (초기엔 모두 False)

{| class="wikitable" style="text-align: center;"
|-
! 번호(i)
! cnt (남은 간식 수)
! per (좋아하는 간식)
! food (이 간식을 좋아하는 학생들)
|-
| 1
| 1개
| [3]
| 1번 간식: [4]
|-
| 2
| 1개
| [2]
| 2번 간식: [2, 3, 4]
|-
| 3
| 3개
| [4, 2, 3]
| 3번 간식: [1, 3]
|-
| 4
| 2개
| [1, 2]
| 4번 간식: [3]
|}

1~4번 학생 중 좋아하는 간식이 하나 뿐인 학생은 1, 2번 학생입니다.

따라서 '''처음 큐(Queue)의 상태는 [1, 2]'''가 됩니다.

💡 '''[시뮬레이션 진행]'''

▶️ '''1번 학생 입장 (현재 Queue: [2])'''

* '''행동 :''' 1번 학생이 들어가서 '''3번 간식'''을 챙깁니다. (visit[3] = True)
* '''변화 :''' 3번 간식이 사라졌으므로, 3번 간식을 좋아하던 food[3] 리스트의 학생들(1번, 3번)의 cnt를 1씩 줄입니다.
* '''결과 :''' 1번 학생 cnt: 1 → 0, 3번 학생 cnt: 3 → 2 (아직 1개가 아니므로 대기)
* 현재 정답 순서(ans): [1], 대기열(Queue) : []

▶️ '''2번 학생 입장 (현재 Queue: [])'''

* '''행동 :''' 2번 학생이 들어가서 '''2번 간식'''을 챙깁니다. (visit[2] = True)
* '''변화 :''' 2번 간식이 사라졌으므로, 2번 간식을 좋아하던 food[2] 리스트의 학생들(2번, 3번, 4번)의 cnt를 모두 1씩 줄입니다.
* '''결과 :''' 2번 학생 cnt: 1 → 0, 3번 학생 cnt: 2 → 1 '''(1이 되었으니 큐에 추가)''', 4번 학생 cnt: 2 → 1 '''(1이 되었으니 큐에 추가)'''
* 현재 정답 순서(ans): [1, 2], 대기열(Queue) : [3, 4]

▶️ '''3번 학생 입장 (현재 Queue: [4])'''

* '''행동 :''' 3번 학생이 들어가서 남은 간식을 살핍니다. 2번, 3번 간식은 이미 사라졌으므로(visit 배열 확인) '''4번 간식'''만 챙깁니다. (visit[4] = True)
* '''변화 :''' 4번 간식이 사라졌으므로, food[4] 리스트의 학생(3번)의 cnt를 1 줄입니다.
* '''결과 :''' 3번 학생 cnt: 1 → 0
* 현재 정답 순서(ans): [1, 2, 3], 대기열(Queue) : [4]

▶️ '''4번 학생 입장 (현재 Queue: [])'''

* '''행동 :''' 4번 학생이 들어가서 남은 간식을 살핍니다. 2번은 사라졌으므로(visit 배열 확인) '''1번 간식'''만 챙깁니다. (visit[1] = True)
* '''변화 :''' 1번 간식이 사라졌으므로, food[1] 리스트의 학생(4번)의 cnt를 1 줄입니다.
* '''결과 :''' 4번 학생 cnt: 1 → 0
* 현재 정답 순서(ans): [1, 2, 3, 4], 대기열(Queue) : []

총 4명의 학생이 무사히(ans의 길이가 4) 모두 1개씩 간식을 챙겨갔습니다. 따라서 정답은 1 2 3 4가 됩니다.

이 풀이는 그래프 이론의 '''위상 정렬(Topological Sorting)''' 개념을 응용한 것입니다. 순서가 정해져 있는 작업을 차례대로 수행할 때 사용하는 알고리즘으로, 진입 차수(이 문제에서는 좋아하는 간식의 수)가 조건에 맞는 노드(학생)부터 큐(Queue)에 넣어 처리하는 방식입니다. deque를 활용하여 '''O(N + 간식 선호도(C) 총합)'''의 시간 복잡도로 풀이 가능합니다.

=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())

# cnt[i]: i번 학생이 현재 좋아하는 간식 중 남아있는 개수
cnt = [0 for _ in range(N+1)]
# per[i]: i번 학생이 좋아하는 간식들의 리스트
per = [0]
# food[j]: j번 간식을 좋아하는 학생들의 리스트
food = [[] for _ in range(N+1)]
# visit[j]: j번 간식이 누군가에게 선택되었는지 여부
visit = [False for _ in range(N+1)]

# 1. 필요한 데이터 준비
for i in range(1, N+1):
a = list(map(int, input().split()))
cnt[i] = a[0]
per.append(a[1:])
for j in range(1, len(a)):
food[a[j]].append(i) # 이 간식을 좋아하는 학생 기록

# 2. 초기 Queue 생성 : 좋아하는 간식이 1개인 학생들 추가
q = deque()
for i in range(1, N+1):
if cnt[i] == 1:
q.append(i)

ans = []

# 3. 대기열 순회
while q:
c = q.popleft()
if cnt[c] != 1: # cnt가 1이 아니면 모두 1개만 가져간다는 규칙을 어김.
break

ans.append(c) # 정답 순서에 추가

# 해당 학생이 좋아하는 간식(하나를 제외한 나머지는 visit 처리가 되어있음)을 찾아 가져감
for f in per[c]:
if not visit[f]:
visit[f] = True # 간식 가져감 처리

# 이 간식을 좋아했던 다른 학생들의 cnt 감소
for p in food[f]:
cnt[p] -= 1
# 카운트가 1이 된 학생이 있다면 새롭게 큐에 추가
if cnt[p] == 1:
q.append(p)

# 4. 모든 학생이 무사히 간식을 1개씩 가져갔는지 확인
if len(ans) == N:
print(*ans)
else:
print(-1)
</syntaxhighlight>

== '''4. 게임 (초4, 중3)''' ==
추가 예정

2026 한국정보올림피아드(KOI) 2차 대회 중등부 - 편집 역사

2026년 8월 11일 (화) 17:12에 ArduWiki님의 편집