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

ArduWiki: /* 2. 가로등 (초2/중1/고1) */

2026-04-20T07:27:03Z

2. 가로등 (초2/중1/고1)

← 이전 판		2026년 4월 20일 (월) 16:27 판
311번째 줄:		311번째 줄:
	이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.		이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.



	~~=== 📊 정답률 ===~~
	~~초등부에서는 10% 미만이 100점, 조금이라도 부분점수를 받은 학생은 반 이상이었습니다.~~

	~~중, 고등부에서는 1번 문제로 출제되어 100점을 받은 학생이 50% 이상, 부분 점수는 대부분 획득한 모습입니다.~~

	~~아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.~~

ArduWiki: /* 📊 정답률 */

2026-04-15T12:57:51Z

📊 정답률

← 이전 판		2026년 4월 15일 (수) 21:57 판
315번째 줄:		315번째 줄:
	=== 📊 정답률 ===		=== 📊 정답률 ===
	초등부에서는 10% 미만이 100점, 조금이라도 부분점수를 받은 학생은 반 이상이었습니다.		초등부에서는 10% 미만이 100점, 조금이라도 부분점수를 받은 학생은 반 이상이었습니다.

	중, 고등부에서는 1번 문제로 출제되어 100점을 받은 학생이 50% 이상, 부분 점수는 대부분 획득한 모습입니다.		중, 고등부에서는 1번 문제로 출제되어 100점을 받은 학생이 50% 이상, 부분 점수는 대부분 획득한 모습입니다.

ArduWiki: /* 1. 보물찾기 (초1) */

2026-04-15T12:57:35Z

1. 보물찾기 (초1)

← 이전 판		2026년 4월 15일 (수) 21:57 판
9번째 줄:		9번째 줄:
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.

			📄 문제 개요
	~~=== 📄~~ 문제 개요 ~~===~~
	다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.		다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.
	보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.		보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.
195번째 줄:		195번째 줄:
	== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==		== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.


	=== 📄 문제 개요 ===		=== 📄 문제 개요 ===
319번째 줄:		318번째 줄:

	아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.		아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.


	== '''3. 색깔 모으기 (초3/중2)''' ==		== '''3. 색깔 모으기 (초3/중2)''' ==

2026년 4월 15일 (수) 12:57에 ArduWiki님의 편집

2026-04-15T12:57:00Z

← 이전 판		2026년 4월 15일 (수) 21:57 판
10번째 줄:		10번째 줄:



	=== 📄 문제 개요 ===		=== 📄 문제 개요 ===
	다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.		다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.
196번째 줄:		195번째 줄:
	== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==		== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.

ArduWiki: /* 2. 가로등 (초2/중1/고1) */

2026-04-15T12:56:42Z

2. 가로등 (초2/중1/고1)

← 이전 판		2026년 4월 15일 (수) 21:56 판
198번째 줄:		198번째 줄:





	=== 📄 문제 개요 ===		=== 📄 문제 개요 ===
211번째 줄:		209번째 줄:

	0부터 L까지 모든 위치의 어두운 정도를 구했을 때, '''가장 작은 값부터 K번째로 작은 값'''까지 차례대로 출력해야 합니다.		0부터 L까지 모든 위치의 어두운 정도를 구했을 때, '''가장 작은 값부터 K번째로 작은 값'''까지 차례대로 출력해야 합니다.




318번째 줄:		314번째 줄:
	이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.		이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.



	=== 📊 정답률 ===		=== 📊 정답률 ===
324번째 줄:		321번째 줄:

	아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.		아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.


	== '''3. 색깔 모으기 (초3/중2)''' ==		== '''3. 색깔 모으기 (초3/중2)''' ==

2026년 4월 15일 (수) 12:56에 ArduWiki님의 편집

2026-04-15T12:56:11Z

← 이전 판		2026년 4월 15일 (수) 21:56 판
206번째 줄:		206번째 줄:
	어떤 위치의 '''어두운 정도'''는 그 위치에서 '''가장 가까운 가로등까지의 거리'''를 뜻합니다.		어떤 위치의 '''어두운 정도'''는 그 위치에서 '''가장 가까운 가로등까지의 거리'''를 뜻합니다.

	[[파일:2024KOI가로등1.png]]		[[파일:2024KOI가로등1.png\|center\|class=coders100]]

	예를 들어 3, 6번 위치에 가로등이 있다면 그림과 같이 가로등이 있는 위치(p=0)을 시작으로 어두운 정도를 표시하게 됩니다.		예를 들어 3, 6번 위치에 가로등이 있다면 그림과 같이 가로등이 있는 위치(p=0)을 시작으로 어두운 정도를 표시하게 됩니다.
221번째 줄:		221번째 줄:
	예를 들어 각 위치(pos)에서 가로등까지의 거리들을 모두 구한 뒤, 그중 가장 짧은 거리가 그 위치의 어두운 정도가 됩니다.		예를 들어 각 위치(pos)에서 가로등까지의 거리들을 모두 구한 뒤, 그중 가장 짧은 거리가 그 위치의 어두운 정도가 됩니다.

	[[파일:2024KOI가로등2.png]]		[[파일:2024KOI가로등2.png\|center\|class=coders100]]

	이 값들을 리스트에 모아 오름차순으로 정렬한 뒤 앞에서부터 K개를 출력하는 방식입니다.		이 값들을 리스트에 모아 오름차순으로 정렬한 뒤 앞에서부터 K개를 출력하는 방식입니다.
279번째 줄:		279번째 줄:
	이처럼 가까운 곳부터 동심원처럼 영역을 넓혀가는 방식을 컴퓨터 공학에서는 '''너비 우선 탐색(BFS)'''이라고 부릅니다.		이처럼 가까운 곳부터 동심원처럼 영역을 넓혀가는 방식을 컴퓨터 공학에서는 '''너비 우선 탐색(BFS)'''이라고 부릅니다.

	[[파일:2024KOI가로등3.png]]		[[파일:2024KOI가로등3.png\|center\|class=coders100]]

	=== 💻 코드 구현 - 너비 우선 탐색(BFS) ===		=== 💻 코드 구현 - 너비 우선 탐색(BFS) ===
317번째 줄:		317번째 줄:

	이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.		이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.



326번째 줄:		325번째 줄:
	아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.		아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.

	~~=== ===~~

	== '''3. 색깔 모으기 (초3/중2)''' ==		== '''3. 색깔 모으기 (초3/중2)''' ==

ArduWiki: /* 2. 가로등 (초2/중1/고1) */

2026-04-15T12:55:32Z

2. 가로등 (초2/중1/고1)

← 이전 판		2026년 4월 15일 (수) 21:55 판
197번째 줄:		197번째 줄:
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.

	~~추가 예정~~




			=== 📄 문제 개요 ===
			수직선 도로 위에 N개의 가로등이 켜져 있습니다. 도로의 끝은 L로 아주 깁니다.

			어떤 위치의 '''어두운 정도'''는 그 위치에서 '''가장 가까운 가로등까지의 거리'''를 뜻합니다.

			[[파일:2024KOI가로등1.png]]

			예를 들어 3, 6번 위치에 가로등이 있다면 그림과 같이 가로등이 있는 위치(p=0)을 시작으로 어두운 정도를 표시하게 됩니다.

			0부터 L까지 모든 위치의 어두운 정도를 구했을 때, '''가장 작은 값부터 K번째로 작은 값'''까지 차례대로 출력해야 합니다.





			=== 💡 첫 번째 접근 - 모든 위치 직접 탐색하기 ===
			가장 먼저 떠올릴 수 있는 직관적인 방법은 0부터 L까지 도로 위를 직접 걸어가며, 각 위치마다 모든 가로등과의 거리를 계산해 보는 것입니다.

			예를 들어 각 위치(pos)에서 가로등까지의 거리들을 모두 구한 뒤, 그중 가장 짧은 거리가 그 위치의 어두운 정도가 됩니다.

			[[파일:2024KOI가로등2.png]]

			이 값들을 리스트에 모아 오름차순으로 정렬한 뒤 앞에서부터 K개를 출력하는 방식입니다.


			=== 💻 코드 구현 - 모든 위치 직접 탐색하기 ===
			<syntaxhighlight lang="python3" line="1">
			import sys
			input = sys.stdin.readline

			l, n, k = map(int, input().split())
			a = list(map(int, input().split()))

			ans = []

			# 0부터 L까지 모든 위치 확인
			for pos in range(l + 1):
			# 현재 위치에서 모든 가로등과의 거리 중 최솟값(어두운 정도) 찾기
			m = 1000000000000000000 # 이론상 가능한 최대 거리
			for i in a:
			m = min(m, abs(pos - i))
			ans.append(m)

			ans.sort() # 오름차순 정렬

			# 가장 어두운 정도가 작은 K개 출력
			for i in range(k):
			print(ans[i])
			</syntaxhighlight>위 코드는 L칸을 일일이 확인하며 N개의 가로등을 매번 비교하므로,

			가로등 개수(N)와 도로 길이(L)가 모두 작은 부분문제 2번(N <= 2500, L <= 2500)까지만 무사히 통과하여 '''20점'''을 받게 됩니다.

			만약 도로 길이가 부분문제 4번(L <= 5,000,000)이나, 사실상 무한하게 커질 수 있는 부분문제 5번의 데이터가 들어오면

			이런 방식은 '''<nowiki/>'시간 초과''''가 발생할 수밖에 없습니다. 따라서 100점을 받기 위해서는 탐색 방식을 바꾸어야 합니다.


			=== 💡 두 번째 접근 - 너비 우선 탐색(BFS) ===
			우리가 출력해야할 것은 가장 밝은(어두운 정도가 가장 낮은) K개의 값입니다.

			따라서 가장 밝은 곳'''(가로등이 있는 위치)'''부터 영역을 점점 넓혀나가면서 탐색하는 방법을 생각해봅시다.



			잔잔한 호수에 돌멩이를 던졌을 때 퍼져나가는 물결을 상상해봅시다.

			가로등이 서 있는 위치를 물결의 중심(거리 0)이라고 생각하고, 양옆으로 동시에 1칸씩 영역을 넓혀가는 겁니다.

			# '''거리 0인 곳:''' 가로등이 있는 중심 위치들
			# '''거리 1인 곳:''' 중심에서 양옆으로 1칸 퍼져나간 위치들
			# '''거리 2인 곳:''' 거기서 다시 양옆으로 1칸 더 퍼져나간 위치들



			도로의 길이와 무관하게 가장 밝은 곳부터 점점 범위를 넓혀나가다가 가장 밝은 K개 값을 찾는 순간 탐색을 종료합니다.

			이처럼 가까운 곳부터 동심원처럼 영역을 넓혀가는 방식을 컴퓨터 공학에서는 '''너비 우선 탐색(BFS)'''이라고 부릅니다.

			[[파일:2024KOI가로등3.png]]

			=== 💻 코드 구현 - 너비 우선 탐색(BFS) ===
			<syntaxhighlight lang="python3" line="1">
			l, n, k = map(int, input().split())
			# 가로등 위치는 탐색 중 변하지 않으므로, 리스트보다 가볍고 빠른 튜플(tuple) 사용
			a = tuple(map(int, input().split()))

			# 100경 크기의 방문 배열 대신, 밟은 좌표만 세트(set) 활용 (메모리 초과 방지)
			visit = set()
			q = deque()

			# 1단계: 초기 가로등 위치들을 어두운 정도(거리) 0으로 큐에 모두 삽입, 방문 처리
			for i in a:
			q.append((i, 0))
			visit.add(i)

			# 2단계: 딱 K번만 정답을 출력하도록 while 조건 설정
			while k > 0:
			x, p = q.popleft() # x: 현재 위치, p: 어두운 정도(거리)

			# 거리가 짧은 곳부터 순서대로 출력됨
			print(p)
			k -= 1 # 정답을 출력할 때마다 목표 개수(K)를 1씩 감소

			# 3단계: 현재 위치 기준 양옆(왼쪽 1칸, 오른쪽 1칸) 탐색
			for cx in [(x - 1), (x + 1)]:
			if 0 <= cx <= l: # 도로 범위(0 ~ L) 안에 포함되고
			if cx not in visit: # 아직 방문하지 않은 위치라면
			visit.add(cx) # 방문 처리한 후
			q.append((cx, b + 1)) # 거리를 1 늘려서 큐에 삽입
			</syntaxhighlight>일반적으로 BFS 코드를 작성할 때, 방문 배열(visit = [False] * (L + 1) 형태)를 활용합니다.

			하지만 지금의 경우 '''L 최대 크기(100경)'''이 너무 크기 때문에 리스트를 활용하면 '''메모리 초과'''가 발생합니다.

			그래서 이번에는 set 자료구조를 사용해 우리가 '''실제로 방문한 좌표만 기록'''함으로써 메모리 낭비를 최소한으로 처리했습니다.

			이렇게 아주 '''큰 데이터 범위로 인한 몇 가지 함정'''을 피해서 완성하면, '''100점'''을 획득할 수 있습니다.



			=== 📊 정답률 ===
			초등부에서는 10% 미만이 100점, 조금이라도 부분점수를 받은 학생은 반 이상이었습니다.
			중, 고등부에서는 1번 문제로 출제되어 100점을 받은 학생이 50% 이상, 부분 점수는 대부분 획득한 모습입니다.

			아무래도 초등부 수준에서는 100점을 받을 정도의 알고리즘 완성도나, 함정을 피하는 것에 어려움이 있었던 문제입니다.

			=== ===

	== '''3. 색깔 모으기 (초3/중2)''' ==		== '''3. 색깔 모으기 (초3/중2)''' ==

ArduWiki: /* 1. 보물찾기 (초1) */

2026-04-14T10:56:08Z

1. 보물찾기 (초1)

← 이전 판		2026년 4월 14일 (화) 19:56 판
14번째 줄:		14번째 줄:
	다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.		다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.
	보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.		보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.



	다빈이는 다음과 같은 규칙으로 이동합니다.		다빈이는 다음과 같은 규칙으로 이동합니다.
26번째 줄:		24번째 줄:
	* 4단계: 오른쪽으로 2칸 떨어진 곳(S+2) 조사		* 4단계: 오른쪽으로 2칸 떨어진 곳(S+2) 조사
	* ...		* ...



	이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 '''가장 먼저 보물을 찾게 되는 단계'''를 구하는 문제입니다.		이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 '''가장 먼저 보물을 찾게 되는 단계'''를 구하는 문제입니다.



79번째 줄:		80번째 줄:

	다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다.		다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다.


	=== 💻 코드 구현 - 하나씩 모두 비교하기 ===		=== 💻 코드 구현 - 하나씩 모두 비교하기 ===
183번째 줄:		185번째 줄:

	따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 '''100점'''을 받을 수 있습니다.		따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 '''100점'''을 받을 수 있습니다.


	=== 📊 정답률 ===		=== 📊 정답률 ===

2026년 4월 14일 (화) 10:55에 ArduWiki님의 편집

2026-04-14T10:55:29Z

← 이전 판		2026년 4월 14일 (화) 19:55 판
28번째 줄:		28번째 줄:

	이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 '''가장 먼저 보물을 찾게 되는 단계'''를 구하는 문제입니다.		이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 '''가장 먼저 보물을 찾게 되는 단계'''를 구하는 문제입니다.



	=== 💡 첫 번째 접근 - 직접 이동해보기 ===		=== 💡 첫 번째 접근 - 직접 이동해보기 ===
80번째 줄:		79번째 줄:

	다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다.		다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다.


	=== 💻 코드 구현 - 하나씩 모두 비교하기 ===		=== 💻 코드 구현 - 하나씩 모두 비교하기 ===
149번째 줄:		147번째 줄:
	\|}		\|}
	가장 중요한 핵심은 오른쪽, 왼쪽을 번갈아 가며 확인하기 때문에 '''두 단계를 거쳐야''' 어느 한 방향으로 한 칸씩 전진이 가능하다는 점입니다.		가장 중요한 핵심은 오른쪽, 왼쪽을 번갈아 가며 확인하기 때문에 '''두 단계를 거쳐야''' 어느 한 방향으로 한 칸씩 전진이 가능하다는 점입니다.


	* '''오른쪽 보물(R)을 찾는 규칙'''		* '''오른쪽 보물(R)을 찾는 규칙'''
184번째 줄:		183번째 줄:

	따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 '''100점'''을 받을 수 있습니다.		따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 '''100점'''을 받을 수 있습니다.




	=== 📊 정답률 ===		=== 📊 정답률 ===
194번째 줄:		190번째 줄:



	== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==		== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.

2026년 4월 14일 (화) 10:54에 ArduWiki님의 편집

2026-04-14T10:54:50Z

← 이전 판		2026년 4월 14일 (화) 19:54 판
61번째 줄:		61번째 줄:
	\|7 (5+2)		\|7 (5+2)
	\|꽝		\|꽝
			\|-
	\|5		\|5
	\|왼쪽		\|왼쪽
141번째 줄:		142번째 줄:
	\|S + 2		\|S + 2
	\|R(오른쪽 보물)		\|R(오른쪽 보물)
			\|-
	\|5(홀수)		\|5(홀수)
	\|왼쪽		\|왼쪽

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

ArduWiki: /* 2. 가로등 (초2/중1/고1) */

ArduWiki: /* ﻿📊 정답률﻿ */

ArduWiki: /* 1. 보물찾기 (초1) */

2026년 4월 15일 (수) 12:57에 ArduWiki님의 편집

ArduWiki: /* 2. 가로등 (초2/중1/고1) */

2026년 4월 15일 (수) 12:56에 ArduWiki님의 편집

ArduWiki: /* 2. 가로등 (초2/중1/고1) */

ArduWiki: /* 1. 보물찾기 (초1) */

2026년 4월 14일 (화) 10:55에 ArduWiki님의 편집

2026년 4월 14일 (화) 10:54에 ArduWiki님의 편집

ArduWiki: /* 📊 정답률 */