0702_TIL

---

🎄오늘 한 일

✔️ 1.  이코테 책 DFS/BFS 학습

✔️ 2. 알고리즘 스터디 카카오기출 5문제 풀이
   

 

이코테

DFS &BFS

• DFS 는 스택과 재귀함수를 통해 구현
• BFS 는 큐를 이용하여 구현

DFS

깊이우선탐색으로, 가장 깊은 부분까지 우선 탐색하는 알고리즘

동작과정
1. 현재노드를 스택에 삽입하고 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 해당 노드를 스택에 넣고 방문처리 방문하지않은 인접노드가 없다면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정 반복

기본코드

 

let visited = Array(graph.length).fill(false);

  function dfs(node) {
    visited[node] = true;
    console.log(node)

    for (let i = 0; i < graph[node].length; i++) {
      if (!visited[graph][node][i]) {
        dfs(graph[node][i]);
      }
    }
  }

  dfs(start);​

 

BFS

'너비우선탐색', 가까운노드부터 탐색하는 알고리즘

동작과정
1. 탐색시작 노드를 큐에 삽입 후 방문처리
2. 큐에서 노드를 꺼내고, 인접노드 중 방문하지 않은 모든 노드를 큐에 삽입 && 방문처리
3. 2번의 과정 반복

기본코드

function solution(graph, start) {
  let result = [];
  let visited = Array(graph.length).fill(false);

  function bfs(node) {
    let Q = [node];
    visited[node] = true;

    while (Q.length > 0) {
      let popNode = Q.shift();
      result.push(popNode);

      for (let i = 0; i < graph[popNode].length; i++) {
        let linkedNode = graph[popNode][i];
        if (!visited[linkedNode]) {
          Q.push(linkedNode);
          visited[linkedNode] = true;
        }
      }
    }
  }

  bfs(start);
  return result;​

 

그래프

• 그래프는 노드와 간선으로 관계를 표현하는 자료구조
• 그래프는 인접행렬과 인접리스트로 표현가능
• 인접행렬은 2차원 배열에 노드의 연결된 형태를 기록, 빠른접근속도+ , 메모리비효율
• 인접리스트는 리스트에 해당 노드에 연결된 노드들만을 저장 탐색속도- ,연결많은노드 비효율- , 메모리효율+

스택&큐

• 스택은 후입선출 구조,
• 큐는 선입선출 구조

재귀함수는 반드시 종료조건을 명시해야함재귀함수를 이용한 팩토리얼 구현

재귀함수를 이용한 팩토리얼 구현
function factorial(n){
	if(n === 1) return 1

	return n * factorial(n-1)
}

반복문을 이용한 팩토리얼
let val = 1;
for(let i = 1; i <= n; i++){
	val *= i
}
return val​

 

• 재귀함수 간결한 코드 장점, 속도는 반복문이 더 빠름

주의사항

• 그리디 알고리즘은 거스름돈 문제에서 100, 500 ,1000의 단위가 아닌 200, 400,500 일 경우 큰 수부터의 부분최적해가 전체최적해를 보장하지 못하는 경우 있다. (800원→ 500, 100, 100 // 400, 400 )
• 이러한 경우에는 다이나믹프로그래밍, 그래프 알고리즘으로 풀수 있는 지 생각하는 것 필요

1번 예제.거스름돈

그리디 가장 기본 예제 : 동전 거스름 돈 문제. n원의 거스름든을 최소한의 개수의 동전을 사용해 거슬러주는 문제 : 큰 동전 순서대로, 최대개수를 차례대로 도출하면 되므로 그리디 문제이다.

function solution(n, coinList) {
  let cnt = 0;
  for (let i = 0; i < coinList.length; i++) {
    cnt += Math.floor(n / coinList[i]);
    n %= coinList[i];
  }
  console.log(cnt);
  return cnt;
}

solution(1260, [500, 100, 50, 10]); // 6

// 시간복잡도는 동전의개수K개라고 할 때 O(K)이다.​

 

2번. 큰수의 법칙

반복문을 이용해 푸는 방법(1)과 공통패턴을 파악해 수식으로 푸는 방법(2) 존재

function solution(rules, nums) {
  let sum = 0;
  let [N, M, K] = rules;
  nums.sort((a, b) => b - a);
  let [first, second] = nums;

  while (true) {
    if (M === 0) break;
    for (let i = 0; i < K; i++) {
      sum += first;
      M--;
      if (M === 0) break;
    }
    sum += second;
    M--;
  }

  console.log(sum);
  return sum;
}

// function solution(rules, nums) {
//   let sum = 0;
//   let [N, M, K] = rules;
//   nums.sort((a, b) => b - a);
//   let [first, second] = nums;

//   let secondQty = Math.floor(M / (K + 1));
//   let firstQty = M - secondQty;
//   sum = firstQty * first + secondQty * second;
//   console.log(sum);
// }

solution([5, 8, 3], [2, 4, 5, 4, 6]);​

 

 

3번. 숫자카드게임

문제이해 :행을 선택하고, 그 행에서 가장 작은 숫자를 선택하는 규칙이 있을 때, 뽑을 수 있는 가장 큰 수를 출력하는 문제

접근 : 각 행의 최소값만을 구하고, 그 중 최대값을 출력하도록 한다. : 각 행에서 최소값을 구하는 과정이 그리디라고 할 수 있다. (그리디는 문제해결을 위한 아이디어떠올림)

풀이
1. map을 통해 순회하며, 각 행의 최소값 도출
2. 최소값 중 최대값 출력

function solution(cards) {
  let minCards = cards.map((el) => Math.min(...el));
  console.log(Math.max(...minCards));
  return Math.max(...minCards);
}​

 

4번. 1이 될 때까지

문제이해

: N을 K로 나누는 것과 N에서 1을 빼는 두가지 연산만을 반복하여 1을 만드는 연산의 횟수를 구하는 문제

접근

: N % K 가 가능한 경우와 아닌 경우에 따라 나누어서 연산처리를 해준다.

풀이
1. while문으로 N = 1이 될 때 cnt를 반환
2. 1나누어지는 경우 1) N을 몫으로 바꾸고 2) cnt++
2.2나누어지지 않는 경우 1) N에서 1빼주고 2) cnt++

 

function solution(N, K) {
  let cnt = 0;
  while (true) {
    if (N === 1) break;

    if (N % K === 0) {
      N = parseInt(N / K);
      cnt++;
    } else {
      N -= 1;
    }
  }
  console.log(cnt);
  return cnt;
}​