hyunkookim 님의 블로그

1. BFS 큐 기반 위상 정렬 (Topological Sort using BFS - Kahn's Algorithm)Problem 1: Course Schedule III (LeetCode 630)설명: 주어진 수업들을 듣기 위한 최소 시간으로 완료할 수 있는 최대 수업 수를 구하는 문제입니다. BFS 기반의 위상 정렬을 사용하여 해결할 수 있습니다.핵심 개념: 위상 정렬, 큐, 진입 차수 (in-degree), 최적화Problem 2: Reconstruct Itinerary (LeetCode 332)설명: 공항 여행 계획을 재구성하는 문제입니다. 각 공항에서의 출발지와 도착지가 주어지며, 위상 정렬을 사용하여 경로를 찾습니다.핵심 개념: 그래프, 위상 정렬, 큐, 경로 탐색Problem 3: Task ..

1. BFS 큐 기반 위상 정렬 (Topological Sort using BFS - Kahn's Algorithm)Problem 1: Course Schedule (LeetCode 207)설명: 수업들 간의 선후 관계를 바탕으로 모든 수업을 듣기 위한 가능한 순서를 찾는 문제입니다. 위상 정렬을 사용하여 해결할 수 있습니다.핵심 개념: 큐, 진입 차수 (in-degree), 위상 정렬Problem 2: Course Schedule II (LeetCode 210)설명: Course Schedule 문제와 비슷하지만, 가능한 수업 순서를 반환하는 문제입니다. BFS를 사용하여 위상 정렬을 수행하여 순서를 구합니다.핵심 개념: 큐, 진입 차수, 위상 정렬, 수업 순서Problem 3: Alien Dictio..

Ubuntu에서 Google Drive 공유 파일 다운로드 방법 정리1. 환경 설정OS: Ubuntu파일 다운로드 도구: rclone다운로드 대상 파일파일명: pc_voxelsize_01.tar공유 링크: https://drive.google.com/file/d/1o5hC1SVxrItMEWwKEy4FYgVJGXpE72D4/view?usp=drive_link파일 크기: 약 95GB2. rclone 설치최신 버전 설치기존 rclone 제거 (이미 설치된 경우):sudo apt remove rclone -y최신 rclone 설치:curl https://rclone.org/install.sh | sudo bash설치 확인:rclone --version3. Google Drive와 rclone 연결Google D..

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

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

완벽한 해싱n개가 n개의 버킷에 하나씩 따로따로 저장된다면 완벽한(perfect) 해싱이라고 볼 수 있습니다. 입력 데이터가 뭔지를 모두 알고 있을 경우에만 가능합니다. 예를 들어서 입력 키가 "Apple", "Orange", "Kiwi" 3가지라고 고정이 되어있다면 각각 0, 1, 2에 대응시키면 메모리 낭비 없이 O(1)으로 처리할 수 있습니다.대부분의 경우에는 입력이 정확히 어떤 것들이 들어올지 미리 알 수가 없기 때문에 충돌이 최소가 되는 좋은 해시 함수를 사용할 필요가 있습니다. 유니버설 해싱유니버설 해싱이라는 이름 보다는 "랜덤 해싱"이라는 이름이 더 이해하기 쉬울 것 같습니다. 난수를 사용하는 무작위 알고리듬이 성능을 높이는 데에 도움이 된다는 것은 앞에서 퀵 정렬에서 본 적이 있습니다. 여..