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

개발

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

대왕판다 2022. 8. 11. 14:27

오늘 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.
```