Home

서론 백트래킹(Backtracking)은 주로 BFS 및 DFS와 같은 모든 경우의 수를 탐색하는 완전 탐색 대신 중간에 더 이상 조건을 충족하지 못하는 경우 이하 탐색을 종료하고 조건을 충족하는 다른 경우를 탐색하는 기법입니다. 완전 탐색에 비해 성능이 좋은 장점이 있습니다. 솔루션 예 백트래킹 문제는 다음과 같은 형식으로 솔루션을 작성하면 쉽게 풀 수 있습니다. 조건을 만족하지 않는 경우를 모두 체크하는 것이 아닌 조건을 모두 만족하는 경우만 체크 조건을 만족하는 경우들을 이하 반복문을 통해 재귀 탐색 def backtracking(tmp_answer): # 조건을 모두 만족하는 경우를 조건문으로 처리합니다. if answer == tmp_answer: return True for i in (추가 탐..

큰 따옴표(Double Quotes)와 작은 따옴표(Single Quotes) 상황에 따라 추천하는 경우가 다를 뿐 차이가 없다고 보셔도 무방합니다. 문자열에 작은 따옴표가 포함되는 경우, 큰 따옴표로 문자열을 감싸 주어야 합니다. example = "I'm an apple" # 출력 결과 : I'm an apple 반대로 문자열에 큰 따옴표가 포함되는 경우, 작은 따옴표로 문자열을 감싸 주어야 합니다. example = 'Apple said "Hello banana"' # 출력 결과 : Apple said "Hello banana" 문자열에 둘 다 들어가야 하는 경우, 큰 따옴표/작은 따옴표 세개로 문자열을 감싸 주어야 합니다. example = """"Hello Apple?" banana said. ..

접근 오히려 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..

접근 문제 자체는 기타 평이한 백트래킹 문제와 다를 바 없었지만 파이썬 리스트에 대한 개념 이해 부족으로 시간을 많이 씀 재귀 함수 내에서 리스트는 참조가 아닌 복사본을 활용하는 것을 권장 시간 버리는 문제라고 생각했는데 오히려 파이썬 리스트 좀더 깊게 알게 되는 계기가 되었음...😅 솔루션 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..