Algorithm 🧩

n개의 입력 데이터에 대하여 알고리즘이 문제를 해결하는 데에 얼만큼의 시간이 걸리는지를 나타내는 것으로 점근적 표기법(asymptotic notation)을 사용 점근적 표기법(asymptotic notation) : 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로, 부분 문제 반복과 최적 부분 구조를 가지고 있는 문제를 푸는데 효율적이다. (큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용)

그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻으로 Greedy 알고리즘은 말 그 대로 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는

그래프 탐색이란 하나의 정점에서 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말하며, 크게 DFS 와 BFS 두가지 방식이 있다.

가중치 그래프(Weighted Graph)에서 한 정점에서 다른 정점으로 갈때, 가중치 합이 최소가 되도록 하는 경로를 찾는 알고리즘

Disjoint set (서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘으로, 두 node가 같은 집합에 속하는지 판별할 때 유용하게 사용할 수 있다!

순서가 있는 작업을 차례대로 수행할 때 순서를 결정해주기 위한 알고리즘으로, DAG(Directed Acyclic Graph)에만 적용 가능

LCA란 최소공통조상(Lowest Common Ancestor)을 찾는 알고리즘이다. 위 그림에서 2와 7의 최소공통조상은 1이다. LCA는 2와 7이 주어졌을 때 1을 찾는 알고리즘이라고 보면 된다!

Backtracking(되추적)은 tree의 변형된 DFS라고 할 수 있다. 각 마디가 유망한지(promising) 검사하고, 만약 유망하지 않으면 그 node의 부모 node로 되추적을 하는 것을 제외하고는 DFS와 같다. 즉, 백트래킹은 유망여부를 판단하여 가지치기

배낭의 용량과 각 물건의 {무게, 가치}가 주어졌을 때 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제

배열에서 원하는 값을 O(log N) 만에 찾는 방법인 Binary Search에 대해 알아보자. Binary Search는 up/down 게임과 유사한 방식으로 배열에서 원하는 값의 위치를 찾을 수 있는 방법이다. Binary Search를 사용할 때 주의해야할 점이