알고리즘 썸네일형 리스트형 [leetcode] 916. Word Subsets 916. Word Subsets LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 words2 의 모든 문자열이 포함되어 있는 words1 의 문자열을 반환하는 문제이다. (subset) 나의 시도 이 풀이를 봤을 때 이중 루프 돌며, words1 과 word2 의 hashmap 을 비교하는 것밖에 생각나지 않았다. 참고로 문제 조건이 아래와 같았기 .. 더보기 [Algorithm] 217-Contains-Duplicate https://leetcode.com/problems/contains-duplicate/ Contains Duplicate - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 방법 1. HashSet 이용한 풀이 class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ inputNums = set() for i in (nums): input.. 더보기 [Algorithm] 213-house-robber2 https://leetcode.com/problems/house-robber-ii/ House Robber II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 시간복잡도 - O(n) : 똑같은 알고리즘(helper function) 2번 호출할 뿐임 2. 공간복잡도 - O(1) : don't need any extra data structure. just 변수 2개만 사용하고 있음. class Solution(object): def rob(self, n.. 더보기 [Algorithm] min-cost-climbing-stairs 문제 https://leetcode.com/problems/min-cost-climbing-stairs/ Min Cost Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 처음에 풀었을 때 - 매개변수로 주어지는 cost 배열을 이용 안 하고 dp 테이블을 따로 만듬 - 시간복잡도 올라감 class Solution(object): def minCostClimbingStairs(self, cost): cost.append(0) n = len.. 더보기 [Algorithm] 편집 거리 출처 - 이코테 p.382 문제 편집 거리 알고리즘.. 잘 이해 안 됐는데 거의 80% 정도까지 이해하도록 도와준 영상이 있다. 이분 영상 너무 좋다. 다른 영상도 계속 보면 도움될 것 같음 https://www.youtube.com/watch?v=XJ6e4BQYJ24&t=661s 여기서 감명깊었던게 "Adding a character to A is equivalent to deleting a character from B" 이다. def edit_dist(str1, str2): n = len(str1) m = len(str2) # 2차원 dp 테이블 초기화 (맨 첫번째 행열은 각각 빈 문자열) dp = [[0] * (m + 1) for _ in range(n + 1)] # dp 테이블 초기 설정 for.. 더보기 [Algorithm] 금광 문제 이코테 p.375 '금광' 문제 문제 2차원 테이블에서 채굴자가 얻을 수 있는 금의 최대 크기를 구하는 문제이다. 내 실수 2차원 테이블의 맨 왼쪽부터 채굴자가 얻을 금을 하나씩 선택해서 이어가는 느낌으로 풀었다. 이건 행마다 max 값을 고르는 선택의 느낌으로 풀면 안 된다. (이러면 결국 그리디가 되어버린다) 어떤 선택이 최적해가 될 지 모르기 때문에 결국에는 모든 맵에 대해서 최적해를 구해주어야 한다. 점화식은 나름 비슷하게 세웠는데, 애초에 내 풀이는 가정이 잘못 됐다. ('선택' 의 느낌으로 갔기 때문) 이 문제를 해결하는데 DP 를 선택해야하는 이유 최적 부분 구조인가 - YES 중복되는가 - YES for tc in range(int(input())): n, m = map(int, input.. 더보기 [Algorithm] 1로 만들기 이코테 p.217 피보나치 수열같은 느낌의 대표적인 dp 기본 문제다. 나는 bfs 가 먼저 떠올라서 bfs 로 풀었다. BFS 풀이 from collections import deque def bfs(n): q = deque() q.append((n, 0)) while q: x, cnt = q.popleft() if x == 1: print(cnt) exit() if x % 5 == 0 and x / 5 > 0 and not visit[x // 5]: newX = x / 5 visit[newX] = True q.append((newX, cnt + 1)) if x % 3 == 0 and x / 3 > 0 and not visit[x // 3]: newX = x / 3 visit[newX] = True q.. 더보기 [Algorithm] 떡볶이 떡 만들기 이코테 p.201 문제 고칠점 list 안에서 최대값 찾을 때 max(array) 로 찾자. 자꾸 sorting 하고 원소로 끄집어내지 말고 import sys def cutDduck(cuttingHeight): sum = 0 for i in data: if i > cuttingHeight: i -= cuttingHeight sum += i return sum def binary_search(start, end, target): global answer if start >= end: return mid = (start + end) // 2 sumDduck = cutDduck(mid) if sumDduck == target: answer = mid return elif sumDduck > target: b.. 더보기 이전 1 2 3 4 다음
