StudyPython and CE

Python 기초 - 4

Algorithm

  • Tower of Hanoi(하노이 탑)

    • 반드시 큰 쟁반이 아래에 있어야 한다.

    • 큰 쟁반이 작은 쟁반보다 위에 있을 수 없다.

    • 기둥1(_from), 기둥2(_by), 기둥3(_to)이 있다.

    • 기둥 1에서 기둥3으로 모두 이동시켜야 한다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      # (num - 1)개를 _from에서 _to를 이용하여 _by로 이동시킨다.
      # num(제일 큰 쟁반)을 _from에서 _to로 이동시킨다.
      # (n - 1)개를 _by에서 _from을 이용하여 _to로 이동시킨다.
      def hanoi(num, _from, _by, _to):
          #base case
          if num == 1:
              print(f'{_from}에서 {_to}로 {num}번째 쟁반 이동')
              return
        
          hanoi(num - 1, _from, _to, _by)
          print(f'{_from}에서 {_to}로 {num}번째 쟁반 이동')
          hanoi(num - 1, _by, _from, _to)

    • 함수가 동작하는 모습을 stack frame으로 그려본다.

    • “pythontutor.com”을 이용하여 함수가 동작하는 모습을 보는 것도 좋다.

    • 점화식 및 기저 조건을 잘 만드는 것이 중요하다.

    • stack frame에 쌓이는 모습을 call stack이라고 한다.

    • call stack 맨 위에 있는 frame이 실행 권한을 가진다.

    • 함수가 실행이 끝나지 않은 상태에서 위 frame에 실행 권한을 주는 것을 blocking이라고 한다.

      1
      2
      3
      4
      5
      6
      7
      8
      hanoi(3, 'A', 'B', 'C')
      >> A에서 C로 1번째 쟁반 이동
         A에서 B로 2번째 쟁반 이동
         C에서 B로 1번째 쟁반 이동
         A에서 C로 3번째 쟁반 이동
         B에서 A로 1번째 쟁반 이동
         B에서 C로 2번째 쟁반 이동
         A에서 C로 1번째 쟁반 이동

first class function

  • first class function 조건

  1. argument(parameter) - 매개 변수

    • 함수 자체를 매개변수로 다른 함수에 전달

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      def f(a, b):
          return a + b

      def g(func, c, d):
          return func(c, d)

      a = 10
      b = 20
      g(f, a, b)  # 함수 자체를 매개변수로 전달
      >> 30

  2. variable - 변수(값)

    • 함수를 변수에 할당

      1
      2
      3
      4
      5
      6
      def f(a, b):
          return a + b

      f_var = f  # 함수를 변수에 할당
      f_var(20 ,30)
      >> 50

  3. return - 반환

    • 다른 함수의 결과값으로 반환

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      def create_calc(kind):
          if kind == 'add':
              def add(a, b):
                  return a + b
              return add

          elif kind == 'sub':
              def sub(a, b):
                  return a - b
              return sub  # 다른 함수의 결과값으로 반환

      f = create_calc('add')
      f(10, 20)
      >> 30

기수법

  • 기수(radix)

  • 한 자리에 표현할 수 있는 수

  • 10진수 - 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9

  • 2진수 - 0, 1

  • 16진수 - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

    • ‘0b’는 2진수

      1
      a = 0b1010 # 0b는 2진수

    • ‘0x’는 16진수

    • hex()를 이용하여 16진수 변환

      1
      2
      3
      4
      5
      6
      hex(a) # 0x는 16진수
      >> '0xa'

      b = 0b10101111
      hex(b)
      >> '0xaf'

    • bin()을 이용하여 2진수 변환

      1
      2
      3
      c = 0xaf
      bin(c)
      >> '0b10101111'

Computer Engineering

  • 32bit와 64bit

    • 한 번에 보낼 수 있는 데이터의 양(32bit = 32개, 64bit = 64개)

    • 32bit는 메모리 주소로 4GB가 한계이다.(2^32 = 4,294,967,296)

    • 32bit CPU에서 4GB 이상의 램을 사용해도 사용할 수 없다.

    • 64bit는 2^64개만큼 쓸 수 있지만 실제로는 48bit 정도만 쓴다.

    • 1byte = 8bit -> 옥텟(octet)

  • 하드웨어의 추상화 / 언어의 추상화

    • Low - Level Language = Assembly Language

      • CPU가 바뀌면 다시 설계해야 하고 레지스트리까지 모두 알아야 한다.

      • 하드웨어에 의존적인 언어

    • High - Level Language = C, Python, Javascript

      • 제조사의 Complier만 있다면 어떤 CPU든 가능하다.

      • C 언어의 경우 int, short, char와 같이 메모리 바인딩을 해줘야 한다.

  • integer overflow

    • 1byte = 0 ~ 255(unsigned), -128 ~ 127

    • 4bytes = 0 ~ 2^32-1(unsigned), -2^31 ~ 2^31-1

    • char형 변수 a = 126이 두 번 증가하면 -128 ~ 127의 범위를 벗어남

    • 실제로 출력하면 128이 아닌 -128이 나오는데 이 것을 integer overflow라고 함

2의 보수

  • 양의 정수 표현

    • 부호 비트 0

    • 정수를 2진수로 표현

  • 음의 정수 표현

    • 부호 비트는 1

    • 정수를 2의 보수(two’s complement)로 저장

    • 1의 보수는 모든 비트를 반전시켜주기만 하면 된다.

    • 1의 보수한 상태에서 1을 더하면 2의 보수가 된다.

    • 2의 보수를 원래의 수에 더하면 자릿수가 바뀐다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      a = 43
      bin(a)
      >> '0b101011'
      # 양의 정수 43 = 0b00101011
      # 음의 정수 43 = 0b00101011 -(1의 보수)-> 0b11010100 -(2의 보수)-> 0b11010101


      # 정수를 메모리에 저장되는 'byte' 형태로 표현
      # to_bytes()의 마지막 인자는 정수를 표현하는데 2의 보수가 사용되는지 결정
      a.to_bytes(1, 'little', signed = True)
      >> b'+'

      # signed의 기본값 = False
      # 음의 정수가 주어지고, signed가 False면 OverflowError 발생
      (-43).to_bytes(1, 'little', signed = True)
      >> b'\xd5' # 0b11010101

    • CPU는 가산기로만 계산을 한다.

      • 9 - 4를 계산하면 9 + (-4)로 계산을 한다.

      • 9 = 0b1001

      • -4 = 0b0100 -> 0b1011 -> 0b1100

      • 0b1001 + 0b1100 = 0b10101 에서 4자리만 기억하므로 맨 앞을 빼면 0b0101 = 5

Algorithom

  • Linear search and Binary search

  • Binary search와 성능을 비교하기 위해 Linear search를 만든다.

  1. Linear search(선형 탐색)

    • 데이터가 모인 집합의 처음부터 끝까지 하나씩 순서대로 비교하여 찾음

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      def linear_search(li, target):
          """
          linear_search(li, target) -> idx
          반환값은 target이 있다면 target의 인덱스
          target이 없다면 None을 반환
          """
          for i in range(len(li)):
              if li[i] == target:
                  return i
            
          return None



      li = [5, 7, 2, 8, 3, 9, 1]

      linear_search(li, 8)
      >> 3

      print(linear_search(li,10))
      >> None

  2. Binary search(이진 탐색)

    • 데이터의 집합이 반드시 정렬된 상태어야 함

    • 시작 인덱스와 끝 인덱스 그리고 중간 인덱스를 정의

    • 원하는 인덱스가 중간 인덱스보다 작다면 끝 인덱스를 중간 인덱스보다 작게 만든다.

    • 원하는 인덱스가 중간 인덱스보다 크다면 시작 인덱스를 중간 인덱스보다 크게 만든다.

    • 시작 인덱스가 끝 인덱스보다 커지면 반복을 멈춘다.

      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
      def binary_search(li, target):
          """
          binary_search(li, target) -> idx
          반환값은 target이 있다면 target의 인덱스
          target이 없다면 None을 반환
          """
          start_idx = 0
          end_idx = len(li) - 1
        
          while start_idx <= end_idx:
              mid_idx = (start_idx + end_idx) // 2
              
              if li[mid_idx] == target:
                  return mid_idx

              elif li[mid_idx] > target:
                  end_idx = mid_idx - 1

              else:
                  start_idx = mid_idx + 1
                 
          return None

      li = [3, 5, 7, 8, 9, 11, 12]

      binary_search(li, 8)
      >> 3

      print(binary_search(li,13))
      >> None

  • 알고리즘 성능을 가늠하는 기준 : 시간

    • 절대 시간 : 컴퓨터 성능에 의해 기준 자체가 모호하므로 기준으로 삼기 어려움

    • 상대 시간 : 데이터의 개수(n)에 따른 연산 횟수를 가지고 비교

      • 알고리즘 성능을 상대 시간으로 결정하기로 함

      • 연산 횟수는 알고리즘 안에서 헤비하게 쓰이는 연산을 기준으로 삼음

      • 보통 비교 연산 부분을 기준으로 삼음(if문, for문…등등)

    • 알고리즘의 성능 3가지

      • 최선의 경우 : 알고리즘 성능에서는 잘 사용하지 않는다.

      • 평균의 경우 : quick sort Algorithm에서 쓰인다.

      • 최악의 경우 : 알고리즘 성능에서 많이 쓰인다.

    • 그래프 성능 비교 : Linear search < Binary search

Share