6강 - Recursion and Dictionaries

Lecture 6: Recursion and Dictionaries | Introduction to Computer Science and Programming in Python | Electrical Engineering and

 

Review / Preview

 

---

저번 시간 내용 : https://ikablog.tistory.com/12

1. Tuple, List

   새로운 Datatype.

2. 얘네로 인해 만들어지는 Aliasing, Mutability, Cloning이라는 개념

 

 ---

 

이번 시간 내용

 

1. Recursion

2. Dictionary

3. 둘이 합쳐서 문제 풀기

 

 

1. Recursion

Recursion : 자기 자신을 반복하는 것.

  - 어떠한 함수가 작동중에 자기 자신을 호출하는 것.

  - 알고리즘적으로 : Divide and Conquer 계열의 문제 해결 방법. 작은 파트를 계속 반복하도록.

 

이전 단원까지는 while, for 등의 Iterative algorithm을 써서, 루프를 만들어서 해결했다.

iterative algorithm은 '정해진 상태의 변수들'을 바탕으로 루프를 만드는 개념이다. (ex> range, list)

 

예를 들어,

a*b 는 a를 더하는 것을 b번 반복하는 것이다. 

Iterative algorithm의 관점에서 코딩하면, a를 더하는 while루프를 짜고, 루프마다 b를 1씩 줄이다가, b가 0이 되면 합을 반환는 코드를 짤 수 있다..

def mult(a,b) :
    total = 0 
    while b > 0 :
        total += a
        b -=1
    return total

.

Recursive algorithm의 관점에서 코딩해보자.

 

Recursive algorithm은 base case (바로 풀 수 있는 단계) 와 recursive step (쪼개기 단개) 로 나뉜다.

 

a * b는 a를 b번 더한 것이지만, 동시에 a + a(b-1)이기도 하다. 또 a + a(b-1)은 a + a + a(b-1-1)로 쪼개진다.

이렇게 반복되는 구조를 바탕으로, a + a(b-1) 의 반복으로 쪼갤 수 있다.

그리고 바로 풀 수 있는 base case는 b == 1일 때, 즉 곱셈이 필요가 없어질 때이다.

  

def mult(a,b) :
    if b==1 :	
        return a	#base case
    else :
        return a + mult (a, b-1)	#recursive step

 

또다른 고전적인 예시로 팩토리얼이 있다.

 

n! = n * (n-1) * (n-2) * ... * 1 이다.

마찬가지로 n * (n-1)! 으로 쪼갤 수 있으며 n = 1일때가 base case가 된다.

 

def fact(n) :
    if n==1 :	
        return 1	#base case
    else :
        return n * fact (n)	#recursive step

 

위 코드에서 fact(4)를 실행해본다고 생각하면,

 ... 이런 식으로, 함수가 함수를 부르고 또 함수가 함수를 부르는 구조가 만들어질 것이다. 
차례차례 1 - 2 - 6 - 24가 return되고 최종적으로 print (24)가 실행될 것이다.

각각의 함수는 고유한 Local scope를 가지게 된다.

 

def fact(n) :
	prod = 1
    for i in range (n) :
    	prod *= i+1
    return prod

 만약 iteration을 가지고 코드를 짰다면 이런 식이 되었을 것이다.

 

 

 

Recursion은 코드를 더 깔쌈하게, 그리고 짧게 만들어준다. 프로그래머 입장에선 이쪽이 읽기 덜 헷갈린다. 일단 변수가 적고, 파악하기도 쉽다.

다만, Recursion은 이처럼 많은 scope를 만들어야 하기 때문에 컴퓨터 입장에서는 왕왕 자원낭비를 하게 된다.

또한, 삑하면 무한루프에 갇힐 수도 있다. 예를 들어 위의 식에 fact(0)을 넣었다고 생각하면... 끔찍해진다.

 

 

고등학교 수학 수학적 귀납법과 같은 매커니즘이다.

 

 

* 하노이의 탑, 피보나치 수열 등의 예시를 듬.

 

* 물론 숫자가 아닌 문자열에 대해서도 풀 수 있음. (ex> 회문 체크 알고리즘)

 

2. Dictionary

 

---

내 성적을 과목별로 정리하고 싶을 때, 리스트 두 개를 만들어

subject = ["국어", "수학", "영어", "사회", "과학"]
score = [100, 90, 80, 70, 60]

 이런 식으로 저장하게 된다면, 다루기도 불편하고 코드를 짜다가 꼬이는 일도 많을 것이다.

 

List가 순서에 대응하는 값이라면, Dictionary는 Key에 대응하는 값이다. {중괄호}로 만든다. 

아까와 같은 리스트를 하나의 Key:값 으로 저장할 수 있다. **Key는 Immutable한 type만 가능.**

score = {'국어':100, "수학":90, "영어":80, "사회":70, "과학":60}

 

 

Dictionary에 새로운 항목을 추가하고 싶을 때는 간단하게  Dict[Key] = value를 하면 된다.

리스트에서 없는 숫자를 부르면 "list assignment index out of range" 오류가 나는 것과는 대조적이다.

score = {'국어':100, "수학":90, "영어":80, "사회":70, "과학":60}

score['한국사'] = 100

in을 통해 해당 Key가 Dict에 있는지 아닌지 알 수 있다.

"한국사" in key #True
"가정" in key #False

 

del (dict[key]) 를 통해 해당 Key:value를 지울 수 있다.

 

score = {'국어':100, "수학":90, "영어":80, "사회":70, "과학":60}
del(score['국어'])
print(score)	# {"수학":90, "영어":80, "사회":70, "과학":60}

 

.keys()를 통해 모든 key를 Tuple의 형태로 반환받을 수 있다. 이때, tuple의 순서는 무작위다.

.values()를 통해 모든 key를 Tuple의 형태로 반환받을 수 있다. 마찬가지로 tuple의 순서는 무작위다.

 

 

Dictionary는 Iterable한 객체로, key값을 Iterate 하게 된다.