[북TIL] 파이썬 알고리즘 인터뷰 7장 배열

오늘 TIL 3줄 요약

• 브루트포스, 투포인터는 생각보다 다양한 풀이에서 써먹을 수 있다.

• 그러나 두 방법보다 효율이 좋은 풀이도 존재한다.

• 파이썬은 쓰기 쉬운 언어다. 그러나 Go나 C(++)에 비해 성능이 부족한걸 기억하고 푼다.

   

TIL (Today I Learned) 날짜

• 2020 08.05. FRI. ~ 08.11. THU

   

오늘 읽은 범위

• 파이썬 알고리즘 인터뷰 7장 배열

   

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

• 추상자료형(ADT)의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다.

• 파이썬과 같은 동적 프로그래밍 언어는 정적 배열 자체를 제공하지 않는다.

• 동적 배열은 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 복사하는 식이다.

• 비교, 탐색을 쓰지 않는 두 수의 합 풀이 //

  # 덧셈하여 타겟을 만들 수 있는 두 숫자 인덱스를 리턴하라
  # 입력값
  nums = [2,7,11,15], target = 9 
  # 풀이
  def twoSum(self, nums:list[int], target:int) -> list[int]:
      nums_map = {}
      # 키와 값을 딕셔너리로 바꿔서 저장
      for i, num in enumerate(nums):
          nums_map[num] = i
      
      # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
      for i, num in enumerate(nums):
          if target - num in nums_map and i != nums_map(target-num):
              return [i, nums_map[target-num]]
            
  ### 위 for 문을 합친다면 
  def twoSum(self, nums:list[int], target:int) -> list[int]:
      nums_map = {}
      for i, num in enumerate(nums):
          if target - num in nums_map:
              return [nums_map[target-num], i]
          nums_map[num] = i
          # 타겟이 4,14,22 등과 같이 리스트 요소를 중복 사용하여 더할 수 있는 경우의 예외처리가 중요한데
  				# target-num 값을 넘스맵과 비교하고 난 후 넘스맵에 붙이는 형식으로 이를 처리한 점이 인상적이다.
  

• 최댓값, 최솟값을 sys.maxsize 로 지정하는 부분이 신박했다. None으로 잡아둘 경우 비교할 수 없고 일반적으로 선언하는 0보다 안전하다.

 

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

• 알고리즘 문제 풀이와 구현을 보다보면, 그 연결 고리가 이해가 되지 않을때가 있다.

  • 예를들면, 리트코드 42번 빗물 트래핑 문제에서 스택을 활용한 풀이가 있다.
  • "변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 이전과의 차이만큼 물 높이를 채워 나간다 " 가 풀이의 핵심인데, 구현을 보면
  • distance 와 waters 를 각각 구해서 곱을 volume에 더해주는데 distance가 왜 구현됐는지 내 머리로는 아직 이해가 안되는 것이다.

• 예제 인풋값을 넣어보면 결국 답이 나옴을 이해하지만, 사실 이런 피상적인 이해로 문제가 주어졌을때 내가 풀어낼수 있을까 하는 의문이 있다.

• 간단한(그러나 생각해내기 어려운) 예외처리가 코드의 질을 높인다는 것을 다시한번 상기하게 되었다.

   

   

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

• Python method 속의 self 역할?

  [파이썬에는] 메서드에서 객체의 멤버를 참조하는 약어가 없습니다. 메서드 함수는 호출에 의해 암시적으로 제공되는 객체를 나타내는 명시적 첫 번째 인수로 선언됩니다.

  종종 메서드의 첫 번째 인수를 self라고 합니다. 이것은 관례에 불과합니다. self라는 이름은 파이썬에 전혀 특별한 의미가 없습니다. 그러나 규칙을 따르지 않으면 가독성이 떨어질 수 있습니다.

  '''
  Let's say you have a class ClassA which contains a method methodA defined as:
  '''
  def methodA(self, arg1, arg2):
      # do something
  
  '''
  and ObjectA is an instance of this class.
  
  Now when 
  # ObjectA.methodA(arg1, arg2) # is called, 
  python internally converts it for you as:
  '''
  ClassA.methodA(ObjectA, arg1, arg2)
  
  # The SELF variable refers to the object ITSELF.