매년 2학기가 되면 특별한 사전 지식 없이도 정보과학을 접할 수 있는 비버챌린지 도전이 시작됩니다.
케이크쌤도 신규 때부터 학생들이 비버챌린지에 참여할 수 있도록 지도해 왔으며, 때로는 정보과학의 어떤 어려운 개념을 설명해야 할 때 동기부여 자료로 비버챌린지 문제를 사용하곤 했는데요. 항상 아이들과 문제를 풀고 나면 ‘심화 수업으로 비버챌린지 문제를 프로그래밍 언어로 구현해 보면 어떨까?’하는 생각을 하곤 했습니다.(항상 시수 부족으로 실천에 옮기진 못했지만요🥲)
그.래.서!
오늘은 2022년 중학교 2~3학년 비버챌린지 문제를 살펴보고, 이를 파이썬과 블록 언어로 해결해 보려고 합니다.
출처: 한국비버챌린지
문제에서 해결하고자 하는 것은?
: 양초의 색깔이 같아지는 특정 생일에서 다음 생일까지 사이 구간의 길이를 period(단위 : 년)라 할 때, 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) + '년')