프론트엔드 데브코스 TIL #DAY7

23.09.27

📚 오늘 공부한 것

• 실습 - 입국심사
• BFS, DFS
• 실습 - 여행경로
• 그리디
• 실습 - 큰 수 만들기
• 실습 - 네트워크

새롭게 알게된 것

파라메트릭 서치 (Parametric Search)

이분 탐색 알고리즘과 비슷한 결정문제인 파라메트릭 서치!

특정 값을 구한다기 보단, 문제 조건을 만족하는 최소, 최댓값을 구하는 문제이다.

파라메트릭 서치 풀이는 다음을 만족해야한다.

• (최솟값을 구하는 경우) 최솟값이 x라면, x 이상의 값에 대해서는 모두 조건을 만족해야 한다.
• (최댓값을 구하는 경우) 최댓값이 x라면, x 이하의 값에 대해서는 모두 조건을 만족해야 한다

마찬가지로 이분탐색에서도 기본 조건이 값들의 정렬이다!!⭐️

크루스칼, 다익스트라 알고리즘

그리디에서 파생되었다고 한다! 그래프 알고리즘으로만 접했었는데, 왜 그리디인지 생각해보자.
크루스칼 알고리즘은 왜 그리디일까 ?
-- 간선들의 가중치를 오름차순으로 정렬해서 매번 가장 작은 간선만 선택해서 최소신장트리로 포함시키니까!
다익스트라 알고리즘은 왜 그리디일까?
-- 다익스트라는 시작정점부터 종료정점까지 최단거리를 구하는 알고리즘이다. 매번 이동하면서 다음 정점까지 가는 최소비용을 갱신하며 선택하니까!

각각 알고리즘 정리는 요기 : 크루스칼 & 다익스트라

자바스크립트에서 문자열 ↔ 숫자(열) 변환 방법

• 숫자배열 → 문자열

  const numli = [1,2,3]
  const strli = numli.join("") >> "123"

• 문자열 → 숫자배열

  const strnum = "1924"
  const numli = number.split("").map(e => parseInt(e)))
  // [1,9,2,4]

배열 합치기

• concat()
  합치려는 파라미터가 원소 뿐아니라 배열이더라도 배열에서 원소를 다 꺼내어 하나의 배열로 합침

  const arr = [1, 2, 3];
  const newArr = arr.concat('a', ['b', 'c'], 'abc');
  // 1,2,3,a,b,c,abc

• … (spread 연산자)
  내부 배열에서 원소를 꺼내진 않고 그대로! 합침

  const arr1 = [1, 2, '3'];
  const arr2 = [4,[ 5, 6]];
  
  console.log([...arr1, arr2])
  // [ 1, 2, '3', [ 4, [ 5, 6 ] ] ]

느낀 점

파이썬으론 많이 익숙해진 알고리즘을 js로 해결하려니 아직 어색하다. 특히 dfs풀이에선 스택 풀이가 많았다. 자바스크립트에선 DFS는 스택으로, 큐를 이용하는 BFS는 직접 구현 혹은 다른 풀이로 하는건지 의문이 들었다..
오랜만에 이분탐색, union-find 등의 코드를 짜려니 버벅거렸다. 알고리즘 풀이에 유연해지기는 멀다 . ..

오늘 회고

Keep

실습문제에 시작부터 js로 도전하였다. 효율성이 조금 낮더라도 해답을 보지 않고 완성하려는 것을 목표로 하며 풀어낼 수 있었다.

Problem

실습문제Js 풀 때 변수 자료형 let, const 선언하자!!! 신경쓰자!
BFS,DFS를 js에서 사용하는데에 미숙하다.
크루스칼, 다익스트라 등 그래프 알고리즘 헷갈리지 않게 자주 봐야겠다고 느꼈다.

Try

각 실습문제마다 처음 고안한 풀이, 정답의 알고리즘을 사용한 풀이, 강사님이나 다른 사람의 풀이 등 여러가지 풀이법으로 해결해보았다. 유용한 문법을 배우기도 하고 알고리즘에 대해 이해할 수 있는 방법이었다. 코드를 한데 잘 모아서 정리하고 설명도 주석으로 달아둬야겠다.