정보 교과서 3단원 [문제 해결과 프로그래밍]에서는 다양한 분야의 문제를 추상화하고 구조화하여 해결 방법을 도출하고 프로그래밍을 통해 프로그램을 작성하여 자동화할 수 있는 능력을 요구한다. 학생들이 파이썬 언어에 어느 정도 익숙해졌을 때 3단원을 돌아보는 문제로 개미 수열을 소개한다.
문제 설명
다음은 베르나르 베르베르의 소설 「개미」에 나온 수열로 개미 수열이라고 불린다. 개미 수열의 규칙을 찾아 8번째 수열을 알아내보자.
문제 이해 및 분석
•
문제에서 해결하고자 하는 것은? 8번째 개미 수열 알아내기
•
문제의 현재 상태와 목표 상태는?
◦
현재 상태 : 첫 번째 개미 수열부터 일곱 번째 개미 수열까지 주어져있다.
◦
목표 상태 : 여덟 번째 개미 수열을 찾는다.
•
문제에서 규칙 찾기 : 이전 수열에서 연속적인 자연수의 개수를 파악하여 다음 수열을 만든다. 예를 들어 이전 수열이 OXX☐☐☐이면 다음 수열은 O1X2☐3이 되는 것이다. 수열이 한 자릿수라면 다음 수열은 O1이 된다.
문제 해결
위에서 찾은 수열의 규칙에 따르면 7번째 수열을 통해 8번째 수열을 알아낼 수 있다.
7번째 수열 ⇨ 1 2 2 2 1 1 3 1
8번째 수열 ⇨ 1 1 2 3 1 2 3 1 1 1
1이 1개 있고, 2가 3개 있고, 1이 2개 있고, ⋯
알고리즘 설계 및 프로그래밍(리스트를 이용한 방법)
개미 수열을 리스트 형태로 저장하여 앞에서 파악한 규칙을 그대로 적용하는 방법이다. 현재 알고 있는 개미 수열을 ant에 저장하고, 알아내고자 하는 다음 개미 수열을 변수 newant에 저장한다고 하자. ant 리스트의 첫번째 원소를 변수 target에 저장해두고 인덱스가 1부터 len(ant) 미만인 범위에서 1씩 증가하는 동안 target과 같은 숫자가 몇 개 나오는지 세어 준다. target과 다른 숫자가 나오면 target 값과 이전까지 저장해둔 개수를 newant 리스트에 추가한다. 아래 그림을 보자.
•
(그림) 네 번째 개미 수열에서 다섯 번째 개미 수열을 구하는 과정
num = int(input('몇 번째 개미 수열을 구할까요? '))
ant = [1] #첫번째 개미 수열
for i in range(num-1) :
target = ant[0]
newant = [] #다음 개미 수열을 저장할 리스트
count = 1
for j in range(1, len(ant)) : #현재 개미 수열에서 숫자 하나씩 살펴보며 개수 세기
if target != ant[j] : #숫자의 연속이 끊긴 경우
newant.append(target)
newant.append(count)
target = ant[j]
count = 1
else : #숫자가 계속 연속적으로 나오는 경우 개수 1씩 증가
count += 1
newant.append(target) #마지막에 저장되어있는 target과 count를 다음 개미 수열에 추가함
newant.append(count)
ant = newant
print(ant)
Python
복사
알고리즘 설계 및 프로그래밍(큐를 이용한 방법)
큐(queue)의 선입선출(FIFO) 방식을 이용하여 앞에서 파악한 규칙을 적용하는 방법이다. 리스트의 pop()을 사용하여 개수를 세야 하는 첫 번째 숫자를 t1에 저장한 뒤, 한 번 더 앞에 있는 데이터를 꺼내 t2에 저장한다. 그 뒤 t1과 t2를 비교해 연속적으로 나타나는 자연수의 개수를 count한다. 아래 그림을 보자.
•
(그림) ant가 1121일 때 다음 개미 수열(newant)을 구하는 과정
ant = input('수열의 시작 값을 입력하세요 : ')
num = int(input('몇 번째 개미수열을 구할까요? '))
queue = []
print(ant)
for n in range(num-1) :
for i in ant :
queue.append(i)
temp = []
t1 = queue.pop(0)
count = 1
result = t1 + str(count)
while queue :
t2 = queue.pop(0)
if t1 == t2 :
count = count + 1
result = t1 + str(count)
else :
result = t1 + str(count)
temp.append(result)
t1 = t2
count = 1
result = t1 + str(count)
temp.append(result)
newant = ''
for i in temp :
newant = newant + i
print(newant)
ant = newant
Python
복사