일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Python Code
- Python
- 시바견
- concurrency
- data science
- 30. Substring with Concatenation of All Words
- 컴퓨터의 구조
- 프로그래머스
- 운영체제
- t1
- LeetCode
- 43. Multiply Strings
- Generator
- Class
- iterator
- Convert Sorted List to Binary Search Tree
- attribute
- Protocol
- 밴픽
- 파이썬
- Regular Expression
- kaggle
- 315. Count of Smaller Numbers After Self
- Decorator
- Python Implementation
- 109. Convert Sorted List to Binary Search Tree
- DWG
- Substring with Concatenation of All Words
- shiba
- 715. Range Module
- Today
- Total
목록시바견 (122)
Scribbling
Floyd-Warshall 알고리즘을 사용한다. https://focalpoint.tistory.com/6 최단 거리 알고리즘 최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq focalpoint.tistory.com def solution(n, results): graph = [[0] * (n+1) for _ in range(n+1)] for result in results: w, l = result graph[w][l] = 1 graph[l][w] = -1 for k in range(1, n+1): f..
다익스트라 알고리즘을 사용한다. 참고: 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..
class Solution: def maxProfit(self, prices: List[int]) -> int: profit, prev = 0, prices[0] for i in range(1, len(prices)): if prices[i] >= prev: profit += prices[i] - prev prev = prices[i] return profit
전형적인 DP 문제 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = [[0] * (i+1) for i in range(len(triangle))] dp[0][0] = triangle[0][0] for i in range(1, len(triangle)): dp[i][0] = dp[i-1][0] + triangle[i][0] for j in range(1, i): dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[i][-1] = dp[i-1][-1] + triangle[i][-1] return min(dp[len(triangle)-1])
""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution: def connect(self, root: 'Node') -> 'Node': self.helper(root) return root def helper(self, node): if not node: return leftmost, prev = None, None cur = node while cur: if c..
개인적으론 매우 어려웠던 문제이다. Binary Search를 이용하라는 힌트가 있음에도 풀지 못하였다. 처음 떠올렸던 방식은 O(N**2)이었는데 N이 너무 커서 안될것 같았다. 이래저래 Binary Search를 적용할 방안을 떠올려보았지만, 끝까지 생각이 나지 않아 구글링을 해따... 아이디어는 매우 간단하다. --> 돌 사이의 간격에 대해 binary search를 하면된다. 효율성은 O(log(D)*N)이므로 최선의 알고리즘이다. def solution(distance, rocks, n): answer = -1 rocks.sort() rocks.append(distance) l, r = 0, distance while l = mid: prev = rock else: num_removed += 1..