hyunkookim 님의 블로그

1. DP 이론 개요https://youtu.be/5dRGRueKU3M?si=Uo3Ki-LDdKyD9QRc 2. Multi-stage Graphhttps://youtu.be/9iE9Mj4m8jk?si=HOFYjoNjMZuLklpWhttps://youtu.be/FcScLYJI42E?si=z2_05CCqWl_bXZCN 3. All Pairs Shortest Path (Floyd-Warshall) 최단 경로: 두 정점 사이의 최단 거리 찾기 문제https://youtu.be/oNI0rf2P9gE?si=rgh9UYMb4a0tLQY7 3. Bellman Ford Algorithm : 음수 가중치가 있는 그래프에서 최단 경로 찾기, 음수 가중치(negative weight)가 있는 그래프에서도 최단 경로를 구하고 ..

Linear Regression (Forward) 📘 문제 설명: 선형 회귀 (Linear Regression) 모델 구현🎯 목표선형 회귀 모델을 통해 입력 데이터 X에 대해 예측값을 구하고,예측값과 실제 정답 간의 오차(error) 를 계산하는 함수를 구현하는 것입니다.🔢 주어진 입력1. get_model_prediction(X, weights) 함수의 입력:X: 입력 데이터셋.X는 n×3 행렬 형태이며, 각 행은 3개의 특성(피처)을 가집니다. 예:X = [ [x1_1, x1_2, x1_3], # 첫 번째 샘플 [x2_1, x2_2, x2_3], # 두 번째 샘플 ...]weights: 모델의 가중치 벡터, 길이 3인 리스트로 구성됨.예: [w1, w2, w3]2. get_error(m..

Gradient DescentEasyYour task is to minimize the function via Gradient Descent: f(x)=x2f(x)=x2.Gradient Descent is an optimization technique widely used in machine learning for training models. It is crucial for minimizing the cost or loss function and finding the optimal parameters of a model.For the above function the minimizer is clearly x = 0, but you must implement an iterative approximatio..

https://youtu.be/tWVWeAqZ0WU?si=zOJL3C3EY4LII59T 1. Graph 에 대한 DFS (깊이 탐색) 과 BFS (너비 탐색) graph = { 'a': ['c', 'b'], 'b': ['d'], 'c': ['e'], 'd': ['f'], 'e': [], 'f': [],}# Online Python - IDE, Editor, Compiler, Interpretergraph = { 'a': ['c', 'b'], 'b': ['d'], 'c': ['e'], 'd': ['f'], 'e': [], 'f': [],}def depthFirstSearchPrint(graph, source): stack = [sourc..

**순열(permutation)**과 **조합(combination)**은 모두 "선택"과 관련된 개념이지만, 순서를 따지느냐에 따라 완전히 달라져요.✅ 순열 (Permutation)📌 정의:순열은 순서가 중요한 선택즉, 어떤 항목들을 어떤 순서로 배열하느냐가 중요해요.📌 예시:숫자 [1, 2, 3]에서 3개를 뽑아 순열을 만들면:[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]👉 총 6개 (3! = 6)✅ 조합 (Combination)📌 정의:조합은 순서를 따지지 않는 선택즉, 뭐를 뽑았는지가 중요하지, 어떤 순서로 뽑았는지는 중요하지 않아요.📌 예시:숫자 [1, 2, 3]에서 3개를 뽑아 조합을 만들면:[1, 2, 3]👉 [1, 2,..

4가지 LCS (Longest Common Subsequence) 알고리즘 버전 ✅ 1. DFS (Brute Force) — 시간복잡도: O(2^(n + m))# 완전탐색 방식: 모든 경우를 재귀로 탐색# 시간 복잡도: O(2^(n+m)), 공간 복잡도: O(n+m) (재귀 스택)def dfs(s1, s2): return dfsHelper(s1, s2, 0, 0)def dfsHelper(s1, s2, i1, i2): # 기저 조건: 두 문자열 중 하나라도 끝에 도달하면 LCS는 0 if i1 == len(s1) or i2 == len(s2): return 0 # 현재 문자가 같으면 두 포인터를 모두 이동시키고 +1 if s1[i1] == s2[i2]: ..

좋아! Unbounded Knapsack 문제는 아주 자주 나오는 동적 계획법(DP) 문제 중 하나야.0/1 Knapsack과 비슷하지만 아이템을 여러 번 쓸 수 있다는 점이 핵심이야.아래에 직관, 차이점, 예제, 코드까지 정리해서 설명해줄게.🎯 1. 문제 정의: Unbounded Knapsack무게 제한이 있는 가방이 있고,각각의 아이템은 **무게(w[i])**와 **가치(v[i])**를 가지고 있음.각 아이템은 무제한으로 여러 번 선택할 수 있음.제한된 총 무게 안에서 가장 높은 총 가치를 구하라.🎒 2. 차이점: 0/1 vs. Unbounded구분    구분 0/1 Knapsack Unbounded Knapsack 아이템 사용한 번만 사용 가능여러 번 사용 가능 (무한)반복 방식for i in..

0/1 Knaptsack: 가방 넣거나 빼거나. 문제weight[i] 를 참고해서 capacity 용량(== sum(weight[i])을 만족하면서.profit 최대화( profit = [4,4,7,1] 이고 weight = [5,2,3,1], capacity = 8 일때 최대 profit 은?capacity 가 8 로 시작해서i=0, weight[0] = 5 선택O 하거나 => 남는 capacity C = 3 또는      -> i=1 선택 O 하거나 => 남는 C=1          -> i=2 선택 O 하거나 => 남는 C=-2 => 선택 못함              -> i=3 진행X          -> i=2 선택 X 하거나 => 남는 C=1              -> i=3 선택 O 하거나..

Topological Sort (위상 정렬) 은 그래프 이론에서 매우 자주 등장하는 개념입니다.한마디로 정리하면:✅ Topological Sort란?**방향성이 있는 그래프(DAG)**에서모든 노드를 "선후 관계를 지키면서" 나열한 순서즉,어떤 작업을 먼저 해야 다른 작업을 할 수 있는 경우그 작업 순서를 찾는 게 바로 위상 정렬이에요.✅ 조건: DAG 여야 함Directed Acyclic Graph (DAG)란?👉 '방향'이 있고, '사이클이 없는' 그래프🔁 용어부터 찬찬히 살펴보면:단어의미Directed간선(선)에 방향이 있음 → A → B는 B → A와 다름AcyclicCycle(순환) 이 없음 → 다시 자기 자신으로 돌아오는 경로가 없음Graph노드(점)들과 간선(선)으로 구성된 구조📌 To..

edges.sort()✅ 최소 신장 트리 (Minimum Spanning Tree, MST)란?모든 노드가 연결되어 있어야 함사이클이 없어야 함가중치의 합이 최소가 되어야 함노드가 n개일 경우, n-1개의 간선으로 이루어짐🌲 크루스칼 Kruskal's Algorithm이란?"모든 간선을 가중치 순으로 정렬해서, 비용이 가장 작은 것부터 연결해나가는 방식"단, 사이클이 생기지 않도록 연결해야 하므로 Union-Find 자료구조를 이용해 cycle을 검사합니다.🧠 핵심 개념 (설명에 반영할 내용)🔹 1. 간선 수는 n-1개면 충분하다✔️ 맞습니다. 노드가 n개면 MST는 항상 n-1개의 간선을 갖게 됩니다.🔹 2. 어디서 출발할지는 상관 없다 (Prim과 달리)✔️ 정확해요! Kruskal은 간선을 ..