pythaac의 개발노트

프로그래밍 언어의 구현체 (Implementation) 우리는 파이썬을 이야기할 때 종종 언어 뿐만 아니라 구현체를 포함하여 말한다. 파이썬은 다양하게 구현될 수 있는 언어의 스펙일 뿐이다. When we speak of Python we often mean not just the language but also the implementation. Python is actually a specification for a language that can be implemented in many different ways. 프로그래밍 언어에서 말하는 구현체란, 위와 같이 실제 언어를 구현한 방식을 말합니다. 언어라는 것은 문법과 같이 정의된 추상적인 틀이며, 이에 대한 구현에 따라 동작 방식도 성능도 달라집..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 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..