Home

접근 처음에 백트래킹으로 풀었으나 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..

접근 스도쿠에 문제 풀이 방식을 알고 있으면 가볍게 풀 수 있을 것으로 보임 문제 접근 방식은 매우 다양함. 논리를 세우고 방법이 나오지 않는다면 처음부터 다시 다른 방향으로 빠르게 바꾸는 것 또한 지혜인 듯 함 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): ..

접근 항상 리스트 자료형을 활용할 때에는 조심해야 한다. 대중적인 접근법을 사용해서 문제 풀이, 가능 여부와 관계없이 선행 탐색 후 올바르지 않는 경우를 조건문을 통해 거르는 로직 진행 백트래킹 함수 구현 시 boolean 형을 리턴하는 방식을 추천, 괜찮은 테크닉을 구현할 수 있다. 문제 https://leetcode.com/problems/word-search/description/ 솔루션 class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROW_length = len(board) COL_length = len(board[0]) WORD_length = len(word) def backtrack(ROW, COL, i..

접근 오히려 easy난이도보다 쉬운 문제인 것 같다 제공되는 자료형이 숫자가 아니라 문자임을 감안하지 않아 조금 고민 일반적인 방법의 코드도 숙지하는 것이 중요해 보임 문제 https://leetcode.com/problems/number-of-islands/description/ 솔루션 class Solution: def numIslands(self, grid: List[List[str]]) -> int: answer = 0 ROW_length = len(grid) COL_length = len(grid[0]) visited = [[False for _ in range(COL_length)] for _ in range(ROW_length)] def dfs(ROW, COL): # update this p..

접근 각 사이드를 확인하여 perimeter를 추가해야 하는 지 그렇지 않은 지를 논리적으로 확실하게 구분하는 것이 핵심 문제 조건 중 섬의 갯수는 무조건 하나이므로 DFS나 DFS를 사용하여 탐색 성능을 높이는 것이 중요해 보임 논리적 흐름이 잘못되었으면 동일한 코드를 수정하기 보다 논리적 흐름을 재설정하여 코드를 새롭게 짜는 것이 좋은 습관인 것 같음.. 문제 링크 https://leetcode.com/problems/island-perimeter/description/ 솔루션 class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: perimeter = 0 ROW_length = len(grid) COL_length = len..

접근 문제 자체는 기타 평이한 백트래킹 문제와 다를 바 없었지만 파이썬 리스트에 대한 개념 이해 부족으로 시간을 많이 씀 재귀 함수 내에서 리스트는 참조가 아닌 복사본을 활용하는 것을 권장 시간 버리는 문제라고 생각했는데 오히려 파이썬 리스트 좀더 깊게 알게 되는 계기가 되었음...😅 솔루션 class Solution: def permute(self, nums: List[int]) -> List[List[int]]: answer = [] nums_length = len(nums) if nums_length == 1: answer.append(nums) return answer def backtrack(answer_list): if len(answer_list) == nums_length: answer.a..

접근 난이도가 있는 문제는 아니지만 특수한 상황에 탐색 기법을 사용하여 솔루션을 작성할 수 있느냐를 묻는 문제 예제가 부실함. 3가지 이상의 예제도 좀 넣어주지... 솔루션 class Solution: def letterCombinations(self, digits: str) -> List[str]: answer = [] digits_length = len(digits) if digits_length == 0: return answer # create mapped list # this result dial list to be # ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] dial = ["", ""] index = 97 for i..

접근 기본적인 백트래킹 문제, 문제 조건이 크게 까다롭지 않아 브루트 포스로 풀 수도 있지만 백트래킹 방법이 출제 의도인 것 같음 문제의 해답이 될 수 있는 경우에 대한 경우를 일반화해야 함. 여기서 막혔음 자연스럽게 중간에 오답이 되는 케이스는 흘려 보내는 논리 흐름이 백트래킹의 핵심 스택이 아닌 변수를 활용하여 괜찮은 솔루션을 작성할 수 있음 솔루션 class Solution: def generateParenthesis(self, n: int) -> List[str]: answer = [] def backtracking(answer_str, left, right): # if it reach to the end, add answer if len(answer_str) == n*2: answer.appen..

접근 두 커서(Two pointer) 개념을 링크드 리스트 문제에 적용시켜 푸는 문제 먼저 간 커서를 n 번 순회시켰을 때, None 인 경우와 그렇지 않은 경우를 모두 생각하여 솔루션을 작성해야 함 가능한 케이스를 모두 면밀히 고민해 볼 필요가 있음 솔루션 class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: cur_left, cur_right = head, head answer = cur_left for i in range(n): cur_right = cur_right.next if cur_right is None: return cur_left.next while cur_rig..

접근 두 노드를 순회하며 계산 친절하게도 이미 거꾸로 뒤업어 놓았음 carry 를 활용해서 모든 경우의 수에 부합하는 보편적인 문제 해결 방식을 찾아야 솔루션 class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: answer = ListNode(0, None) answer_cursor = answer carry = 0 while l1 != None or l2 != None or carry != 0: l1Value = 0 l2Value = 0 if l1: l1Value = l1.val if l2: l2Value = l2.val sumOfValue = l1Value..