hyunkookim 님의 블로그

47. Permutations II "중복 숫자가 포함된 리스트에서 모든 유일한 순열을 반환하라"는 문제입니다.✅ 핵심 포인트 요약nums에 중복 원소가 존재할 수 있음따라서 단순한 백트래킹으로 모든 순열을 생성하면 중복된 결과가 포함됨→ 정렬 + 백트래킹 중 중복 조건 체크로 중복 제거 필요✅ 최적 풀이 (정렬 + used[] + 가지치기)from typing import Listclass Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: # 결과를 저장할 리스트 res = [] # 중복 숫자를 인접하게 만들어 중복 제거가 쉽게 되도록 정렬 nums.sort() ..

51. N-Queens https://youtu.be/Ph95IHmRp5M?si=nFzhZlWopNf9D4FI class Solution: def solveNQueens(self, n: int) -> List[List[str]]: """ - negDiag: ↖ ↘ 대각선 방향을 추적 (row - col = 일정한 값) - posDiag: ↗ ↙ 대각선 방향을 추적 (row + col = 일정한 값) - col: 퀸이 이미 배치된 열(column)을 추적 - 매 줄마다 퀸 하나씩 배치 가능 (한 행에 하나의 퀸만 존재) """ # 퀸이 배치된 열(colum..

131. Palindrome Partitioning https://youtu.be/3jvWodd7ht0?si=paC9K4J8hqA0IgZJ class Solution: def partition(self, s: str) -> List[List[str]]: # palindrome: 앞으로 읽으나 뒤로 읽으나 같은 문자열을 의미 res = [] # 모든 가능한 회문 분할 결과를 저장할 리스트 # 주어진 문자열이 palindrome인지 확인하는 함수 def isPalidrome(substring): # 문자열을 뒤집어서 비교하여 palindrome 여부 반환 return substring == substring[::..

78. Subsets https://youtu.be/REOH22Xwdkk?si=J1EDs8ppnu7DJndK class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: # subset 만들기 res = [] subset = [] def dfs(idx): if idx >= len(nums): print(idx, subset) res.append(subset.copy()) return # decision to include nums[idx] sub..

79. Word Search class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROWS, COLS = len(board), len(board[0]) visit = set() def backtrack(r, c, index): # 단어의 모든 문자를 찾았을 경우 True 반환 if index == len(word): return True # 현재 위치가 유효하지 않거나, # 이미 방문했거나, # 문자가 일치하지 않을 경우 False 반환 ..

39. Combination Sum from typing import Listclass Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtrack(start, comb, total): # Base case: 합이 target과 같으면 결과에 추가 if total == target: res.append(comb.copy()) return # 합이 target을 초과하면 더 이상 탐색하지 않음 if tot..

46. Permutations 이 문제는 주어진 배열의 모든 순열(permutations)을 생성하는 문제입니다. 순열은 순서가 중요한 조합으로, 배열의 각 요소를 모든 가능한 순서로 나열해야 합니다.풀이 접근백트래킹 사용:순열을 생성하기 위해 각 요소를 선택하고, 선택된 요소는 사용하지 못하도록 추적합니다.모든 요소가 사용되면 현재 조합을 결과에 추가합니다.탐색이 끝나면 선택을 취소(백트래킹)하고 다음 탐색을 진행합니다.중복된 숫자가 없으므로 단순한 추적만 필요:중복 제거를 위해 추가적인 set이나 중복 확인이 필요하지 않습니다.재귀적으로 순열 생성:재귀를 통해 가능한 모든 순서를 탐색하며 결과를 생성합니다.  https://youtu.be/s7AvT7cGdSo?si=tUsr_udpq0Mpu_vA cl..

77. Combinations https://youtu.be/q0s6m7AiM7o?si=im6vNN9SG6FK35Vs 풀이 과정문제 이해:n: 1부터 n까지의 숫자.k: 조합에 포함할 숫자의 개수.조합은 순서가 중요하지 않음.백트래킹 전략:숫자 1부터 n까지 반복하며 k개의 숫자를 선택.선택된 숫자는 조합에 추가.조합이 k개의 숫자를 만족하면 결과에 추가.선택한 숫자를 다시 되돌려가며 새로운 조합을 탐색.최적화:현재 숫자 iii를 선택한 뒤에는 i+1부터 탐색.중복된 조합 생성을 방지.class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res = [] # 결과를 저장할 리스트 # 백트래킹 함수 정의 ..

112. Path Sum # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: # DFS로.. def dfs(node, curSum): if not node: return False ..

17. Letter Combinations of a Phone Number GPT: 백트레킹class Solution: def letterCombinations(self, digits: str) -> List[str]: # 1. 숫자와 문자 매핑 정의 phone_map = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } # 2. 결과 리스트 초기화 res = [] # 3. 입력이 빈 문자열인 경우 빈 리스트 반환 i..