leetcode30 leetcode 322 - Coin Change dp문제.. 매우 어렵다. greedy로 접근하기 쉬운데, 코인과 amount가 greedy로 풀리지 않는 경우가 있다. DFS적 접근으로 결정 트리를 그려보면 이해하기 쉽다. 브루트포스로 amount에서 coins의 경우를 선택해 나간다고 생각해보자. 케이스 1 에서 처음 1,2,5 중 하나의 선택을 하게 된다. 1을 택했다면 , amount는 10이되고 여기서 또 125의 선택을 반복해 나간다. 예를 5를 택했다면 amount 는 5의 상태로 코인 1,2,5에서의 선택. 즉 amount에 따른 subtask가 계속 생긴다고 볼 수 있다. dp bottom up 접근이 가능 class Solution: def coinChange(self, coins: List[int], amount: int) -> i.. 2023. 5. 2. leet code 70 - Climbing Stairs 첫번째 dp문제.. 결정 트리를 그려봐야한다. 나의 풀이 처음에는 2가 몇개 있는가에 따라서 조합으로 규칙을 구할 수 있을 것이라고 생각했다, 규칙 x 구현 실패. 브루트포스 레벨 0의 계단 0 에서 시작해, 발생하는 경우의수 한칸 가는 경우, 두칸 가는 경우에 대해 모든 경우를 계산한다. 각 트리에서 5가 되는 노드가 발생하는 경우의 수를 전부 센다. 이진 트리의 형태를 보이며 DFS와 유사하다. 시간 복잡도 2^height. height == n+1 바텀업 dp를 활용한 풀이 동적 프로그래밍이란.. 하나의 거대한 전체 문제를 sub task 로 분할해 푸는 방법이다. 메모이제이션. 기존 풀이했던 동일한 문제의 정답을 저장해 가져와 활용하는 문제 풀이법. 이미 알고 있는 결과에 대해 저장만 확실하게 하.. 2023. 4. 25. Leetcode 11 - Container with Most Water 브루트포스 class Solution: def maxArea(self, height: List[int]) -> int: res = 0 for l in range(len(height)): for r in range(l + 1, len(height)): area = (r - l) * min(height[l], height[r]) res = max(res, area) return res 가능 한 모든 경우의 수를 판단한다. l , r포인터를 포문으로 이동하고 가능한 모든 조합에 대한 영역 값을 계산해 결과값 구함. 시간복잡도 n^2 포인터 활용 풀이 class Solution: def maxArea(self, height: List[int]) -> int: res = 0 l,r = 0, len(height) .. 2023. 4. 24. leet code 15 - 3SUM 수상한 제목을 가진 문제.. 파이썬 모듈을 이용한 풀이. from itertools import combinations class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: #ijk는 서로 다르다. ijk값을 더하면 0이다. #똑같은 tripet이 있어서는 안된다. # 서로다른 인덱스 세개의 값을 뽑아서 0 이 되게 해라. # 똑같은 triplet은 안된다. #모든 조합을 구하고 #구한 조합중 겹치는게 있다면 0으로 만들면 어떨까? ls1 = [] ls2 = [] for i in combinations(nums, 3): ls1.append(sorted(i)) ls1 = list(map(list,set(map(tuple,ls1))).. 2023. 4. 22. 이전 1 2 3 4 5 6 7 8 다음
