매년 2학기가 되면 특별한 사전 지식 없이도 정보과학을 접할 수 있는 비버챌린지 도전이 시작됩니다.
케이크쌤도 신규 때부터 학생들이 비버챌린지에 참여할 수 있도록 지도해 왔으며, 때로는 정보과학의 어떤 어려운 개념을 설명해야 할 때 동기부여 자료로 비버챌린지 문제를 사용하곤 했는데요. 항상 아이들과 문제를 풀고 나면 ‘심화 수업으로 비버챌린지 문제를 프로그래밍 언어로 구현해 보면 어떨까?’하는 생각을 하곤 했습니다.(항상 시수 부족으로 실천에 옮기진 못했지만요
)
)그.래.서!
오늘은 2022년 중학교 2~3학년 비버챌린지 문제를 살펴보고, 이를 파이썬과 블록 언어로 해결해 보려고 합니다.
문제설명
출처: 한국비버챌린지
문제 이해 및 분석
•
문제에서 해결하고자 하는 것은?
: 양초의 색깔이 같아지는 특정 생일에서 다음 생일까지 사이 구간의 길이를 period(단위 : 년)라 할 때, period의 최댓값
•
문제의 현재 상태와 목표 상태는?
◦
현재 상태 : 0부터 9까지의 각 양초 색깔이 주어짐, 현재 사이먼은 11번째 생일
◦
목표 상태 : 앞으로 99살이 될 때까지 period의 최댓값
알고리즘 설계 및 프로그래밍(파이썬)
중학생 아이들이 가장 쉽게 떠올릴 수 있는 문제 풀이 방법은 11살부터 99살까지 모든 경우의 양초 색깔을 살펴보는 것입니다. 이렇게 가능한 모든 경우를 탐색하여 답을 찾는 알고리즘을 브루트 포스(Brute Force) 알고리즘이라고 합니다. 어떤 문제에 대해 모든 가능한 조합을 시도해 보는 것이죠.
브루트 포스 알고리즘은 간단하고 이해하기 쉬우며, 작은 문제나 입력 크기가 작은 경우에는 효과적일 수 있습니다. 하지만 입력 크기가 큰 문제의 경우 시간이 오래 걸리거나 메모리를 많이 사용할 수 있습니다.
candle 리스트에 각 양초의 색상 정보를 저장한 후 11부터 99까지 모든 경우를 살펴보고 양초 색이 같다면 그 숫자(나이)를 same_age 리스트에 넣어줍니다. same_age 리스트에 있는 원소들은 오름차순으로 저장되어 있기 때문에 각 이웃한 원소의 사이 간격을 조사하여 그 최댓값을 찾아주면 우리가 원하는 정답을 구할 수 있습니다.
#양초 리스트를 만들어 인덱스를 양초 번호로 보고, 해당 인덱스에 색상정보 저장
#o는 주황, r는 빨강, b는 파랑
candle = ['o', 'r', 'b', 'o', 'r', 'b', 'o', 'r', 'b', 'o']
same_age = []
#11살부터 99살까지 양초 색깔 확인하기(브루트 포스)
for i in range(11, 100) :
x = i // 10
y = i % 10
if candle[x] == candle[y] : #십의 자리 양초와 일의 자리 양초 색상이 같으면
same_age.append(i) #same 리스트에 그 나이를 저장
period = 0
#인접한 숫자의 차를 period에 저장해서 최댓값 구하기
for i in range(0, len(same_age)-1) :
if same_age[i+1] - same_age[i] > period :
period = same_age[i+1] - same_age[i]
print('다음 생일까지 제일 긴 기간: ' + str(period) + '년')
Python
복사
알고리즘 설계 및 프로그래밍(엔트리)
엔트리 역시 파이썬과 마찬가지로 리스트를 활용하여 candle 리스트에 양초의 색상 정보를 저장한 후 11부터 99까지 모든 경우를 살펴보고 same_age 리스트에 추가합니다. 단, 엔트리는 파이썬과 달리 리스트의 인덱스가 0번이 아닌 1번부터 시작하므로 넘버링할 때 이 부분을 꼭 기억하고 코드를 작성해야 합니다.
same_age 리스트에 양초색이 동일한 숫자를 추가하였다면 period 변수를 사용하여 가장 긴 간격을 구하기 위해 다시 한 번 for 반복문을 작성해주면 됩니다. 그래서 마지막에 출력되는 최댓값이 이 문제의 정답이 될 수 있습니다!!
코드 화면
실행 화면