[DAY-6] JS 주요 문법(6)

😉 헷갈렸던 & 몰랐던 부분들만 정리하는 나만의 TIL
😯 모든 강의 내용은 적지 않아요!

오늘의 소감은?
파이썬으로 코테 준비를 했었어서, JS로 풀자니 너무 시간이 많이 걸리네요.
지금이라도 JS로 연습해야 하나.. 고민 중입니다.
어떻게 해야해..😯

그리디는 직관적인 문제를 풀 수 있어서 좋지만,
직관적인 해결 방법이 생각나지 않으면 절대 못 풀 것 같네요.
많이 풀어보는 것이 실력이 향상되는 가장 좋은 방법이겠죠?

[1] BFS & DFS

[1-1] BFS (너비 우선 탐색)

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘입니다.

특징

• Queue를 사용해서 구현할 수 있습니다.
• 시작 지점에서 가까운 정점부터 탐색합니다.
• V가 정점의 수, E가 간선의 수 일때, BFS의 시간복잡도는 O(V+E)입니다.

[1-2] DFS (깊이 우선 탐색)

그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘입니다.

특징

• Stack을 사용해서 구현할 수 있습니다.
• 시작 정점에서 깊은 것 부터 찾습니다.
• V가 정점의 수, E가 간선의 수 일때, DFS의 시간복잡도는 O(V+E)입니다.

[+] 실습 코드 - 여행 경로

DFS로 풀어주었습니다.

• 제출 코드

function solution(tickets) {
  let answer = ["ICN"];
  let visit = new Array(tickets.length).fill(0);

  tickets.sort();

  function dfs(str, index) {
    if (index === tickets.length) {
      return true;
    }

    for (let i = 0; i < tickets.length; i += 1) {
      if (visit[i] == 0 && tickets[i][0] == str) {
        visit[i] = 1;
        answer.push(tickets[i][1]);
        if (dfs(tickets[i][1], index + 1)) {
          return true;
        }
        visit[i] = 0;
        answer.pop();
      }
    }

    return false;
  }

  dfs("ICN", 0);

  return answer;
}

[2] 그리디(Greedy)

매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘입니다.

따라서 최적 해를 보장해주지는 않습니다.

[2-1] 그리디 특징

• 최적 해를 구하는 알고리즘보다 빠른 경우가 많습니다.
  보통 선형 시간을 가집니다. (O(n))
• 크루스칼, 다익스트라 알고리즘 등에 사용됩니다.
• 직관적인 문제 풀이에 적합합니다.

[+] 실습 코드 - 큰 수 만들기

😀 전형적인 그리디 문제입니다.
코딩테스트를 준비하면서 그리디를 많이 안풀어봤었는데, 이제라도 열심히 풀어봐야겠어요.

마지막에 k가 남는 경우를 생각하지 못해서
하………splice 구역 생각하느라 시간이 너무 오래 걸렸습니다.

• 제출 코드

function solution(number, k) {
  numArr = [];

  for (let i = 0; i < number.length; i += 1) {
    const num = number[i];

    while (k > 0) {
      if (numArr[numArr.length - 1] < num) {
        numArr.pop();
        k -= 1;
      } else break;
    }

    numArr.push(num);
  }

  numArr.splice(numArr.length - k, k);
  answer = numArr.join("");

  return answer;
}

---

출처

프로그래머스