Home

접근 stack과 array 탐색을 통해 문제를 해결해야 함을 알았으나 코드를 논리적으로 짜지 못하였음. 효율적인 로직을 짜는 것에 대한 훈련이 필요해 보임 문제 링크 Simplify Path - LeetCode 솔루션 class Solution: def simplifyPath(self, path: str) -> str: stack = [] word = "" for char in path + "/": if char == "/": # if .. -> delete lastest stack if word == "..": if stack: stack.pop() # if none of them and not an empty word, add stack elif word != "" and word != ".": s..

접근 완전탐색이 아닌 DP로 풀어야 하는 문제 DP[0]에 도달하여 True를 리턴하면 되기에 Bottom-up 방식으로 문제를 풀 수 있다. DP 리스트 길이를 s의 길이보다 하나 더 길게 설계하여 부드러운 솔루션을 작성해야 함 문제 링크 https://leetcode.com/problems/word-break/description/ 솔루션 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: s_length = len(s) DP = [False for _ in range(s_length+1)] DP[s_length] = True for i in range(s_length-1, -1, -1): for word in wordD..

접근 완전탐색으로 풀 수 있지만 DP로 푸는 것이 맞는 문제 Bottom-Up으로 풀 수 있는 지 확인해 보았지만 목적지에서 부터 출발지로 가는 경우의 수를 특정할 수 없음 따라서 Top-Down 방식으로 솔루션을 작성하여 해결 예제 1의 DP) 문제 링크 https://leetcode.com/problems/unique-paths/description/ 솔루션 class Solution: def uniquePaths(self, m: int, n: int) -> int: if m == 1 or n == 1: return 1 DP = [[1 for _ in range(n)] for _ in range(m)] for M in range(1, m): for N in range(1, n): DP[M][N] = ..

접근 DP의 기초, 위의 두 값이 아래 값을 결정하는 것을 확인하면 된다. 문제 링크 https://leetcode.com/problems/pascals-triangle/description/ 솔루션 class Solution: def generate(self, numRows: int) -> List[List[int]]: answer = [[1]] for i in range(1, numRows): tmp = [] tmp.append(1) for j in range(1, i): num = answer[i-1][j-1] + answer[i-1][j] tmp.append(num) tmp.append(1) answer.append(tmp) return answer

접근 처음 DFS로 풀이 시도 허나 도식화 후 Memoization이 가능함을 보고 DP로 솔루션 작성이 가능함을 판단 DP 방식 중 Top Down 으로 푸는 방법이 도저히 생각이 나지 않아 Bottom-up으로 고민 후 솔루션 작성 DP의 가장 교과서적인 문제 중 하나... 알고리즘 수업 때도 보았던 문제로 기억남 문제 링크 https://leetcode.com/problems/climbing-stairs/description/ 솔루션 class Solution: def climbStairs(self, n: int) -> int: DP = [1 for _ in range(n+1)] # Bottom-up for i in range(n-2, -1, -1): DP[i] = DP[i+1] + DP[i+2] ..

접근 O(N^2) 으로 처음에 시도했다가 TLE에 걸렸음 알파벳의 갯수와 k를 활용하여 이에 적합한 솔루션을 짜는 것이 핵심 문제를 제대로 이해한다면 올바른 솔루션을 짜는 것이 가능하니.. 문제를 정확히 이해할 것... 문제 링크 https://leetcode.com/problems/longest-ideal-subsequence/description/ 시도1(TLE) O(N^2) 으로 모두 비교하는 방법으로 처음 솔루션을 작성했습니다. 하지만 이 시도는 TLE에 걸려 통과하지 못했습니다. class Solution: def longestIdealString(self, s: str, k: int) -> int: s_length = len(s) DP = [1 for _ in range(s_length)] f..

접근 다이나믹 프로그래밍을 활용하여 문제를 풀어야 함 subsequence의 특징 중 앞의 원소에서 가능했던 갯수를 포함할 수 있다는 점을 캐치해야 함 문제 링크 https://leetcode.com/problems/longest-increasing-subsequence/description/ 솔루션 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: nums_length = len(nums) dp = [1 for _ in range(nums_length)] for i in range(nums_length): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) return ..

접근 O(n) 시간복잡도 탐색을 통해 문제에서 요구하는 성능을 만족하는 것이 핵심 two pointers 기법을 사용해야 한다. 문제 링크 https://leetcode.com/problems/container-with-most-water/description/ O(n^2) 시도 TLE: 해당 솔루션은 오답입니다. class Solution: def maxArea(self, height: List[int]) -> int: answer = 0 left = 0 height_length = len(height) while left < height_length-1: for i in range(left+1, height_length): WIDTH, HEIGHT = i-left, min(height[left], h..

접근 기존 점프 게임처럼 그리디를 쓰는 방법도 있겠지만, DFS 와 백트래킹을 통해 문제를 풀 수도 있음. DFS를 활용할 때에는 Runtime error를 조심하도록 합시다. visited 리스트를 활용해 불필요한 재귀를 줄여야 함 문제 링크 https://leetcode.com/problems/jump-game-iii/description/ 솔루션 class Solution: def canReach(self, arr: List[int], start: int) -> bool: arr_length = len(arr) visited = [False for _ in range(arr_length)] def dfs(index): # if out of bound or already visited if index..

접근 그리디로 풀면 되는 문제 기술적인 스킬이 부족해서 안될 코드를 계속 붙잡고 있었다. 머리를 써야 한다. 왜 상황 이해를 제대로 하지 않는 듯 문제 링크 https://leetcode.com/problems/jump-game-ii/description/ 솔루션 class Solution: def jump(self, nums: List[int]) -> int: nums_length = len(nums) left = right = 0 answer = 0 while right < nums_length-1: max_index = 0 # get max index of available range for i in range(left, right+1): max_index = max(max_index, i+nums..