hyunkookim 님의 블로그

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

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

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

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개입니다...

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

909. Snakes and Ladders https://youtu.be/6lH4nO3JfLk?si=VJAa2R-huRKNzl6O 문제 설명 요약게임 보드 구조:n x n 크기의 정수 행렬 board가 있습니다.board는 Boustrophedon 스타일로 채워져 있습니다:숫자는 아래 왼쪽에서 시작하여 첫 줄은 왼쪽 → 오른쪽으로 채워지고,다음 줄은 오른쪽 → 왼쪽으로 채워지는 식으로 반복됩니다.각 칸은 1부터 n2까지의 숫자로 라벨링됩니다.초기 상태:게임은 1번 칸(왼쪽 아래)에서 시작합니다.이동 규칙:매 턴마다 주사위를 굴려 1에서 6 사이의 값을 얻습니다.현재 칸 curr에서 [curr + 1, min(curr + 6, n^2)] 범위 내의 칸 중 하나로 이동합니다.예: 현재 칸이 10이면, 다음 ..

149. Max Points on a Line https://youtu.be/Bb9lOXUOnFw?si=srijUp6iwLeL2_n5 class Solution: def maxPoints(self, points: List[List[int]]) -> int: # 1. for each pt determin if it lies on the logest line # 2. count all pts with same slop # 3. update result with max res = 1 # 최소 포인트 개수가 1개 이므로, 1개는 게런티 가능해서, for i in range(len(points)): p1 = points[i..

50. Pow(x, n) Time Limit Exceededclass Solution: def myPow(self, x: float, n: int) -> float: res = 1 if n>0: for i in range(1, n+1): res *= x elif n  이진 분할(분할 정복) 기법을 활용하여 효율적으로 해결할 수 있습니다. 이는 반드시 이진 트리를 명시적으로 사용하는 것은 아니지만, 개념적으로 재귀적으로 문제를 반으로 나누는 방식이 이진 트리의 구조와 유사합니다.  def myPow(x: float, n: int) -> float: # 음수 지수 처리 if n  이진 트리와의 ..

69. Sqrt(x) 통과는 하지만, 쫌 오래 걸림class Solution: def mySqrt(self, x: int) -> int: i = 0 while(i>=0): if (i*i == x): return i elif (i*i > x): break i+=1 return i-1 https://youtu.be/zdMhGxRWutQ?si=DRszQKJf3yNpiTyt 바이너리 써치로..class Solution: def mySqrt(self, x: int) -> int: # 바이너리 써치로. 이진 탐색 ..

373. Find K Pairs with Smallest Sums https://youtu.be/Youk8DDnLU8?si=dTtsC6RqlaGW-wWl class Solution: def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]: res = [] if not nums1 or not nums2 or not k: return res heap = [] visited = set() # 1번째 pair 추가: 정렬되어 있으므로, 둘다 첫번째, idx=0 이면, 합이 최소 # 힙에 (sum, i, j) 추가..