Scribbling

def solution(m, n, puddles): dp = [[0] * m for _ in range(n)] dp[0][0] = 1 for i in range(1, m): if [i+1, 1] in puddles: continue dp[0][i] = dp[0][i-1] for i in range(1, n): if [1, i+1] in puddles: continue dp[i][0] = dp[i-1][0] for i in range(1, n): for j in range(1, m): if [j+1, i+1] in puddles: continue dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1] % 1000000007

굉장히 전형적인 DP 문제 def solution(triangle): h = len(triangle) dp = [[] for _ in range(h)] dp[0].append(triangle[0][0]) for i in range(1, h): dp[i].append(dp[i-1][0] + triangle[i][0]) for j in range(1, i): dp[i].append(max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]) dp[i].append(dp[i-1][-1] + triangle[i][-1]) return max(dp[h-1])

난이도가 높지는 않은 문제. N을 1개씩 늘려가면서 완전탐색하되, number가 있는지 확인한다. 예컨대... 5가 네개인 경우를 완전탐색하려면, (5, 5, 5, 5) (5) + (5, 5, 5) (5, 5) + (5, 5) (5, 5, 5) + (5) 위의 모든 케이스를 다 따져 주면 된다. 여기서 +는 더하라는 의미가 아니라, 왼쪽에서 발생되는 모든 케이스와 오른쪽에서 발생되는 모든 케이스를 조합하는 모든 케이스를 생성하라는 의미이다. def solution(N, number): if number == N: return 1 dp = [[] for _ in range(9)] dp[1] = [N] for i in range(2, 9): dp[i].append(int(str(N)*i)) for j in ..

1. 요구 페이징 1.1 요구 페이징 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것이 가져오기 정책이다. 일반적으로 프로세스가 요청할 때 메모리로 가져오는데, 일르 요구 페이징(Demang Paging)이라고 한다. 컴퓨터를 오래 켜둔 상태로 사용하다보면 느려진다. 그 이유는 작업을 하지 않고 쉬는 프로세스나 좀비 프로세스가 메모리를 차지하여 메모리 관리가 복잡해지기 때문이다. 덩치가 큰 프로세스는 모든 모듈이 메모리에 올라오지 않는다. 필요한 모듈만 올려두고 나머지 모듈은 필요시에만 메모리에 올려서 사용한다. 이러한 방식을 통하여 메모리를 효율적으로 관리 가능하며, 사용자에 대한 응답 속도를 향상시킬 수 있다. 포토샵을 예로 들어보자. 포토샵을 실행하면 기본적인 모듈이 메모리에 올..

2021롤드컵 8강 밴픽 티어 리스트 (기준일자: 2021-10-21 (목)) 1. 탑 1티어: 그레이브즈, 케넨, 제이스 - 그레이브즈: 무난한 선픽 카드. 라인 푸쉬 능력이 좋아서 상대 정글을 찾아주는 역할을 잘 수행하며, 갱 회피 능력도 매우 뛰어남. 선픽으로 뽑아도 성능이 좋은 확실한 1티어 챔프. - 케넨: 선픽이 가능한 카드. 카운터 픽은 꽤 있지만 버티는 플레이가 용이한 편. 한타 잠재력이 매우 뛰어난 픽으로 상대에게 탈진을 강요한다는 것도 장점. AD가 많이 나오는 현 메타에서 성능이 좋은 몇 안되는 AP라는 점 또한 큰 장점. 다만 다이브에 약함. - 제이스: 선픽이 가능한 카드. 역시 카운터 픽이 꽤 있음(오공, 이렐). 케넨에 비해 선픽 난이도가 더 높다고 보는 것이 맞으며, 블루2-..

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: return self.builder(inorder, postorder) def builder(self, inorder, postorder): if not inorder: return None head = TreeNode(val=postor..

route들이 최대한 잘 겹치게 만드는 것이 목표인 문제이다. 이런 문제는 input의 순서를 강제하는 것이 큰 도움이 되는 경우가 많은데, 여기서는 routes를 사전에 정렬하는 것이 이에 해당된다. 정렬이 필요한 이유에 대해서는 생각해 볼 필요가 있는데, 이 문제에서는 group간 겹치는 문제를 회피하기 위해서이다. 아래 예제를 보자. [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] groups = [[-20, -15] 정렬하면, [[-20, -15], [-18, -13], [-14, -5], [-5, -3]] 1) [-18, -13] 처리 group 내의 [-20, -15]와 겹치므로 group[0]를 [-20, -15]와 [-18, -13]의 교집합인 [-18, -15]..

섬을 연결하는 최소 비용을 구하는 문제로, 최소 신장 트리 문제에 해당된다. 자연스럽게 크루스칼 알고리즘을 떠올릴 수 있다. 최소 신장 트리 혹은 크루스칼 알고리즘이 궁금하다면, 아래 링크로! (간단히 말하자면, 크루스칼 알고리즘은 비용이 가장 적게 드는 edge부터 연결시켜가는 알고리즘이다) https://focalpoint.tistory.com/15 신장 트리, 최소 신장 트리, Kruskal Algorithm 1. 신장 트리: 모든 node를 포함하면서 cycle이 존재하지 않는 그래프를 의미한다. 2. 최소 신장 트리: 신장 트리 중에서 최소 비용으로 만들 수 있는 트리 3. Kruskal Algorithm: 최소 신장 트리를 찾는 알 focalpoint.tistory.com def solutio..

몸무게로 줄을 세우고, 돼지와 홀쭉이를 매칭시켜준다. def solution(people, limit): answer = 0 people.sort(reverse=True) i, j = 0, len(people) - 1 while i

def solution(number, k): stack = [] for num in number: while stack and stack[-1] 0: k -= 1 stack.pop() stack.append(num) return ''.join(stack[:len(stack)-k])