Scribbling

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..

무언가를 예측하고, 그 예측이 맞아떨어지는 것을 확인하는 일은 참 즐겁다. 2021 롤드컵 결승전 3Set 양팀의 밴과 픽은 8강을 앞두고 적어둔 티어리스트의 내용에 정확하게 부합되었다. 오늘은 결승전 3Set 밴&픽의 내용을 복기해둔다. 블루 밴 - 키아나, 라칸, 그레이브즈 DWG가 2set에 잘 활약했던 키아나와 라칸을 밴해주었다. 여기서 주목해야 할 점은 EDG가 트페 밴을 풀었다는 것. 레드 밴 - 유미, 나미, 자르반 EDG가 트페 밴을 하지 않은 것에 대한 DWG의 밴 대응이 훌륭했다. 변수가 될만한 유미와 나미(루시안)을 자르고, 보통은 리신을 밴 해야 하지만, 리신을 밴하지 않음으로써 압도적 1티어 픽 3개(트페, 리신, 아펠) 중 2개를 가져올 수 있게 되었다. 블루 1픽 - 트페(독보..

다익스트라 알고리즘을 사용한다. 참고: 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..