본문 바로가기

전체 글

 (107)
Prim’s Algorithm Prim’s Algorithm is another approach to find the minimum spanning tree (MST) from a given graph.Its code implementation is simpler and easier than Kruscal’s Algorithm based on union-find.Key IdeaGrow the MST greedily: Pick the smallest edge that connects a visited node to an unvisited node.Priority queue (min-heap): Use min-heap to efficiently pick the smallest edge.Repeat until all nodes are in..
백준 11047: 동전 0 아이디어그리디가 최적해 보장큰 단위의 동전은 항상 작은 단위의 동전으로 표현할 수 있으므로 그리디 알고리즘이 최적해 보장!큰 단위의 동전부터 for 루프coins.reverse()로 큰 단위 부터 루프나눗셈동전으로 금액을 나누어 얻은 몪만큼 동전 개수 카운트 증가.동전으로 금액을 나누어 얻은 나머지가 새로운 금액이 됨.탈출새로운 금액이 0이 될 때 이미 답은 나왔지만 for 루프를 계속 돌게 됨.탈출 조건을 주고 최적화 가능 (둘다 O(n)이므로 성능 차이는 미미하다).시간 복잡도coins를 정렬하는데 O(n) (처음부터 내림차순 정렬이 아니라 오름차순을 단순 재배열하므로)for 루프에서 O(n).k와는 관계 없음.최종적으로 O(n)이고 최악의 경우 10이므로 충분히 가능.코드 구현import sysin..
백준 14503: 로봇 청소기 아이디어2차원 리스트로 청소 공간 표현: space[row][col]0: 청소 안된 빈 칸, 1: 벽. 추가로 2: 청소 된 칸 체크용도방향 벡터로 이동을 표현drow = [-1, 0, 1, 0], dcol = [0, 1, 0 -1]북, 동, 남, 서 순으로 정함. 이렇게 하면 drow[d] = 전진, -drow[d] = 후진으로 표현 가능!나머지 연산으로 회전을 표현90도 시계 방향 회전: 0 → 1 → 2 → 3 → 1 → 2 → …90도 반시계 방향 회전: 0 → 3 → 2 → 1 → 0 → 3 → …-1 mod 4 = 3이므로 d = (d - 1) % 4로 구현 가능!while 문으로 반복: 작동 멈출 때까지 계속 반복한다.for문으로 4방향 탐색, 0을 찾았으면 for 문 탈출찾았으면 for문 ..
Kruskal’s Algorithm GoalOur goal is to find the minimum spanning tree (MST) from the graph, which satisfies:All the nodes are connected.The sum of weights is minimized.IdeaThe key ideas for the Kruskal’s algorithm are:Greedy approach: we always process the edge with smallest weight first.Sort the edges in ascending order before processing.Exclude redundant edges: if adding the edge forms a cycle, skip it.Use union-..
Review: CC:DAE https://arxiv.org/abs/2402.08919Core IdeaConceptual similarity between images can be quantified by the complexity of the natural language descriptions required to distinguish the images.DescriptionConceptual SimilarityShorter descriptions that apply well to both imagesHighLonger descriptions that only fit one image well and not the otherLowOptimization ProblemOriginal Optimization ProblemThe opt..
Logistic Regression The goal of Logistic RegressionSuppose we have data with $m$ samples and $n$ features. The data can be represented as an $m\times n$ matrix $X$:where:$x_j^{(i)}$ is a scalar, representing the value of the $j$-th feature for the $i$-th sample (entry view).$x^{(i)T}$ is a row vector, representing the values of all features for the $i$-th sample (row view).$x_j$ is a column vector, representing the..
Topological Sorting The figure on the left is a directed acyclic graph (DAG) representation for the following table, which contains information of dependencies between cources.No.Course NamePrerequisitesNumber of Prerequisites1Calculus-02Linear Algebra-03Probability TheoryCalculus14Information TheoryProbability Theory15Vector CalculusCalculus, Linear Algebra26Mathematical StatisticsProbability Theory, Information T..
Breadth-Frist Search (BFS) vs Depth-First Search (DFS) When exploring all nodes in a graph, we have two fundamental traversal methods:Breadth-First Search (BFS)Depth-First Search (DFS)Breadth-Frist Search (BFS)Key IdeaBFS explores nodes level by level, meaning it visits all neighbors of a node before moving deeper. This ensures that nodes are processed in increasing order of distance from the starting node.Steps:Start from a given node.Visit all its..

티스토리툴바