Scribbling

Decorator는 이미 만든 함수를 수정하지 않고, 함수 주변을 감싸는 방식으로 함수에 추가 기능을 구현한다. def trace(func): # wrapper는 아래처럼 가변 인수로 만들 수 있다. # 가변 인수가 아닌 경우, 원래 함수의 parameter 형태와 일치해야 한다. def wrapper(*args, **kwargs): ret = func(*args, **kwargs) print('{0}(args={1}, kwargs={2}) -> {3}'.format(func.__name__, args, kwargs, ret)) # 원래 함수가 return이 필요한 경우에는 wrapper도 return이 필요하다. return ret return wrapper @trace def get_max(*args..

1. Iterator __iter__, __next__를 가진 객체를 iterator protocol을 지원한다고 일컫는다. class Counter: def __init__(self, limit): self.num = 0 self.limit = limit def __iter__(self): return self def __next__(self): if self.num < self.limit: ret = self.num self.num += 1 return ret else: raise StopIteration for i in Counter(10): print(i, end=' ') 클래스에서 __getitem__ 메서드만 구현해도 이터레이터가 된다. class Counter: def __init__(sel..

2019 카카오 코딩 테스트 기출 문제라고 한다. 단순 구현문제다. from collections import defaultdict def solution(record): results = [] record_dict = defaultdict(list) nickname_dict = {} for rec in record: rec = rec.split(' ') if rec[0] == 'Enter': user_id, nickname = rec[1], rec[2] results.append(nickname + "님이 들어왔습니다.") record_dict[user_id].append(len(results) - 1) if user_id not in nickname_dict: nickname_dict[user_id]..

O(N) 알고리즘. class Solution: def longestConsecutive(self, nums: List[int]) -> int: longest = 0 nums = set(nums) for num in nums: if num - 1 not in nums: cnt = 1 while num + 1 in nums: num += 1 cnt += 1 longest = max(longest, cnt) return longest class Solution: def longestConsecutive(self, nums: List[int]) -> int: numSet = set(nums) longest = 0 while nums: cnt = 1 l = r = nums.pop() numSet.discard(..

난이도가 꽤 높은 그래프 문제이다. 방이 만들어지는 조건을 따져야 한다. * 방이 만들어지는 조건 - 재방문한 점이다. - 타고온 edge는 첫 방문이다. 여기까지는 생각하기 쉬운데, 문제는 아래와 같은 케이스다. 현재 알고리즘은 위의 그림에 대해 방을 1개로 파악한다. 이는 가운데 교차점을 정점으로 생각하지 않기 때문이다. 이 문제를 해결할 방법은 여러가지인데, 가장 간단한 방법은 하나의 화살표에 대해 이동을 2번 반복하는 것이다. def solution(arrows): answer = 0 dx = (0, 1, 1, 1, 0, -1, -1, -1) dy = (-1, -1, 0, 1, 1, 1, 0, -1) vertex = set() vertex.add((0, 0)) edge = set() cur = [..

아래 문제와 거의 같다. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: wordSet = set(wordList) wordSet.discard(beginWord) if endWord no..

다익스트라 알고리즘을 사용한다. 참고: https://focalpoint.tistory.com/6 최단 거리 알고리즘 최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq focalpoint.tistory.com import heapq def solution(n, edge): answer = 0 max_dist = 0 graph = [[] * (n+1) for _ in range(n+1)] for e in edge: u, v = e graph[u].append(v) graph[v].append(u) dista..

At each node, we have to do two jobs. First: update the global sum with the path going through node, node's left child, and node's right child Second: either choose node's left child or node's right child to return a partial path than can be connected to current node's parent - here we can't choose both left child and right child because if we choose both of them, that path can't be connected to..

LeetCode에서 푼 문제 중 가장 어려웠다... 당연히 빡대가리 내 머리로는 못 풀었고, 다른 사람 풀이 보고 이해하는 데에도 한참 걸렸다. DP로 풀어야하는데, 점화식은 아래와 같다. O(NK) Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/655837/Python-Very-Detailed-Explanation-with-thought-process-DP 위 점화식에 대한 예제이다. P = [3, 3, 5, 0 0, 3, 1, 4], K = 3 class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if not prices: return..

class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ n = len(prices) leftprofit, rightprofit = [0] * n, [0] * n leftmin = prices[0] for i in range(1, n): price = prices[i] leftmin = min(leftmin, price) leftprofit[i] = max(leftprofit[i-1], price - leftmin) rightmax = prices[-1] for i in range(n-2, -1, -1): price = prices[i] rightmax = max(rightmax, pric..