Algorithm 스터디

Huffman Encoding이란? Greedy algorithm의 대표적인 예시 *Greedy Algorithm: 매 순간 가장 이득이 되는 선택을 하는 알고리즘 문자들의 '빈도수'를 기반으로, 자주 나오는 문자는 짧은 코드, 길게 나오는 문자는 긴 코드를 부

'그래프는 Node와 edge로 구성된 집합이다'Node: 데이터를 표현하는 단위Edge: Node를 연결가중치(Weight): 에지에 부여된 숫자값Tree 또한 그래프의 일종Union-Find: 노드들이 같은 그룹에 속해 있는지 확인할 때 사용, 싸이클 유무 판단위상

1. DFS(깊이 우선 탐색) 2. BFS(너비 우선 탐색) 3. Binary Search(이진 탐색)

최소 신장 트리(Minimum Spanning Tree) > MST, 최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. MST를 구현하는 대표적인 방식 두 가지는 '크루스칼'과 '프림'이 있다. MST는 다음

Brute force algorithm이란?

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘위의 트리구조를 봤을 때, 그리디 알고리즘의 경우는 그 단계단계마다 무조건 제일 큰 쪽, 즉 최선의 선택지를 선택하는 것을 확인할 수 있다. 핵심 이론은 다음과 같다.Sol

'큰 문제'를 '작은 문제'로 나누어서 해결하는 알고리즘조금 더 풀어 말하자면, 하나의 큰 문제를 작은 부분의 문제들로 나누고, 나눈 부분 문제를 해결하고 해결된 해들을 모아 원래의 문제를 해결해 나가는 방식이다. 따라서 크게 '분할 > 정복 > 결합'의 단계를 지닌다

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이 정의만 봤을 때는, 앞서 다뤘던 분할 정복(divide and conquer)와 매우 유사하다고 느낄 수 있다. 두 알고리즘 모두 큰 문제를 작은