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

2026-08-11T17:09:33Z

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


	=== 💡 문제 풀이 시뮬레이션 ===		=== 💡 문제 풀이 시뮬레이션 ===

ArduWiki: /* 2. 주사위 탑 쌓기 (초2, 중1) */

2026-08-11T17:08:56Z

2. 주사위 탑 쌓기 (초2, 중1)

← 이전 판		2026년 8월 12일 (수) 02:08 판
10번째 줄:		10번째 줄:

	== '''2. 주사위 탑 쌓기 (초2, 중1)''' ==		== '''2. 주사위 탑 쌓기 (초2, 중1)''' ==
	~~'''제목 링크를 통해 문제를 확인해주세요.'''~~		추가 예정

ArduWiki: /* 3. 간식 분배 (초3, 중2, 고1) */

2026-08-11T17:08:32Z

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

← 이전 판		2026년 8월 12일 (수) 02:08 판
52번째 줄:		52번째 줄:

	{\| class="wikitable" style="text-align: center;"		{\| class="wikitable" style="text-align: center;"
	\|- ~~style="background-color: #f8f9fa;"~~		\|-
	\| 번호(i)		! 번호(i)
	\| cnt (남은 간식 수)		! cnt (남은 간식 수)
	\| per (좋아하는 간식)		! per (좋아하는 간식)
	\| food (이 간식을 좋아하는 학생들)		! food (이 간식을 좋아하는 학생들)
	\|-		\|-
	\| 1		\| 1
186번째 줄:		186번째 줄:
	print(-1)		print(-1)
	</syntaxhighlight>		</syntaxhighlight>


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

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

2026-08-11T17:07:43Z

← 이전 판		2026년 8월 12일 (수) 02:07 판
51번째 줄:		51번째 줄:
	* visit : 각 간식이 '''선택되었는지 여부''' (초기엔 모두 False)		* visit : 각 간식이 '''선택되었는지 여부''' (초기엔 모두 False)

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

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

2026-08-11T17:06:17Z

차이 보기

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

2026-08-11T17:01:38Z

새 문서: {{#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]]

== '''[https://coj.ac/problems/2138 1. 장애물 (초1)]''' ==
제목 링크를 통해 문제를 확인해주세요.

=== 📄 문제 개요 ===
수직선 위 위치 0에서 출발하여 N개의 장애물을 모두 뛰어넘어야 합니다.

* '''행동 1:''' 오른쪽으로 1만큼 걸어간다.
* '''행동 2:''' 오른쪽으로 2만큼 점프한다.
* '''장애물 넘기 규칙:''' 위치 X에 있는 장애물을 넘으려면, '''반드시 위치 X-1에서 점프하여 위치 X+1에 도착'''해야 합니다.

주어진 규칙을 활용해 '''모든 장애물을 넘기 위한 최소 이동 횟수'''를 구하고, 만약 넘는 것이 불가능하다면 '''-1'''을 출력하는 문제입니다.[[파일:2025KOI장애물1.png|center|class=coders100]]위 그림과 같이 한 칸, 혹은 두 칸을 움직여 최종적으로는 최소한의 움직임으로 모든 장애물을 넘어야 합니다.

=== 💡 첫 번째 접근 - 문제 조건대로 하나씩 이동해보기 (Greedy) ===
가장 확실하고 직관적인 방법은 캐릭터가 직접 이동하는 과정을 코드로 시뮬레이션해 보는 것입니다.

목적지(다음 장애물 앞 칸)까지 가장 적게 이동하려면 자연스럽게 1칸 걷기보다는 '''2칸 점프를 최대한 많이 활용'''해야 합니다.

일단 이후는 생각하지 않고, '''현재 주어진 위치에서 최대한 앞으로 나가려고 하면''' 자연스럽게 정답에 도달할 수 있는 문제입니다.

이처럼 지금 당장 눈앞에 보이는 가장 효율적인 선택을 먼저 취하는 방식을 컴퓨터 공학에서는 '''<nowiki/>'그리디(Greedy, 탐욕) 알고리즘''''이라고 부릅니다.

[[파일:2025KOI장애물1.png|center|class=coders100]]

* '''0 위치:''' 2칸 앞에 장애물이 있어 2칸을 가지 못하기 때문에 '''1칸 이동(0 → 1)'''
* '''1 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(1 → 3)'''
* '''3 위치:''' 2칸 앞에 장애물이 있어 2칸을 가지 못하기 때문에 '''1칸 이동(3 → 4)'''
* '''4 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(4 → 6)'''
* '''6 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(6 → 8)'''
* '''8 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(8 → 10)'''
* '''10 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(10 → 12), 모든 장애물 극복 완료'''

단, '''장애물 두 개가 붙어있는 경우'''(1칸 앞, 2칸 앞에 모두 장애물이 있는 경우)에는 장애물을 넘지 못한다는 사실을 기억해둡시다.

=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n = int(input())
arr = list(map(int, input().split()))

last = arr[-1] # 마지막 장애물 위치
x = [0] * (last + 2) # 장애물 위치 기록 / 마지막 장애물을 넘는 것을 고려하여 한 칸 넉넉하게
for i in arr:
x[i] = 1

s = 0 # 현재 위치
ans = 0
while s < last: # 현 위치가 마지막 장애물보다 앞에 있는 동안
if x[s+2] == 0: # 2칸 앞에 장애물이 없다면 2칸 전진
s += 2
elif x[s+1] == 0: # 1칸 앞에 장애물이 없다면 1칸 전진
s += 1
else: # 2칸 앞, 1칸 앞에 모두 장애물이 있으면 불가능
ans = -1
break
ans += 1

print(ans)
</syntaxhighlight>이번 문제의 장애물 사이의 거리, 장애물의 개수가 최대 250,000이므로

이렇게 반복문으로 하나하나 시뮬레이션해도 시간초과 없이 안정적으로 100점을 받을 수 있습니다.

=== 💡 두 번째 접근 - 수학적 접근 ===
두 번째 방법은 이동해야할 거리에 따른 횟수를 수학적으로 계산하는 것입니다.

i위치에서 j까지 이동할 때, 두 지점 거리(d)는 j - i 입니다.

이동할 때 최대한 '''2칸 점프를 많이 활용'''해야하기 때문에 가능한 만큼 먼저 점프를 활용합니다. (d // 2)

만약 도달하지 못하고 1칸이 남았다면 1칸 걷기를 더해 마무리합니다. (d % 2)

d % 2 값은 0 또는 1이기 때문에 2칸 점프로만 원하는 지점에 도착했더라도 '''최소 이동 횟수는 d // 2 + d % 2'''로 계산할 수 있습니다.

[[파일:2025KOI장애물2.png|center|class=coders100]]위에서 계산한 방식에 따라

'''[0 → 1(+1)] + 장애물 뛰어넘기(+1) + [3 → 4(+1)] + 장애물 뛰어넘기(+1) + [6 → 10(+2)] + 장애물 뛰어넘기(+1) = 7'''

이 정답이 되는 것을 확인할 수 있습니다. 장애물을 넘지 못하는 조건은 동일합니다.

=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n = int(input())
obs = list(map(int, input().split()))

s = 0 # 현재 위치
ans = 0

for i in obs:
# 장애물이 연속으로 붙은 경우 예외 처리
if i - 1 < s:
print(-1)
exit()

d = (i - 1) - s # 내 위치부터 다음 장애물 앞 칸까지 남은 거리
ans += d / 2 + d % 2 # 최소 이동 횟수 누적

# 장애물 뛰어넘기
ans += 1
s = i + 1

print(ans)
</syntaxhighlight>이번 문제의 경우 장애물 사이의 거리가 25만 칸으로 첫 번째 접근, 두 번째 접근의 시간 차이가 미미한 수준입니다.

하지만 '''장애물 사이의 거리가 10억 칸'''으로 늘어난다면 반복문으로 최대 2칸씩 이동하는 방법은 시간이 아주 오래 걸리게 됩니다.

이런 경우 지금처럼 '''수학적인 접근'''으로 계산 횟수를 줄여주는 것이 필요합니다.

== '''[https://coj.ac/problems/2139 2. 거울 (초2/중1)]''' ==
제목 링크를 통해 문제를 확인해주세요.

=== 📄 문제 개요 ===
수직선 위의 위치 s에서 출발하는 캐릭터가 있습니다. 그리고 수직선 위에는 N개의 거울이 놓여 있습니다.

* '''이동 규칙:''' 위치 a에 있는 캐릭터가 위치 b에 있는 거울을 사용하면, 거울을 기준으로 점대칭인 지점인 '''2b - a''' 위치로 이동하게 됩니다.
* '''조건:''' N개의 거울을 '''원하는 순서대로 정확히 한 번씩 모두 사용'''해야 합니다.

이 조건하에서 캐릭터가 최종적으로 도착할 수 있는 위치의 '''최댓값'''을 구하는 문제입니다.

[[파일:2025KOI거울1.png|center|class=coders100]]'''문제에 적힌 내용을 조금 더 정확하게 이해해봅시다.'''

거울 사용시 위치를 문제에서 2b- a로 제시해주었고, 그림을 통해 확인해보면 다음과 같습니다.

* '''시작 위치 0에서 1번 거울 사용: -2''' 위치로 이동 (2b-a = 2 x (-1) - 0 = -2)
* '''-1 위치에서 2번 거울 사용: 6 위치'''로 이동 (2b-a = 2 x 2 - (-2) = 6)

위와 동일한 방식으로 2번 거울을 먼저 사용하고 1번 거울을 사용하면 캐릭터 최종 위치는 -6이 됩니다.

따라서 캐릭터 위치의 최대값은 1번 거울을 먼저 사용했을 때의 6이 됩니다.

=== 💡 첫 번째 접근 - 모든 순서를 다 해보기? ===
가장 쉽게 떠오르는 방법은 어떤 거울을 먼저 쓸지 '''모든 순서를 다 바꿔가며 계산'''해 보는 것입니다.

이렇게 가능한 모든 경우의 수를 빠짐없이 전부 탐색하는 방식을 컴퓨터 공학 용어로 '''브루트포스(Brute-force, 완전 탐색)'''라고 부릅니다.

첫 번째 예제처럼 거울이 2개일 때는 '''(1번 거울 → 2번 거울), (2번 거울 → 1번 거울)''' 두 가지 경우만 계산해서 더 큰 값을 고르면 됩니다.

하지만 이 문제의 제약 조건을 살펴보면 거울의 수 N은 최대 '''200,000개'''입니다.

20만 개의 거울을 나열하는 경우의 수는 200,000!으로 슈퍼컴퓨터로도 제한 시간(1초) 내에 절대 계산할 수 없는 엄청난 숫자입니다.

따라서 이러한 접근 방식으로 코드를 작성했다면 '''시간초과'''로 인해 '''부분문제 1. N은 2 이하''' 에 해당하는 7점만 획득할 수 있습니다.

=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n, s = map(int, input().split())
arr = list(map(int, input().split()))

if n == 1:
print(2 * arr[0] - s)
elif n == 2:
# 경우 1: 1번 거울 -> 2번 거울 순서
pos1 = 2 * arr[1] - (2 * arr[0] - s)

# 경우 2: 2번 거울 -> 1번 거울 순서
pos2 = 2 * arr[0] - (2 * arr[1] - s)

# 둘 중 더 큰 값을 출력
print(max(pos1, pos2))
</syntaxhighlight>실전에서는 긴장감과 시간 압박 때문에, 평소에는 금방 찾아내던 수학적 규칙도 머릿속이 하얗게 변해 안 떠오를 때가 많습니다.

1년에 한 번 뿐인 대회, 그냥 포기하는 것보다는 내가 풀 수 있는 부분문제를 끈기있게 찾아내어 7점을 더 얻어내는 집념을 가져보세요.

[[파일:2025KOI거울3.png|center|class=coders100|3점 차이로 내가 받을 상이 달라질 수 있다]]

이렇게 단 몇 점 차이로 내가 받는 상이 달라질 수 있습니다.

정보올림피아드는 100점을 맞아야만 상을 받는 대회가 아닙니다.

이런 집념을 가지고 임하는 학생에게 다음 대회에서 더 좋은 아이디어가 피어날 것이라 믿습니다.

=== 💡 두 번째 접근 - 수학적 규칙 찾기 ===
컴퓨터가 모든 경우를 계산할 수 없다면, 우리가 직접 종이 위에서 수식의 패턴을 찾아내야 합니다.

거울을 차례대로 사용했을 때 위치가 어떻게 변하는지 수식으로 써보면 다음과 같습니다.

[[파일:2025KOI거울2.png|center|class=coders100]]수식을 유심히 살펴보면 아주 중요한 규칙들을 발견할 수 있습니다.

# 초기 위치 s는 거울의 개수가 짝수면 더해지고'''(+s)''', 홀수면 빼집니다'''(-s)'''.
# 선택한 거울의 위치(m)에는 항상 '''+2''' 또는 '''-2'''가 곱해집니다.

우리의 목표는 '''최종 위치의 값을 최대'''로 만드는 것입니다.

그렇다면 어떤 거울에 '''+2'''를 곱하고, 어떤 거울에 '''-2'''를 곱해야 결과가 가장 커질까요?

당연히 '''위치가 큰 거울들을 골라 더해주고, 위치가 작은 거울들을 골라 빼주면''' 됩니다.

문제에서 거울의 위치는 이미 오름차순으로 정렬되어 주어지기 때문에 '''중간을 기준'''으로 '''왼쪽, 오른쪽의 합'''을 계산하면 됩니다.

단, 홀수 위치일 때 보면 더해지는 쪽이 하나 더 많기 때문에 '''중간 위치는 오른쪽 합에 포함'''됩니다.

=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n, s = map(int, input().split())
m = list(map(int, input().split())) # 거울
half = n // 2 # 거울 개수의 반

# 중간 위치는 큰 쪽에 포함
small = sum(m[:half]) # 작은 값들의 합
large = sum(m[half:]) # 큰 값들의 합

if n % 2 == 0: # 거울 개수가 짝수일 때는 +s
print(2 * large - 2 * small + s)
else: # 거울 개수가 홀수일 때는 -s
print(2 * large - 2 * small - s)
</syntaxhighlight>

반복이 아니라 단순 연산으로 계산하기 때문에 거울의 개수가 20만 개라도 시간 내에 처리가 가능(100점)합니다.

== '''3. 통행료 (초3)''' ==

추가 예정

== '''4. 상자 보관 (초4)''' ==
추가 예정

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

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

ArduWiki: /* 2. 주사위 탑 쌓기 (초2, 중1) */

ArduWiki: /* 3. 간식 분배 (초3, 중2, 고1) */

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

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