Today I Learned

• Fastcampus에서 진행한 졸업생과의 티타임 시간에 졸업한 개발자분을 만나뵙고 경험들을 들었다. 많은 도움이 됐다.

• Network를 대략적으로 살펴봤다. 나는 학교에서 배웠지만 오래되어 다시 한 번 정리하는 게 필요할 것 같다.

  TCP/IP 네트워크 스택 이해하기

• Quick Sort의 성능 분석 및 정리해서 posting 했다.

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)

Python Class

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

class Account:
    # constructor
    # 객체를 생성할 때 "반드시" 한 번 호출한다.
    def __init__(self, cus_name, init_balance):
        # instance member
        self.name = cus_name
        self.balance = init_balance
        
    # descructor
    # 객체가 소멸될 때 "반드시" 한 번 호출
    def __del__(self):
        pass
    
    # instance method(operator)
    def deposit(self, money):
        if money < 0:
            print('0보다 작은 값을 저금할 수 없습니다.')
            return False
        
        self.balance += money        
        print(f'잔고 {self.balance}')
        return True
    
    def withdraw(self, money):
        if money > self.balance:
            print('잔고보다 출금하려는 돈이 더 많습니다.')
            return False
        
        self.balance -= money
        print(f'잔고 {self.balance}')
        return money
    
    def transfer(self, other, money):
        self.balance -= money
        # 다른 object의 member에 바로 접근하지 않는다!! (private없어서 접근 할 수는 있음(뭐임?))
        # 다른 object의 member는 "반드시" 상대 object의 method를 호출해서 접근해야 한다. - Message Passing
        other.deposit(money)
        print(f'잔고 {self.balance}')

Object : abstraction method (추상화 도구)

• 관련 있는 변수(member)와 기능(operator, method)를 묶어서 하나의 object로 만든다.
• Operator를 통해서만 member에 접근할 수 있다.

Class와 Instance, object의 차이

• 클래스(class)란 똑같은 무엇인가를 계속해서 만들어낼 수 있는 설계 도면 같은 것이고(과자 틀), 객체(object)란 클래스에 의해서 만들어진 피조물(과자틀에 의해서 만들어진 과자)을 뜻한다.
• class에 의해서 만들어진 Object를 instance라고도 한다. 그렇다면 Object와 Instance의 차이는 무엇일까?
  이렇게 생각해 보자. a = Cookie() 이렇게 만들어진 a는 Object이다. 그리고 a라는 Object는 Cookie의 Instance이다.
• 즉, Instance라는 말은 특정 Object(a)가 어떤 Class(Cookie)의 객체인지를 관계 위주로 설명할 때 사용된다. 즉, “a는 instance” 보다는 “a는 object”라는 표현이 어울리며, “a는 Cookie의 object” 보다는 “a는 Cookie의 instance”라는 표현이 훨씬 잘 어울린다.

Public, Private and Protected | Python Access Modifier

C++, Java와 같이 클래식한 object-oriented 언어에서는 public, private, protected와 같은 키워드로 class의 member에 대한 접근을 제어한다. Class의 Private member는 class 외부에서 접근이 불가능하며 class 내부에서만 접근될 수 있다.

Class 내의 Public member는 class 외부에서도 접근할 수 있다. 같은 class의 object는 public method를 호출하도록 요구된다. Private instance variable과 public method를 함께 써야지만 데이터 encapsulation의 원칙에 따르는 것이다.

Class의 protected member는 오직 해당 class와 그 class를 상속받은 child class만이 접근할 수 있다. 이는 parent class가 child class에게 특정한 리소스를 상속할 수 있게 한다.

그런데 Python은 instance variable과 method에 대해서 접근 제한을 하는 방식이 따로 없다. Python vaiable이나 method의 이름 앞에 한개 또는 2개의 _(underscore)를 붙여서 protected와 private으로 구분하기로 약속한다.

Public Attributes

1
2
3
4
5

class Account:
    def __init__(self, cus_name, init_balance):
        # instance member
        self.name = cus_name
        self.balance = init_balance

Protected Attribute

1
2
3
4
5

class Account:
    def __init__(self, cus_name, init_balance):
        # instance member
        self._name = cus_name
        self._balance = init_balance

Private Attribute

1
2
3
4
5

class Account:
    def __init__(self, cus_name, init_balance):
        # instance member
        self.__name = cus_name
        self.__balance = init_balance

그런데 웃긴 건, underscore로 name mangling한 private variable을 class 외부에서 접근이 가능하다는 것이다. 다음의 방법을 사용하면 된다.

1
2

myAccount = Account('subin', 10000)
myAccount._Account__balance

정말 필요하다면 접근할 수 있지만, Python에서는 접근하지 말 것을 권고하고 있다.

참고 자료

• 점프 투 파이썬
• TutorialsTeacher

Today I Learned

오늘 한 일

• Python Class 선언과 instance를 만드는 방법에 대해서 배웠다.

• Object-Oriented Programming에 대해서 정리한 내용을 포스팅했다. ✨4 Fundamentals of OOP

• Python Access Modifier에 대해서 알고 정리했다.

• Network 계층 및 Eathernet과 IP Protocol에 대해서 배웠다.

• Quick sort | Divide and Conquer - Python으로 Code를 짰다

추상화 | 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)

Today I Learned

오늘 한 일

• Big-O notation을 다시 한 번 정리하며 성능순으로 정리했다.

1. O(1) : 상수 시간
   • 엄청 빠름
   • array의 indexing, linked list의 insert, delete
2. O(logn) : 로그 시간
   • Binary Search Tree의 insert, search, delete
3. O(n) : 선형 시간
   • linked list의 search, 특정 array의 insert, delete
4. O(nlogn) : 선형 로그 시간
   • quicksort, merge sort
   • comparision sorting의 경우 quick sort보다 성능 좋을 수 없다.
5. O(n²) : 지수시간(?)
   • bubble sort, select sort, insert sort 등

• Memory | Performance of fbstring

  Memory에 관련된 영상 하나를 보고 Memory 공부를 했다. Performance of fbstring

  나는 전공 수업에서 OS를 들으며 배웠던 내용이라, 그 때 배웠던 것들을 처음부터 정리하며 복습 했다.

• Process and Thread

  어렵고 다룰 게 많은 주제인데 한 번에 후다닥 나가는 느낌이라 아쉬웠다. OS를 복습할 겸 Chapter 별로 정리해 포스팅할 계획을 세웠다.

• Process와 Memory 개념 정리

• Codewars 5kyu Sum of Pairs 문제를 풀었다. 자꾸 Timeout이 나서 성능을 좋게 만들려고 최대한 노력했다.

Today I Learned

오늘 한 일

• Python Functions(호출 방식, stack, map filter 등)을 배우고 posting으로 정리했다.

• LeetCode 알고리즘을 풀고, 알고리즘 스터디를 했다.

First-class Function

• 프로그래밍 언어 중 함수를 다른 변수와 동일하게 다루는 언어를 함수우선순위(First-class Functions) 가졌다고 표현한다.
• 함수를 다른 함수의 argument로 사용하고, 함수에서 함수를 return하거나 변수의 값으로 함수를 할당할 수 있다.

1. 변수에 함수를 할당

   1 2 3 4 5

   const foo = function() { console.log("foobar"); } // 변수를 사용하여 호출 foo();

2. 함수를 인자로 전달

   1 2 3 4 5 6 7 8

   function sayHello() { return "Hello, "; } function greeting(helloMessage, name) { console.log(helloMessage() + name); } // `sayHello`를 `greeting` 함수에 인자로 전달 greeting(sayHello, "JavaScript!");

• 다른 함수에 인자로 전달된 함수를 Call Back 함수라고 한다.
• 다른 언어들과 같이 sayHello()를 호출하면 바로 실행되지만, 위와 같이 greeting(satHello, “)의 인자로 전달된 sayHello의 경우 greeting 함수의 helloMessage parameter로 전달된 후에, 필요한 경우 helloMessage()에서 호출된다.
• 전달된 이후 나중에 호출되기 때문에 CallBack 함수라고 불린다.

3. 함수를 return 값으로 전달 (함수 return)

   1 2 3 4 5

   function sayHello() { return function() { console.log("Hello!"); } }

   • 함수가 함수를 반환하는 예시문. JavaScript에서는 함수를 변수처럼 취급하므로 함수를 return할 수 있다.
   • Higher-Order Function : 함수를 반환하는 함수

우선 Parameter와 Argument의 차이를 짚고 가도록 한다.

Parameter

The names given in the function definition are called Parameters.

Argument

The values supplied in the function call are called Arguments.

Call by Value

• 함수를 호출할 때, 변수의 값을 복사하여 argument로 넘기는 것

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

  #include <stdio.h> void change_value(int x, int val) { x = val; printf("x : %d in change_value \n", *x); } int main(void) { int x = 10; change_value(x, 20); printf("x : %d in main \n", x); }

  

  • 위 코드에서는 단순히 x에 10이라는 값이 복사되어 들어가기 때문에, change_value(x, 20)에서 x를 변경하더라도 main 함수에서의 x에 영향을 미치지 못한다.

Call by Reference

• 함수를 호출할 때 변수의 값을 넘기는 것이 아니라, 변수의 주소(변수의 위치)를 복사하여 함수에 넘긴다.

• 넘겨받은 주소로 실제 변수에 접근하고 값을 변경할 수 있다.

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

  #include <stdio.h> void change_value(int * x, int val) { *x = val; printf("x : %d in change_value \n", *x); } int main(void) { int x = 10; change_value(&x, 20); printf("x : %d in main \n", x); }

  

• 주소값을 전달 (참조값을 전달) : 주소값을 알고 있으면 해당 memory 주소에 저장되어있는 값을 참조할 수 있다.

• *x가 x를 참조하고 있다 : 가리키고 있다.

  이를 이해하기 위해서는 pointer에 대한 이해가 필요하다.

• Pointer

  1 2 3

  int *pnum; int num = 12345; pnum = &num //num의 주소값을 return하여 pnum에 저장

  • 변수를 만들 때 변수 이름 앞에 *를 붙이면 pointer 변수 됨
  • &연산자: &오른쪽에 오는 피연산자의 주소값을 반환
  • *연산자: 포인터가 가리키는 메모리 공간에 접근할 때 사용되는 연산자. 포인터 변수를 이용해 포인터 변수가 가리키는 변수의 값을 바꿀 수도 있다.

Call by Assignment (Call by Object Reference)

The actual parameters (arguments) to a function call are introduced in the local symbol table of the called function when it is called; thus, arguments are passed using call by value (where the value is always an object reference, not the value of the object). [1] When a function calls another function, a new local symbol table is created for that call.

이 문장이 나를 얼마나 헷갈리게 했는지 모른다. 그러니까 Python에서는 function의 argument가 call by value로 넘어오는데, 그 value는 언제나 object의 값이 아닌 object의 reference라는 것이다.

Actually, call by object reference would be a better description, since if a mutable object is passed, the caller will see any changes the callee makes to it (items inserted into a list).

정확하게는 call by object reference라는 설명이 더 맞다. 왜냐면 mutable 객체가 넘어올 때에는 call by reference처럼 원본 값을 변경할 수 있기 때문이다.

• 파이썬은 모든 것이 object이고, Object에는 두 종류가 있다.

1. Immutable object
   • int, float, str, tuple
   • Immtable 객체가 함수의 인자로 전달되면, 처음에는 call by reference로 받지만 값이 변경되면 call by value로 동작한다.
   • 즉, 함수 내에서 formal parameter 값이 바뀌어도 actual parameter에는 영향이 없다.
   • 함수 내부에서 값을 변경할 수 없다!
   • 그래서 tuple은 변경하려면 함수에서 element와 tuple 인자로 넘겨 아예 새로 할당해줘야 함
2. Mutable object
   • list, dict, set
   • Mutable 객체가 함수의 인자로 넘어가면 call by reference도 동작한다. 즉, object referene가 전달되어 actual parameter의 값에 영향을 미칠 수도 있다.
   • 새로운 객체를 할당하는 게 아니라면, 함수 내부에서 값을 변경할 수 있다!

정리

• Python은 함수를 실행할때 Call by reference같은 느낌으로 reference를 넘겨준다. 하지만 이때 넘겨주는 것은 변수(Variable)의 reference가 아니라 변수가 담고 있는 자료(Data)의 reference이다.
• 자료가 mutable하다면 변경해도 reference가 보존되므로 결과적으로 Call by reference처럼 보일 것이고, 자료가 immutable하다면 결과적으로 Call by value처럼 보일 것이다.