컴퓨터공학 & 정보통신/알고리즘 문제 풀이41 [LeetCode] 300. Longest Increasing Subsequence 접근 다이나믹 프로그래밍을 활용하여 문제를 풀어야 함 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 .. 2023. 4. 6. [LeetCode] 11. Container With Most Water 접근 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.. 2023. 4. 4. [LeetCode] 1306. Jump Game III 접근 기존 점프 게임처럼 그리디를 쓰는 방법도 있겠지만, 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.. 2023. 4. 3. [LeetCode] 45. Jump Game II 접근 그리디로 풀면 되는 문제 기술적인 스킬이 부족해서 안될 코드를 계속 붙잡고 있었다. 머리를 써야 한다. 왜 상황 이해를 제대로 하지 않는 듯 문제 링크 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.. 2023. 4. 3. [LeetCode] 55. Jump Game 접근 처음에 백트래킹으로 풀었으나 TLE로 인해 승인되지 않았음 찾아본 결과 백트래킹+DP 로 풀거나 그리디 알고리즘을 사용하여 풀어야 함을 알게 되었음 그리디 알고리즘을 통해 문제를 해결 https://www.youtube.com/watch?v=Yan0cv2cLy8 참고하였음 문제 링크 https://leetcode.com/problems/jump-game/ 솔루션 class Solution: def canJump(self, nums: List[int]) -> bool: nums_length = len(nums) point = nums_length-1 for index in range(nums_length-1, -1, -1): # if available to move point from place of.. 2023. 4. 3. [LeetCode] 36. Valid Sudoku 접근 스도쿠에 문제 풀이 방식을 알고 있으면 가볍게 풀 수 있을 것으로 보임 문제 접근 방식은 매우 다양함. 논리를 세우고 방법이 나오지 않는다면 처음부터 다시 다른 방향으로 빠르게 바꾸는 것 또한 지혜인 듯 함 set 함수를 응용하여 코드를 간결화하는 것이 좋음 문제 링크 https://leetcode.com/problems/valid-sudoku/description/ 솔루션 class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: SUBSQ = [[[] for _ in range(3)] for _ in range(3)] # check ROWS for i in range(9): ROW = [] for j in range(9): .. 2023. 3. 31. 이전 1 2 3 4 5 6 7 다음
