본문 바로가기

컴퓨터공학 & 정보통신84

[알고리즘] 백트래킹(backtracking) 문제 정복 커리큘럼 서론 백트래킹(Backtracking)은 주로 BFS 및 DFS와 같은 모든 경우의 수를 탐색하는 완전 탐색 대신 중간에 더 이상 조건을 충족하지 못하는 경우 이하 탐색을 종료하고 조건을 충족하는 다른 경우를 탐색하는 기법입니다. 완전 탐색에 비해 성능이 좋은 장점이 있습니다. 솔루션 예 백트래킹 문제는 다음과 같은 형식으로 솔루션을 작성하면 쉽게 풀 수 있습니다. 조건을 만족하지 않는 경우를 모두 체크하는 것이 아닌 조건을 모두 만족하는 경우만 체크 조건을 만족하는 경우들을 이하 반복문을 통해 재귀 탐색 def backtracking(tmp_answer): # 조건을 모두 만족하는 경우를 조건문으로 처리합니다. if answer == tmp_answer: return True for i in (추가 탐.. 2023. 4. 3.
[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.
[LeetCode] 79. Word Search 접근 항상 리스트 자료형을 활용할 때에는 조심해야 한다. 대중적인 접근법을 사용해서 문제 풀이, 가능 여부와 관계없이 선행 탐색 후 올바르지 않는 경우를 조건문을 통해 거르는 로직 진행 백트래킹 함수 구현 시 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.. 2023. 3. 26.

티스토리툴바