pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 g 이상인 값을 s와 매칭할 수 있는 최대 개수 책에서 구현된 코드 # 그리디 알고리즘 from typing import List class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() child_i = cookie_j = 0 # 만족하지 못할 때까지 그리디 진행 while child_i = g[child_i]: child_i += 1 cookie_j += 1 return child_i # 이진 탐색 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 주유소를 원형 큐에서 시계방향으로 돌 때, 현재 채울 수 있는 gas와 다음 주유소의 cost로 모든 주유소에 도달할 수 있는 시작점 출력 책에서 구현된 코드 from typing import List class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: # 모든 주유소 방문 가능 여부 판별 if sum(gas) < sum(cost): return -1 start, fuel = 0, 0 for i in range(len(gas)): # 출발점이 안되는 지점 판별 if gas[i] + fuel < cost[i]..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 n개 안에 겹치는 문자가 없도록 배열, 불가능할 경우 "idle"을 삽입하여 최소 길이 출력 책에서 구현된 코드 import collections from typing import List class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: counter = collections.Counter(tasks) result = 0 while True: sub_count = 0 # 개수 순 추출 for task, _ in counter.most_common(n + 1): sub_count += 1 result += 1 counter.s..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 (내 키, 앞에 줄 선 사람 중 내 키 이상인 사람)이 주어질 때 재정렬 책에서 구현된 코드 import heapq from typing import List class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: heap = [] # 키 역순, 인덱스 삽입 for person in people: heapq.heappush(heap, (-person[0], person[1])) result = [] # 키 역순, 인덱스 추출 while heap: person = heapq.heappop(heap) resul..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 주식 가격이 시간순으로 주어질 때 최대 이익 출력 책에서 구현된 코드 from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: # 0보다 크면 무조건 합산 return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1)) 기억해야할 기법 "그리디 알고리즘으로 접근해야한다"는 힌트를 어디서 얻을 수 있을까 문제를 잘 해석하면 모든 이익의 합산이다 sell & buy를 동시에 할 수 있다는 것을 캐치하면 쉬운 문제였다 나는 나중에 팔았을 때 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 요약 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 (코딩 테스트에서의 정의를 의미하는듯? -> 항상 글로벌 최적을 찾기는 어려울 듯) 그리디 알고리즘 드물게 최적해를 보장하는 경우도 있음 보통 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음 최적해를 찾을 수 있는 두 가지 조건 탐욕 선택 속성 (Greedy Choice Property) - 앞의 선택이 이후 선택에 영향을 주지 않음 - 즉, 문제 해결 과정 중 substructure마다 독립적인 문제 해결 최적 부분 구조 (Optimal Substructure) - 문제의 최적 해결 방법이 부분 문제에 대한..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 문자열 s에 대해 k개를 변경하여 만들 수 있는 가장 긴 반복문자열의 길이 출력 책에서 구현된 코드 class Solution: def characterReplacement(self, s: str, k: int) -> int: left = right = 0 counts = collections.Counter() for right in range(1, len(s) + 1): counts[s[right - 1]] += 1 # 가장 흔하게 등장하는 문자 탐색 max_char_n = counts.most_common(1)[0][1] # k 초과시 왼쪽 포인터 이동 if right - left - max_char_n..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 t의 모든 문자, 개수가 포함된 s의 최소 윈도우 출력 책에서 구현된 코드 import collections class Solution: def minWindow(self, s: str, t: str) -> str: need = collections.Counter(t) missing = len(t) left = start = end = 0 # 오른쪽 포인터 이동 for right, char in enumerate(s, 1): missing -= need[char] > 0 need[char] -= 1 # 필요 문자가 0이면 왼쪽 포인터 이동 판단 if missing == 0: while left < right..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 k개의 슬라이드마다 최대값을 담아 출력 책에서 구현된 코드 # 테스트케이스 변경으로 현재 책의 방식으로 통과되지 않음 (책에도 이슈관련 내용이 적혀있음) # github에 다른 분이 작성하신 수정된 방식 from collections import deque from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: deq, ans = deque(), [] for i in range(len(nums)): # 앞에서부터 out of window -> 제거 if deq and i-de..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 슬라이딩 윈도우 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용하는 문제를 풀이하는 알고리즘 네트워크에 사용되던 용어 (MAC 계층에서 본 적 있음) 알고리즘 문제 풀이에 매우 유용하게 사용되는 중요한 기법 투포인터와의 차이점 고정 사이즈 윈도우를 사용함 정렬 여부에 관계없이 활용 좌->우로만 이동