hyunkookim 님의 블로그

148. Sort List https://youtu.be/TGveA1oFhrc?si=rRYsC927YCXjnEcg # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: # time: n log n => merge sort # memory: O(1) => can Recursion, 재귀 if not head or..

108. Convert Sorted Array to Binary Search Tree # 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: # 오름차순으로 정렬된 리스트로부터 , 이진 바이너리 서치 트리로 바꿔라 BST """ # base c..

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 반환 ..

22. Generate Parentheses https://youtu.be/s9fokUqJ76A?si=ERC4z90YXz3-fkws class Solution: def generateParenthesis(self, n: int) -> List[str]: # stack: 현재까지 생성된 괄호를 저장하는 스택 # res: 유효한 괄호 조합을 저장할 결과 리스트 stack = [] res = [] # 백트래킹 함수 정의 def backtrack(openN, closedN): # openN: 열린 괄호 '('의 개수 # closedN: 닫힌 괄호 ')'의 개수 # 베이스 케..

52. N-Queens II 문제 설명: N-Queens IIN-Queens 문제는 n×n 체스판에서 n개의 퀸을 서로 공격하지 않도록 배치하는 문제입니다.이 문제의 목표는 모든 가능한 배치 방법의 개수를 찾는 것입니다.퀸(Queen)의 공격 조건퀸은 다음의 위치에 있는 다른 퀸을 공격할 수 있습니다:같은 행에 있는 퀸같은 열에 있는 퀸대각선에 있는 퀸 (왼쪽 위 ↖, 오른쪽 위 ↗, 왼쪽 아래 ↙, 오른쪽 아래 ↘)즉, 어떤 퀸도 서로 같은 행, 같은 열, 또는 대각선에 위치할 수 없습니다.문제 예제예제 1: n=4출력: 2설명:4×4 체스판에 퀸을 배치할 수 있는 경우의 수는 2개입니다.예제 2: n=1출력: 1설명:1×1 체스판에서는 퀸을 1개만 배치할 수 있으므로, 가능한 배치 방법은 1개입니다...

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..

797. All Paths From Source to Target 이 문제는 DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서 시작 노드(0)에서 목표 노드(n−1)로 가는 모든 경로를 찾는 것입니다. 이 과정은 DFS(깊이 우선 탐색)를 이용하여 해결할 수 있습니다. 아래는 코드의 주요 흐름에 대한 한글 설명입니다.DFS 함수 정의:dfs 함수는 현재 노드(node)와 현재까지 탐색한 경로(path)를 인자로 받습니다.만약 현재 노드가 목표 노드(n−1)라면, 지금까지의 경로를 결과 리스트(result)에 추가합니다.재귀와 백트래킹:현재 노드의 모든 이웃 노드(neighbor)를 탐색합니다.이웃 노드를 경로에 추가한 뒤, 재귀적으로 dfs를 호출합니다.재귀 호출이 끝난 후에는 ..

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 = [] # 결과를 저장할 리스트 # 백트래킹 함수 정의 ..

212. Word Search II https://leetcode.com/problems/implement-trie-prefix-tree/description/ : 208. Implement Trie (Prefix Tree) https://youtu.be/asbcE9mZz_U?si=7ovXqcPW-mJDtg7h   class TrieNode: def __init__(self): self.children = {} # 자식 노드를 저장하는 딕셔너리 (예: {'a': TrieNode()}) self.isWord = False # 현재 노드가 단어의 끝인지 여부를 나타내는 플래그 def addWord(self, word): cur = self # 현재 노드에..