hyunkookim 님의 블로그

433. Minimum Genetic Mutation 이 문제는 그래프 탐색 문제로 생각할 수 있습니다.각각의 유효한 유전자 문자열(gene)을 노드로 보고,한 번의 변이로 연결될 수 있는 두 노드를 간선으로 연결하여최단 경로를 찾는 방식으로 해결합니다.문제의 주요 포인트유전자 변이의 정의:두 유전자 문자열에서 단 하나의 문자만 다른 경우, 한 번의 변이라고 간주합니다.예: "AACCGGTT" → "AACCGGTA" (1개의 문자만 변이).유효한 변이 조건:변이 후의 문자열은 반드시 bank에 포함되어 있어야 합니다. 그렇지 않으면 유효하지 않은 변이로 간주합니다.목표:startGene에서 endGene까지 변이를 통해 도달하기 위해 필요한 최소 변이 횟수를 계산합니다.도달할 수 없는 경우 -1을 반환합..

97. Interleaving String https://youtu.be/3Rw3p9LrgvE?si=Bs1PKA3LI4l3H4my class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: # 길이 조건 확인 if len(s1) + len(s2) != len(s3): return False dp = {} def dfs(i, j): # 종료 조건: s1과 s2를 모두 사용했을 때 if i == len(s1) and j == len(s2): return True # 이미 계산..

427. Construct Quad Tree https://youtu.be/UQ-1sBMV0v4?si=5BBkFUGx3Q4HoIeF """# Definition for a QuadTree node.class Node: def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight): self.val = val # 현재 노드의 값 (0 또는 1) self.isLeaf = isLeaf # 현재 노드가 리프 노드인지 여부 self.topLeft = topLeft # 왼쪽 위 서브노드 self.topRight = topRight # 오른쪽 위 서브노드 self.bot..

23. Merge k Sorted Lists https://youtu.be/q5a5OiGbT6Q?si=Oe5XE1QtO56CiD-s # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: # 입력으로 주어진 리스트가 비어 있거나, 리스트의 길이가 0일 경우 None 반환 if not lists or len(..

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 이 문제는 정렬된 정수 배열(nums)이 주어질 때, 이를 사용하여 **높이 균형 이진 탐색 트리(Height-Balanced BST)**를 생성하라는 요청입니다.주요 용어와 개념이진 탐색 트리(Binary Search Tree, BST):각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.BST의 특징:왼쪽 서브트리의 모든 값은 부모 노드보다 작음.오른쪽 서브트리의 모든 값은 부모 노드보다 큼.높이 균형 트리(Height-Balanced):모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리.트리가 균형 잡혀 있어야, 검색 및 삽입 연산이 효율적으로 이루어짐.문제의 요구사항정렬된 배열 num..

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