Lecture 06. RECURSION, DICTIONARIES
이 글은 Mit Open Courseware(OCW)에서 공개한 교육자료이며 OCW의 라이센스정책을 따릅니다.
License : Common Creative License : BY-NC-SA (저작자표시-비영리-동일조건변경허락)
1. RECURSION
1) Recursion(재귀)이란
- 알고리즘 측면 : 분할정복(divide-and-conquer) 또는 감소정복(decrease-and-conquer) 방법으로 문제를 해결하는 방법
문제를 동일한 형태의 단순한 문제로 줄이는 방법
- 의미론적 측면 : 함수 자신을 호출하는 프로그래밍 기법
무한반복을 방지하기 위해 하나 이상의 기본 케이스가 존재해야 한다
큰 문제를 동일한 형태의 작은 문제로 나누어서 해결하는 방법
2) 예제 : '곱하기'를 재귀기법으로 풀기
a * b = a 를 b 번 더하기
a * b = a + a*(b-1) = a + a + a* (b-2)
def mult(a, b):
if (b == 1) :
return a
elif (b == 0) :
return 0
else:
return a + mult(a, b-1)
print(mult(2,0))
print(mult(2,1))
print(mult(2,2))
3) 예제 : Factorial
n! = n*(n-1)*(n-2)*(n-3)* … * 1
n! = n * (n-1)!
n = 1 이면 n! = 1 이라는 base case
def factorial(n):
if n == 1 :
return 1
else :
return n * factorial(n-1)
print(factorial(5))
4) 예제 : 하노이의 탑
- 3개의 기둥
- 서로 다른 크기의 64개의 원반이 하나의 기둥에 쌓여있음
- 이 원반을 다른 기둥으로 이동해야 함
- 한번에 하나만 옮길수 있으며, 작은 원반위에 큰 원반을 올릴수 없음
일반적인 해법을 위한 설명은 아래 링크 참고
https://terms.naver.com/entry.nhn?docId=2270443&cid=51173&categoryId=51173
기둥 세개를 Fr, Spare, To 라고 각각 지칭했을때 n개의 원반을 옮기는 방법을 아래의 세단계로 나눌 수 있다.
1. n-1개의 원반을 Fr에서 Spare 위치로 옮긴다.
2. n-1개를 옮겼으므로 Fr에는 가장 큰 원반이 하나가 남아 있으니 이 원반을 To의 위치로 옮긴다
3. 가운데 (spare) 위치의 n-1개의 원반을 To 위치로 옮긴다
base case : 원반이 하나일 때는 Fr에서 To로 이동한다.
def printMove(fr, to):
print('move from ' + str(fr) + ' to ' + str(to))
def Towers(n, fr, to, spare):
if n == 1:
printMove(fr, to)
else:
Towers(n-1, fr, spare, to)
Towers(1, fr, to, spare)
Towers(n-1, spare, to, fr)
print(Towers(4, 'P1', 'P2', 'P3'))
5) 예제 : 피보나치 수열
갓 태어난 암수 한쌍의 토끼를 우리에 넣는다
토끼는 태어난지 1개월이 지나면 짝짓기를 한다
토끼의 임신기간은 1개월이다
토끼가 죽지않고 한번에 암수 한쌍을 낳는다고 하면, 1년 뒤에 암컷 토끼는 몇마리가 되겠는가?
Month |
Female |
0개월 |
1마리(새끼) |
1개월후 |
1마리(임신) |
2개월후 |
2마리(임신1, 새끼1) |
3개월후 | 3마리(임신2, 새끼1) |
일반화시키면 females(n) = females(n-1) + females(n-2)
base case : females(0) = 1 , females(1) = 1
def fib(x):
"""assumes x an int >= 0
returns Fibonacci of x"""
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)
print(fib(12))
6) 예제 : palindrome (회문 回文: 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구)
“Able was I, ere I saw Elba”– Napoleon
“Are we not drawn onward, we few, drawn onward to new era?” – Anne Michaels
- 첫글자와 마지막 글자가 같으면 나머지가 회문인지 체크
- base case : 0글자, 1글자는 회문
Able was I, ere I saw Elba => ablewasiereisawelba
isPalindrome(‘ablewasiereisawleba’)
첫글자와 마지막글자 'a '== 'a' 이므로 나머지 isPalindrome(‘blewasiereisawb’)
def isPalindrome(s):
def toChars(s):
s = s.lower()
ans = ''
for c in s:
if c in 'abcdefghijklmnopqrstuvwxyz':
ans = ans + c
return ans
def isPal(s):
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and isPal(s[1:-1])
return isPal(toChars(s))
print(isPalindrome("abba"))
print(isPalindrome("abcd"))
print(isPalindrome('Able was I, ere I saw Elba'))
2. Dictionary
1) Student Info (List)
지금까지 배운 자료형으로는 아래처럼 각각의 List에 정보를 저장해야 하고, get_grade라는 함수를 작성하더라도 성명으로 학생의 index를 찾은후 나머지 정보는 그 index로 접근해야 한다. 따라서 모든 정보가 같은 길이를 가져야한다.
names = ['Ana', 'John', 'Denise', 'Katy']
grade = ['B', 'A+', 'A', 'A']
course = [2.00, 6.0001, 20.002, 9.01]
def get_grade(student, name_list, grade_list, course_list):
i = name_list.index(student)
grade = grade_list[i]
course = course_list[i]
return (course, grade)
2) Dictionary
List는 index, element로 데이터 저장하지만 Dictionary는 index외에 key, value를 쌍으로 저장한다.
my_dict = {} #empty dictionary
grades = {'Ana':'B', 'John':'A+', 'Denise':'A', 'Katy':'A'}
print(grades['John']) # 'A+' 출력
print(grades['Sylvan']) # 없는 key 이므로 KeyError: 'Sylvan'
3) Dictinary Operation
grades = {'Ana':'B', 'John':'A+', 'Denise':'A', 'Katy':'A'}
grades['Sylvan'] = 'A'
print( 'John' in grades ) # True 출력
print( 'Daniel' in grades) # False 출력
del(grades['Ana']) # Ana 삭제
print(grades)
print(type(grades.keys())) # <class 'dict_keys'>
print(grades.keys()) # dict_keys(['John', 'Denise', 'Katy', 'Sylvan'])
print(type(grades.values())) # <class 'dict_values'>
print(grades.values()) # dict_values(['A+', 'A', 'A', 'A'])
4) DICTIONARY KEYS and VALUES
- value
- any type (immutable and mutable)
- 중복가능
- List도 value로 가능하며 다른 Dictionary도 value로 가능 - key
- unique 해야한다
- immutable type (int, float, string, tuple,bool) - key와 value는 순서가 없다
d = {4:{1:0}, (1,3):"twelve", 'const':[3.14,2.7,8.44]
3. INEFFICIENT FIBONACCI RECURSIVE CODE
앞서 설명한 Fibonacchi 재귀 알고리즘은 동일한 함수를 여러번 호출하게 되어 있어서 비효율적이다
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(4)의 계산이 끝나면 fib(3)의 값을 알고 있음에도 fib(3)을 다시 계산하는 방식인데 만약 앞서 계산에서 fib(3)의 값을 저장하고 있다면 다시 계산할 필요가 없게된다.
Dictionary 자료구조에 이미 계산한 값을 저장하고 결과값이 존재하면 다시 계산하지 않고 그 값을 사용하는 방식으로 코드를 개선한다
def fib_efficient(n, d):
if n in d:
return d[n]
else:
ans = fib_efficient(n-1, d) + fib_efficient(n-2, d)
d[n] = ans
return ans
d = {1:1, 2:2}
print(fib_efficient(6, d))
'Tech-Pyhton' 카테고리의 다른 글
| Python 자료형 SORT [List, Tuple, Dictionary] (0) | 2019.03.06 |
|---|---|
| [Python] 문자열 함수 (0) | 2019.03.03 |
| MIT OCW - Introduction to Computer Science and Programming in Python - Lecture 05 (0) | 2019.02.12 |
| MIT OCW - Introduction to Computer Science and Programming in Python - Lecture 04 (0) | 2019.01.25 |
| MIT OCW - Introduction to Computer Science and Programming in Python - Lecture 03 (0) | 2019.01.10 |
댓글