파이썬 알고리즘 인터뷰 9, 10, 11장 - 스택, 큐, 데크, 우선순위 큐, 해시 테이블

오늘 TIL 3줄 요약

• 스택은 거의 모든 APP을 만들때 사용되는 자료구조로서, 스택과 연관된 알고리즘을 제대로 이해하느냐 못 하느냐에 따라서 기본 알고리즘을 설계할 수 있느냐 없느냐가 결정되기도 한다.
• FIFO로 처리되는 큐는 BFS, 캐시 등을 구현할 때 널리 사용된다. 데크나 우선순위 큐 같은 변형들도 유용하다. 성능을 위해 파이썬에서는 데크를 사용하는 것이 가장 좋다.
• 파이썬에서는 대부분의 우선순위 큐 풀이에 heaqpq 모듈을 사용한다.

TIL (Today I Learned) 날짜

• d2022 10. 24. ~ 2022. 11.07

오늘 읽은 범위

• 파이썬 알고리즘 인터뷰 9장 스택, 큐, 10장 데크, 우선순위 큐, 11장 해시 테이블

책에서 기억하고 싶은 내용을 써보세요.

• 파이썬의 Global Interpreter Lock

 -  **하나의 스레드가 자원을 독점하는 형태로 실행**된다.


 -  번거로운 동시성 관리를 편하게 하기 위해, 스레드 세이프 하지 않은 CPython의 메모리 관리를 쉽게하기 위해


 -  GIL로 파이썬 객체에 대한 접근을 제한하는 형태로 설계했다.


 -  *스레드 세이프 - 멀티 스레드에도 안전한 프로그래밍 개념. 스레드 세이프 하지 않은 경우 1번 스레드 값이 2번 스레드에서 변경이 될 수 있어 문제가 발생한다.*


 -  CPython이 개발되던 1994년에는 CPU가 싱글코어로 GIL을 선택할 만했고, 디자인에 아무런 문제가 없었다. 하지만 지금처럼 멀티코어가 당연한 세상에서 이런 제약은 치명적이다. **파이썬이 왜 느린가?** 를 얘기할때 가장 자주 듣게 되는 요인!

• 해시테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상자료형을 구현하는 자료구조다.

• 해시테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간복잡도가 O(1)이라는 점이다. -> 데이터 양과 무관하게 빠른 성능 보장

• 충돌은 생각보다 쉽게 일어난다. 비둘기집 원리에 따라 생일이 같으려면 366명 이상이 모여야 할 것 같다. 그러나 실제로는 23명만 모여도 50%를 넘고, 57명이 모이면 99%를 넘어간다!

• # 위의 생일 중복자 실험 코드
  import random
  
  TRAIALS = 100000
  smae_birthdays = 0
  # 10만 번 실험 진행
  for _ in range(TRAIALS):
        birthdays= []
      # 23명이 모였을 때 생일이 같을 경우 same_birthdays +=1
      for _ in range(23):
            birthday = random.randint(1, 365)
          if birthday in birthdays:
                same_birthdays +=1
              break
          birthdays.append(biorthday)
  print(f"{same_birthdays / TRIALS * 100}") 
  # 50.708%

• 비둘기집 원리란 n개의 아이템을 m개의 컨테이너에 넣을 때, n>m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어있다는 원리

• 아무리 좋은 해시함수라도 충돌은 일어난다. 충돌이 발생할 경우

  1. 개별 체이닝으로 처리한다. 충돌 발생 시 연결 리스트로 연결하는 방식을 개별 체이닝이라고 한다.
  2. 오픈 어드레싱 방식으로 해결한다. 이는 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다.

• 로드팩터란 해시테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다. 이 로드팩터 비율에 따라 해시 함수를 재작성할지, 해시 테이블의 크기를 조정해야할지를 결정한다

• 리트코드 771번 보석과 돌의 한줄 풀이

  • # J = "aA",  S = "aAAbbbb"
    def numJewelsINStones(self, J:str, S:str) -> int:
        return sum(s in J for s in S) 
      # == return sum([True, True, True, False, False, False, False])
      # == return 3

• 파이썬의 zip() 함수

  • zip()함수는 2개 이상 시퀀스를 짧은 길이 기준으로 일대응 대응하는 새로운 튜플 시퀀스를 만든다

  • a = [1,2,3,4,5]
    b = [2,3,4,5]
    c = [3,4,5]
    zip(a,b) # <zip object at 0x105b6d0b0> (제너레이터)
    list(zip(a,b)) # [(1,2), (2,3), (3,4), (4,5)]
    list(zip(a,b,c)) # [(1,2,3), (2,3,4), (3,4,5)]

• 파이썬 아스테리스크 *

  • 별표, 아스테리스크라 부르는 는 *시퀀스 언패킹 연산자**다.

  • C의 포인터 변수와 혼동될 수 있지만 파이썬에는 포인터 변수가 존재하지 않는다.

  • 다음과 같이 활용될 수 있다.

  • fruits = ['lemon','pear','watermelon','tomato']
    print(*fruits) # lemon pear watermelon tomato

  • 위 zip()과 더불어 활용할 수 있다.

  • nums = [1,1,1,2,2,3] k = 2
    
    collections.Counter(nums).most_common(k) # [(1,3), (2,2)]
    # 언패킹을 하면
    list(zip(*collections.Counter(numse).most_common(k))) # [(1,2), (3,2)]
    # 언패킹을 하지 않으면
    list(zip(collections.Counter(numse).most_common(k))) # [((1,3), (2,2),)]
    

  • 함수의 파라미터가 되었을때는 반대로 패킹도 가능하다.

  • def f(*params):
          print(params)
    f('a','b','c')     # ('a','b','c')

  • 또 다른 예시. 변수의 할당도 묶어서 처리할 수 있다.

  • a, *b = [1,2,3,4]
    a # 1
    b #[2,3,4]

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

• 여전히 풀이 코드를 쉽게 읽어낼 순 없지만 조금씩 속도가 올라가는 듯하다. 화이팅.

궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

• abstract data type(ADT) 아래 정의를 따르는 데이터 구조의 모델이다.

  1. 데이터 컬렉션의 속성
  2. 데이터에 대해 수행할 수 있는 작업

  An ADT has two parts:

  1. 사용자가 볼 수 있는 항목: 개념적 그림(객체, 구조가 어떻게 구성되었는지에 대한 사용자의 견해). 개념 작업(사용자가 ADT에 수행할 수 있는 작업)
  2. 프라이빗 혹은 내부 파트로 구성되어 있습니다. 작업 구현(실제 구조가 어떻게 저장되는지)의 표현(실제 코드)

• 파이썬 heappush에서 추가 인자 삽입

  • # Tuple in heappush method args
    heappush(h, value)
    # Heap elements can be tuples. 
    # This is useful for assigning comparison values (such as task priorities)
    h = []
    heappush(h, (5, 'write code'))
    heappush(h, (7, 'release product'))
    heappush(h, (1, 'write spec'))
    heappush(h, (3, 'create tests'))
    heappop(h)
    (1, 'write spec')
    # https://docs.python.org/3/library/heapq.html
    
    # 책 274 페이지 'k개 정렬 리스트 병합' 문제 풀이 중
    for lst in lists:
          heapq.heappush(heap, (lst.val, lst))
    # TypeError: '<' not supported between instances of ListNOde and ListNode
    # (중복된 값을 넣을 수 없다는 에러) 가 있을때 오직 추가 방지만을 위해 추가 인자를 삽입한다.
    for lst in range(len(lists)):
          heapq.heappush(heap, (lists[i].val, i, lists[i]))