hyunkookim 님의 블로그

**카데인 알고리즘(Kadane's Algorithm)**은 이런 상황에서 사용돼요:✅ 언제 사용하는가?**"연속된 부분 배열(subarray) 중에서 가장 큰 합을 구하는 문제"**가 나오면 무조건 카데인 알고리즘을 생각하세요.✅ 예시 문제 유형:정수 배열이 주어졌을 때, 부분 배열의 최대 합을 구하라.예: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 답: 6 ([4, -1, 2, 1])일부 변형으로는 다음도 포함돼요:연속된 일 수 동안의 최대 이익연속된 구간에서 최대 에너지, 기쁨, 포인트 등등…부호가 섞인 값에서 연속 부분 최대화 문제✅ 왜 좋은가?시간 복잡도 O(n) → 매우 빠름공간 복잡도 **O(1)**도 가능 → 메모리 효율적✅ 쓰지 말아야 할 때?"부분 수열(subseque..

✅ BFS (Breadth-First Search, 너비 우선 탐색)📌 정의BFS는 루트(또는 시작 노드)에서 가까운 노드부터 차례대로 방문하는 탐색 방식이에요.DFS는 한쪽 끝까지 파고들었다가(backtrack) 올라오는 방식이었다면,BFS는 먼저 “수평적으로” 넓게 퍼지면서 탐색해요.🧠 어떻게 동작하냐면?큐(Queue) 를 사용해요. → 선입선출 구조루트 노드를 큐에 넣고 시작큐에서 하나 꺼내서 처리하고, 그 노드의 자식들(또는 연결 노드들) 을 큐에 추가큐가 빌 때까지 반복📊 예시 (이진 트리 기준) 1 / \ 2 3 / \ \ 4 5 6BFS 순서: 1 → 2 → 3 → 4 → 5 → 6                  → 위에서부터, 왼쪽에서 오른쪽으로 한 층..

height 는 자식이 없는 노드가 1이고Depth 는 부모 root 노드가 1로 시작 DFS 검색 방법: 깊이 우선 탐색 (Depth-First Search, DFS)깊이 우선 탐색(DFS)은 코딩 인터뷰에서 가장 자주 등장하는 알고리즘 중 하나입니다. 주로 트리나 그래프를 탐색할 때 사용됩니다. 이 강의에서는 트리 탐색에 초점을 맞춰 설명하겠습니다. 트리 전체를 탐색하려면 모든 노드를 방문해야 합니다. 이때 사용할 수 있는 방법 중 하나가 깊이 우선 탐색입니다.기본 아이디어는 어떤 방향(예: 왼쪽) 을 먼저 선택해서, 해당 방향으로 갈 수 있을 때까지 계속 내려가는 것입니다. 즉, 왼쪽 자식 노드를 따라 계속 내려가다가 더 이상 노드가 없으면(null에 도달하면), 부모 노드로 되돌아가서 이번엔 오른..

DP: 0 / 1 Knapsack 0/1 Knapsack 문제 아이디어주어진 배낭(가방)은 고정된 용량을 가지고 있으며, 여러 개의 아이템이 주어진다.각 아이템은 **무게(weight)**와 **이익(profit)**을 가지고 있다.우리는 총 이익을 최대화하면서도, 배낭의 용량을 초과하지 않도록 해야 한다. 이 알고리즘이 0/1 Knapsack이라 불리는 이유는각 아이템을 선택하거나(1) 선택하지 않거나(0) 하는 이진 선택(binary decision) 구조이기 때문이다.문제 정의N개의 아이템이 주어진다.배낭의 최대 수용량이 주어진다.profit[i]: i번째 아이템의 이익weight[i]: i번째 아이템의 무게각 아이템은 한 번만 추가 가능하며, 부분적으로 추가할 수 없음.배낭에 넣을 수 있는 아이템..

Sorting: Bucket Sort  https://youtu.be/mMELgqz7Wnk https://youtu.be/gFesW458zsU def bucketSort(arr): # Assuming arr only contains 0, 1 or 2 counts = [0, 0, 0] # Count the quantity of each val in arr for n in arr: counts[n] += 1 # Fill each bucket in the original array i = 0 for n in range(len(counts)): for j in range(counts[n]): arr[i] = n ..

AND 연산: & OR 연산: |XOR 연산: ^NOT 연산: ~Shift 연산>> : right shift: / 2 나누기 연산(버림)

m x n 의 2D 행렬(matrix) 문제에서  - Brute Force 알고리즘 (DFS 사용) => Time: O(2^(n+m)), Space: O(n+m) dfs, 재귀 사용# Brute Force - Time: O(2 ^ (n + m)), Space: O(n + m)def bruteForce(r, c, rows, cols): if r == rows or c == cols: return 0 if r == rows - 1 and c == cols - 1: return 1 return (bruteForce(r + 1, c, rows, cols) + bruteForce(r, c + 1, rows, cols))print(bruteFo..

위상 정렬(Topological Sort)란?위상 정렬은**유향 비순환 그래프(DAG, Directed Acyclic Graph)**에서 노드들을 선행 관계에 따라 순서대로 정렬하는 알고리즘입니다.특징선행 관계를 보장:노드 A에서 B로 가는 간선이 있다면, 정렬 결과에서 A는 항상 B보다 먼저 나옵니다.**DAG(Directed Acyclic Graph)**에서만 수행 가능:싸이클이 있는 그래프에서는 위상 정렬이 불가능합니다.예제입력 그래프:간선: [[1, 0], [2, 0], [3, 1], [3, 2]]설명: 0은 1과 2의 선행 조건이고, 1과 2는 3의 선행 조건입니다.위상 정렬 결과:가능한 정렬: [0, 1, 2, 3] 또는 [0, 2, 1, 3]위상 정렬 알고리즘Kahn's Algorithm:진..

힙, 우선순위큐 는 완전 이진 트리 임그래서왼쪽 자식 index: 2*i오른쪽 자식 index: 2*i +1부모 index = i/2 단 행렬에서, index 는 1부터.. leftChild of i = heap[2 * i]rightChild of i = heap[(2 * i) + 1] parent of i = heap[i // 2]# leftChild of i = heap[2 * i]# rightChild of i = heap[(2 * i) + 1] # parent of i = heap[i // 2] 힙(Heap)의 종류힙에는 크게 두 가지 유형이 있습니다:최소 힙 (Min Heap):루트 노드에 가장 작은 값이 위치합니다.가장 작은 값이 우선순위가 가장 높으며, 가장 먼저 제거됩니다.최대 힙 (Max..

B-트리(B-Tree)와 B+트리는 데이터베이스와 파일 시스템에서 효율적인 데이터 저장과 검색을 위해 사용되는 균형 트리 구조입니다. 그러나 LeetCode에서는 이러한 특정 트리 구조를 직접적으로 다루는 문제가 많지 않습니다. 대신, 이와 관련된 개념을 다룰 수 있는 이진 탐색 트리(BST), 균형 트리, 세그먼트 트리, 또는 **우선순위 큐(힙)**를 사용하는 문제들이 유사하게 학습할 수 있는 좋은 대안이 됩니다. B-트리와 B+트리의 특징은 주로 다음과 같습니다:B-트리: 균형 잡힌 다진 검색 트리로, 디스크 읽기 및 쓰기를 최적화합니다.B+트리: B-트리의 변형으로, 리프 노드가 연결 리스트 형태로 연결되어 순차 탐색에 효율적입니다. 추천 대체 문제들이진 탐색 트리(BST) 관련 문제:Conver..