알고리즘3 백트래킹 Javascript DFS 문제 풀이를 보다 보면 dfs로 탐색을 하다가 탐색이 끝나면 방문 했던 노드나, 값을 취소하는 코드가 있는데 예를 들어 아래 코드의 경우 울타리를 세울수 있는 경우 울타리를 세우고 dfs 탐색을 한 다음 끝나면 울타리를 제거하고 for 문을 계속 돌아준다. 나는 지금까지 책 풀이를 볼 때 이런 경우 백트래킹이라고 딱히 명시를 안해줘서 이런 경우는 그냥 이렇게 풀어야 되는구나로 알고 있었는데 이런 풀이가 백 트래킹이란 것을 오늘 알았다. 백트래킹이란? 해결책을 구하기 위해, 후보군을 구하다가, 해당 후보군이 문제의 조건을 만족하지 않으면, 다시 이전의 상태로 돌아가 다른 후보군을 찾는 기법이다. map에서 빈 곳일때(0) 울타리를 세우는(1) 과정이다. dfs 탐색을 하여 해당 함수가 끝나면 울타리.. 2023. 4. 3. 자바스크립트 힙(javascript heap) 야! 너 좀 힙한데?(이것만 보면 힙 가능) 자바스크립트로 코딩 테스트 문제를 풀면 우선순위 큐를 사용할 시간이 오게 된다. 하지만 아쉽게도 자바스크립트는 직접 코드를 작성해야 한다. 🥲 우선순위 큐를 알아보기 전에 우선순위 큐는 힙으로 되어있다. 그렇기 떄문에 근본인 힙을 알아야 한다. 힙부터 알아보자. 힙이란? 트리 구조의 일종으로 이진 트리와 비슷해 보이지만 다르며, 최대 이진 힙, 최소 이진 힙이 있다. 힙이랑 이진 힙이랑 같다고 보명 된다. 😀 힙은 이것만 알면 된다능~ 최대 이진 힙 기준 1. 트리의 루트는 최대 값이다. 2. 자식 노드는 항상 부모노드보다 작다. 3. 자식 노드는 순서가 없다. -> 이진트리랑 핵심 차이이다. 4. 최대 2개의 자식노드를 가질 수 있다. 이것만 알면 끝이다. 아래 사진은 이진트리와 최대 이진 힙의 차이다.. 2023. 1. 30. JavaScript 조합 구현하기 어짜피 또 까먹을 미래의 나에게. 이걸 보러 왔다면, 또 까먹었구나. 일단 코드부터 보자 function combinations(arr, selectNumber) { const result = []; if (selectNumber === 1) return arr.map((el) => [el]); arr.forEach((fixed, index, origin) => { const rest = origin.slice(index + 1); const cms = combinations(rest, selectNumber - 1); const attached = cms.map((el) => [fixed, ...el]); result.push(...attached); }); return result; } 오랜만에 봐서.. 2023. 1. 26. 이전 1 다음
