C

Object-oriented Language

다른 객체 지향 언어와 마찬가지로 Class와 Instance Attribute, Method 등의 개념이 존재한다.

Object-oriented Design

Object-oriented design has fundamnental defferences from structured programming design methods. The two methods are similar in that they develop complex systems with divide and conquer, but differ in how to divide a given task.

Subsequence

In mathmatics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elememts without changing the order of the remaining elememts.

What is Sequence?

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed. Serial arrangement in which things follow in logical order or a recurrent pattern.

Substring

Substring can be derived from the string by deleting anoter substring. The substring is a refinement of the subsequence.

Quick Sort

• Divide and Conquer Algorithm

• Use Recursion

0. 정렬해야할 list, 시작점 start와 끝점 end를 넘겨 받는다. left = start, right = end로 정한다.

1. 양방향의 left와 right를 pivot 방향으로 움직이며 pivot 값과 left, right index의 element 값을 비교한다.

2. left의 element 값이 pivot 보다 크고, right의 element 값이 pivot보다 작을 때 둘을 교환하고 각 index를 하나씩 이동한다.(left면 +1, right면 -1)

3. left와 right가 교차되기 전까지 반복하면서 sorting한다.

4. 한 번 교차되면 while문을 빠져나오는데, 이 때 pivot을 기준으로 왼쪽은 pivot보다 작은 값들로, 오른쪽은 pivot보다 큰 값들로만 이루어져있다.

5. Recursion으로 pivot을 포함하지 않고 왼쪽과 오른쪽을 각각 다시 돌려준다. 이 때 base case는 start가 end와 같아지거나 교차하면 return하는 것이다.

• 코드를 보는 게 더 이해가 쉬울 것 같다. 그림으로 그려보며 진행하는 게 가장 도움이 된다.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  def quickSort(li, start, end): if start >= end: return left = start right = end pivot = li[(left+right)//2] while left <= right: while li[left] < pivot: left += 1 while li[right] > pivot: right -= 1 if left <= right: li[left], li[right] = li[right], li[left] left += 1 right -= 1 quickSort(li, start, right-1) quickSort(li, left, end)

  1 2 3 4 5 6 7 8 9 10

  import random while True: num_data=int(input('데이터 개수(0이면 종료):')) if not num_data: break data=[random.randint(1, 100) for _ in range(num_data)] print(data) quickSort(data, 0, len(data)-1) print(data)

• [Quick sort에 관련된 TED edu 영상] What’s the fastest way to alphabetize your bookshelf?

  

• 문제는 pivot을 어떻게 결정할 것이냐이다. Pivot이 정렬해야할 list의 모든 값들의 평균치일 때는 n/2번을 비교하는 것으로 가장 좋지만, 예를 들어 최솟값이나 최댓값을 기준으로 pivot이 선택될 경우 n번을 계산해야한다.

• pivot을 정렬된 list의 가운데 값으로 결정하는 것이 Best case지만, 정렬을 하기 위해서 pivot을 사용하는 것이므로 실현될 수 없는 이야기이다.

• Quick Sort의 Time Complexity는 O(nlogn)으로, average case일 때를 기준으로 한다. Pivot을 random pivot으로 둘 경우 확률적으로 avarage case를 만족한다.

• li의 start와 end와 mid를 정렬한 결과의 중간 값을 return한다. Random Pivot을 이용하기 위해 코드를 수정했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def getMiddleIndex(li, start, mid, end):
    """
    list의 맨 처음 값, 끝 값, 중간 값 정렬시 가운데 값의 index 반환
    """
    indices = [start, mid, end]
    
    if li[indices[0]] > li[indices[1]]:
        indices[0], indices[1] = indices[1], indices[0]
    if li[indices[1] > li[indices[2]]]:
        indices[1], indices[2] = indices[2], indices[1]
    if li[indices[0]] > li[indices[1]]:
        indices[0], indices[1] = indices[1], indices[0]
        
    return indices[1]

전체 반영한 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def getMiddleIndex(li, start, mid, end):
    """
    list의 맨 처음 값, 끝 값, 중간 값 정렬시 가운데 값의 index 반환
    """
    indices = [start, mid, end]
    
    if li[indices[0]] > li[indices[1]]:
        indices[0], indices[1] = indices[1], indices[0]
    if li[indices[1] > li[indices[2]]]:
        indices[1], indices[2] = indices[2], indices[1]
    if li[indices[0]] > li[indices[1]]:
        indices[0], indices[1] = indices[1], indices[0]
        
    return indices[1]


def quickSort(li, start, end):
    if start >= end:
        return
    left = start
    right = end
    mid = (left+right)//2
    
    #추가된 코드
    mid_index = getMiddleIndex(li, start, mid, end)
    li[mid_index], li[mid] = li[mid], li[mid_index]
    
    pivot = li[mid]
    
    while left <= right:
        while li[left] < pivot:
            left += 1
        while li[right] > pivot:
            right -= 1
        if left <= right:
            li[left], li[right] = li[right], li[left]
            left += 1
            right -= 1
            
    quickSort(li, start, right-1)
    quickSort(li, left, end)

추상화 | Abstraction ?

• 추상화란, 복잡한 로직을 가지고 있는 기능에서 그것을 다루기 위해 필요한 최소한의 핵심만을 추출해내는 것을 말한다. 정의만 들으면 어렵다.

  TV 전원을 예로 들어 생각해보자. 새로 산 TV의 설명서를 보면 TV를 켜려면 전원 버튼을 누르라고 되어있다. 사용자는 전원 버튼을 누르면 쉽게 TV를 켤 수 있다.

  그러나 실제로 TV의 전원 버튼을 누르는 순간 내부 전기회로에서는 복잡한 기능이 실행될 것이다. 사용자는 그것을 알 수 없고, 알 필요도 없다. TV 제작 회사에서 TV에 대한 추상화를 시켜 사용자가 쉽게 TV를 동작시킬 수 있도록 한 것이다.

• 함수를 보통 function, routine, procedure 라고 부른다. 이 때, procedure 단위로 추상화를 하고 procdural하게 진행하는 프로그램을 절차 지향 프로그램이라고 한다. 그러나 프로그램이 거대해지고, 코드가 길어지자 프로그램을 객체(object)로 추상화하는 방법론이 나왔고 그걸 적용한 게 객체 지향 프로그램이다.

Recursion (재귀)

1. 함수 호출 도중에 자기 자신을 다시 호출하는 것

2. Base case가 필수 (기초, 종료, 탈출 조건)

   Base case가 없으면 무한으로 자기 자신을 호출해서 stack overflow가 된다.

재귀함수를 만드는 방법

1. 패턴을 찾는다. 즉, 점화식(Induction)을 만든다.
2. Base case를 만든다.

예제1: Factorial !

• Basis

  0! = 1! = 1

• Induction Step

  n! = (n-1) * (n-2) * (n-3) * … 3 * 2 * 1

1
2
3
4
5

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n*factorial(n-1)

예제2: Fibonacci

• Basis

  fib(0) = fib(1) = 1

• Induction Step

  fib(n) = fib(n-1) + fib(n-2)

1
2
3
4
5

def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Fibonacci Dynamic Programming

1. Memorization (Top Down)

1
2
3
4
5
6
7
8
9

f = [-1 for _ in range(100)]
def fib_memorize(n):
    if f[n] > -1:
        return f[n]
    elif n <= 1:
        f[n] = 1
    else:
        f[n] = fib_memorize(n-1) + fib_memorize(n-2)
    return f[n]

2. Bottom Up

1
2
3
4
5
6

f2 = [-1 for _ in range(100)]
def fib_bottup(n):
    f2[0] = f[1] = 1
    for i in range(2, n+1):
        f[n] = f[n-1] + f[n-2]
    return f[n]

예제3: Hanoi Tower

Play Tower of Hanoi

1
2
3
4
5
6
7
8

def hanoi(n, _from, _by, _to):
    # base case
    if n==1:
        print(f'{n}번째 쟁반을 {_from}에서 {_to}로 옮긴다.')
        return
    hanoi(n-1, _from, _to, _by)
    print(f'{n}번째 쟁반을 {_from}에서 {_to}로 옮긴다.')
    hanoi(n-1, _by, _from, _to)