너비 우선 탐색(Breadth First Search)
-
시작 정점에서 가까운 정점(같은 깊이)부터 먼저 탐색하는 알고리즘
-
Queue를 이용해서 구현한다
-
V가 정점의 수, E가 간선의 수일 때, 너비 우선 탐색은 O(V+E)의 시간 복잡도를 가진다.
깊이 우선 탐색(Depth First Search)
-
시작 정점에서 최대한 깊은 정점부터 탐색하는 알고리즘
-
Stack을 이용해서 구현한다
-
너비 우선 탐색과 동일하게 O(V+E)의 시간 복잡도를 가진다.
그리디(Greedy)
-
매 선택의 순간마다 최적을 선택하는 알고리즘
-
그 순간의 최적을 선택하기 때문에, 결과가 최적해가 아닌 경우도 있다.
-
특징상 최적해를 구하는 알고리즘보다 빠른 경우가 많으며, O(N)의 시간 복잡도를 가진다.
-
사람이 이해하기 쉬운 직관적인 문제 풀이에 적합한 알고리즘이다.
실습 문제
문제 출처
문제 풀이
function solution(number, k) {
let answer = '';
let count = 0;
for (let i = 0; i < number.length; i++) {
while (count < k && answer[answer.length-1] < number[i]) {
answer = answer.slice(0, answer.length - 1);
count++;
}
answer += number[i];
}
return answer.slice(0, answer.length - (k - count));
}백트래킹(Backtracking)
-
모든 경우의 수를 탐색하지만, 효율을 위해 해가 되지 않는 경로는 탐색하지 않는 알고리즘
-
해가 되지 않을 것 같은 경로를 방문하지 않는 것을 가지치기(Pruning)라고 한다.
-
BFS 혹은 DFS를 이용해서 구현한다.
-
탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다.
동적 계획법(Dynamic Programming)
-
해결한 작은 문제로 큰 문제를 해결하는 방식
-
메모리를 많이 사용하는 대신, 빠른 성능을 자랑한다.
-
DP를 사용해서 메모리 사용량이 문제가 된다면 백트래킹을 이용해서 해결이 가능하지만, 이런 경우는 거의 없다. -
메모이제이션과 타뷸레이션 두 가지 방법론이 있다.
메모이제이션(Memoization)
-
하향식 접근방법
-
느긋한 계산법(Lazy evaluation)을 사용한다.
-
이전 계산값을 메모리에 저장하고, 필요할 때 저장해둔 값을 꺼내서 사용한다.
타뷸레이션(Tabulation)
-
상향식 접근방법
-
조급한 계산법(Eager evaluation)을 사용한다.
-
작은 값부터 천천히 채워나가며, 필요하지 않을 수 있는 값도 미리 계산하는 특징을 가지고 있다.
느낀 점
죽여....줘....
알고리즘 파트를 끝내면서 느낀 점은, 분명 알고리즘의 특징도 이해했고 문제 해결에 대한 방법도 올바르게 접근했지만, 그걸 코드로 옮겨내는 능력이 부족하다는 점이다.
특히 재귀함수의 흐름에 대한 이해가 부족해서, DFS를 사용해야 하는 문제는 대부분 Stack을 이용해서 구현하려고 하고 있는데, 이 부분이 가장 취약한 것 같다.
분명 단시간에 해결 가능한 문제는 아니라고 생각하기 때문에, 천천히 시간을 들여서 여러유형의 문제를 풀어보는 것이 중요하다고 생각된다.
관련해서 [Programmers Level.3] 여행경로 와 [Programmers Level.3] N-Queen 문제는 꼭 다시 풀어보도록 하자!!!😣
