2023 한국정보올림피아드(KOI) 2차 대회 초등부: 두 판 사이의 차이

아두위키 : Arduwiki
시각위키텍스트
(새 문서: {{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2024 KOI, 2024 초등부 2차 대회|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/arduwiki.pn...)
 
잔글편집 요약 없음
1번째 줄: 1번째 줄:
{{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2024 KOI, 2024 초등부 2차 대회|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}
{{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2023 KOI, 2023 초등부 2차 대회|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}


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




== '''[https://codersit.co.kr/oj/problems/1688 1. 보물찾기 (초1)]''' ==
== '''[https://codersit.co.kr/oj/problems/1589 1. 불안정한 수열 (초1)]''' ==
제목 링크를 통해 문제를 확인해주세요.
제목 링크를 통해 문제를 확인해주세요.


📄 문제 개요

 
다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다.
보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.
 
다빈이는 다음과 같은 규칙으로 이동합니다.
 
[[파일:2024KOI보물찾기1.png|center|class=coders100]]
 
* 1단계: 제자리(S) 조사
* 2단계: 오른쪽으로 1칸 떨어진 곳(S+1) 조사
* 3단계: 왼쪽으로 1칸 떨어진 곳(S-1) 조사
* 4단계: 오른쪽으로 2칸 떨어진 곳(S+2) 조사
* ...
 
 
 
이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 '''가장 먼저 보물을 찾게 되는 단계'''를 구하는 문제입니다.
 
 
 
=== 💡 첫 번째 접근 - 직접 이동해보기 ===
가장 직관적인 방법은 시작 위치(S)부터 한 단계씩 직접 움직여보면서 L 또는 R에 도착하는 상황을 확인하는 것입니다.
 
예를 들어 '''왼쪽 보물이 2(L=2), 오른쪽 보물이 9(R=9)'''에 있고 '''다빈이가 5(S=5)에서 출발'''한다고 가정해 보겠습니다.
{| class="wikitable" style="text-align: center;"
|+
!단계
!이동 방향
!다빈이의 위치
!확인 결과
|-
|1
|제자리
|5
|꽝
|-
|2
|오른쪽
|6 (5+1)
|꽝
|-
|3
|왼쪽
|4 (5-1)
|꽝
|-
|4
|오른쪽
|7 (5+2)
|꽝
|-
|5
|왼쪽
|3 (5-2)
|꽝
|-
|6
|오른쪽
|8 (5+3)
|꽝
|-
|7
|왼쪽
|2 (5-3)
|왼쪽 보물 찾음
|}
이렇게 단계(step)를 1씩 늘려가며 짝수일 때는 오른쪽, 홀수일 때는 왼쪽을 확인하다가,
 
다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다.
 
 
=== 💻 코드 구현 - 하나씩 모두 비교하기 ===
<syntaxhighlight lang="python3" line="1">
import sys
input = sys.stdin.readline
 
t = int(input())
for _ in range(t):
    l, r, s = map(int, input().split())
   
    step = 1
    k = 0
    while True:
        # step이 짝수면 오른쪽(+k), 홀수면 왼쪽(-k)
        if step % 2 == 0:
            pos = s + k
        else:
            pos = s - k
           
        # 보물을 찾으면 종료
        if pos == l or pos == r:
            print(step)
            break
           
        # 다음 단계를 위한 설정
        step += 1
        if step % 2 == 0:
            k += 1
</syntaxhighlight>이 방식은 구현이 쉽다는 장점이 있지만, 제약 조건에 따라 보물이 시작점으로부터 1억 칸(100,000,000) 떨어져 있다면
 
반복문도 수억 번을 돌아야 합니다. 따라서 제한 시간 내에 모든 테스트 케이스를 통과하지 못하고 '''부분 점수(48점)'''를 받게 됩니다.
 
 
=== 💡 두 번째 접근 - 수학적 규칙 찾기 ===
반복문으로 인한 시간 초과를 피하려면 종이 위에서 다빈이의 이동 패턴을 차분하게 수식으로 전개해 보아야 합니다.
{| class="wikitable" style="text-align: center;"
|+
!단계
!이동 방향
!다빈이의 위치
!목표 지점
|-
|1(홀수)
|제자리
|S
|d
|-
|2(짝수)
|오른쪽
|S + 1
|R(오른쪽 보물)
|-
|3(홀수)
|왼쪽
|S - 1
|L(왼쪽 보물)
|-
|4(짝수)
|오른쪽
|S + 2
|R(오른쪽 보물)
|-
|5(홀수)
|왼쪽
|S - 2
|L(왼쪽 보물)
|}
가장 중요한 핵심은 오른쪽, 왼쪽을 번갈아 가며 확인하기 때문에 '''두 단계를 거쳐야''' 어느 한 방향으로 한 칸씩 전진이 가능하다는 점입니다.
 
 
* '''오른쪽 보물(R)을 찾는 규칙'''
 
오른쪽으로 1칸 전진하려면 (오른쪽) 👉 '''2단계''' 소요
 
오른쪽으로 2칸 전진하려면 (오른쪽, 왼쪽, 오른쪽) 👉 '''4단계''' 소요
 
오른쪽으로 떨어진 거리(R - S)를 가기 위해서는 '''두 단계씩''' 거쳐야 하므로 거리에 '''2를 곱하면''' 됩니다. 👉 '''수식: 2 * (R - S)'''
 
 
* '''왼쪽 보물(L)을 찾는 규칙'''
 
왼쪽으로 1칸 전진하려면 (오른쪽, 왼쪽) 👉 '''3단계''' 소요
 
왼쪽으로 2칸 전진하려면 (오른쪽, 왼쪽, 오른쪽, 왼쪽) 👉 '''5단계''' 소요
 
항상 오른쪽을 먼저 확인한 뒤 왼쪽을 확인하기 때문에 왼쪽으로 떨어진 거리(S - L)에 '''2를 곱한 뒤, 처음에 썼던 1단계를 더해주면''' 됩니다.
 
👉 '''수식: 2 * (S - L) + 1'''
 
 
=== 💻 코드 구현 - 카드 번호 처음 등장 위치 메모해두기 ===
<syntaxhighlight lang="python3" line="1">
t = int(input())
for i in range(t):
    l, r, s = map(int, input().split())
   
    r_step = 2 * (r - s)  # 오른쪽 보물(R)을 찾는 단계
    l_step = 2 * (s - l) + 1 # 왼쪽 보물(L)을 찾는 단계
   
    # 둘 중 더 빨리 찾는(작은) 단계 출력
    print(min(r_step, l_step))
</syntaxhighlight>이렇게 수학적인 규칙을 찾아 수식을 잘 생각해내었다면 보물이 아주 멀리있더라도 단 한 번의 사칙연산으로 정답을 구할 수 있습니다.
 
따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 '''100점'''을 받을 수 있습니다.
 
 
=== 📊 정답률 ===
2차에 진출한 80% 이상의 초등부 학생들이 100점을 받아낸 비교적 난이도가 쉬운 문제였습니다.
 
100점을 받지 못했더라도 거의 모든 학생들이 48점을 받을 수 있는 풀이는 해낸 모습입니다.






== '''[https://codersit.co.kr/oj/problems/1689 2. 가로등 (초2/중1/고1)]''' ==
== '''[https://codersit.co.kr/oj/problems/1629 2. 스케이트 연습 (초2/중1/고1)]''' ==
제목 링크를 통해 문제를 확인해주세요.
제목 링크를 통해 문제를 확인해주세요.
=== 📄 문제 개요 ===
수직선 도로 위에 N개의 가로등이 켜져 있습니다. 도로의 끝은 L로 아주 깁니다.
어떤 위치의 '''어두운 정도'''는 그 위치에서 '''가장 가까운 가로등까지의 거리'''를 뜻합니다.
[[파일:2024KOI가로등1.png|center|class=coders100]]
예를 들어 3, 6번 위치에 가로등이 있다면 그림과 같이 가로등이 있는 위치(p=0)을 시작으로 어두운 정도를 표시하게 됩니다.
0부터 L까지 모든 위치의 어두운 정도를 구했을 때, '''가장 작은 값부터 K번째로 작은 값'''까지 차례대로 출력해야 합니다.






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


예를 들어 각 위치(pos)에서 가로등까지의 거리들을 모두 구한 뒤, 그중 가장 짧은 거리가 그 위치의 어두운 정도가 됩니다.
== '''[https://codersit.co.kr/oj/problems/1670 3. 호숫가의 개미굴 (초3/중2)]''' ==


[[파일:2024KOI가로등2.png|center|class=coders100]]
추가 예정
 
이 값들을 리스트에 모아 오름차순으로 정렬한 뒤 앞에서부터 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|center|class=coders100]]
=== 💻 코드 구현 - 너비 우선 탐색(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점'''을 획득할 수 있습니다.

== '''3. 색깔 모으기 (초3/중2)''' ==
추가 예정




== '''4. 양손에 V (초4)''' ==
== '''4. 고기 파티 (초4/중3)''' ==


추가 예정
추가 예정

2026년 4월 25일 (토) 11:40 판


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

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


1. 불안정한 수열 (초1)

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





2. 스케이트 연습 (초2/중1/고1)

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




3. 호숫가의 개미굴 (초3/중2)

추가 예정


4. 고기 파티 (초4/중3)

추가 예정

원본 주소 "https://arduwiki.com/html/index.php?title=2023_한국정보올림피아드(KOI)_2차_대회_초등부&oldid=2874"