Day13

Day13

BFS, DFS

• BFS(Breadth-First Search) : 그래프에서 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
  • Queue를 이용하여 구현할 수 있다.
  • 시작 지점에서 가까운 정점부터 탐색한다.
  • V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)이다.
• DFS(Depth-First Search) : 그래프에서 최대한 깊은 정점부터 탐색하는 알고리즘
  • Stack을 이용하여 구현할 수 있다.
  • 시작 정점에서 깊은 것부터 찾는다.
  • V가 정점의 수, E가 간선의 수일 때 DFS의 시간 복잡도는 O(V+E)이다.
• 문제 : 여행경로
• 정답코드

Greedy

• 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘. 최적해를 보장해주진 않는다.
• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에서 적용된다.
• 직관적인 문제 풀이에 적합하다.

• 동전 반환 문제

• 문제 : 큰 수 만들기
• 정답코드

  function solution(number, k) {
    const stack = [];
    let count = 0;
    for(const item of number) {
        while (count < k && stack[stack.length-1] < item) {
            stack.pop();
            count++;
        }
        stack.push(item);
    }
  
    while(count < k) {
        stack.pop();
        count += 1;
    }
  
    return stack.join('');
  }