알고리즘9 백트래킹 Javascript DFS 문제 풀이를 보다 보면 dfs로 탐색을 하다가 탐색이 끝나면 방문 했던 노드나, 값을 취소하는 코드가 있는데 예를 들어 아래 코드의 경우 울타리를 세울수 있는 경우 울타리를 세우고 dfs 탐색을 한 다음 끝나면 울타리를 제거하고 for 문을 계속 돌아준다. 나는 지금까지 책 풀이를 볼 때 이런 경우 백트래킹이라고 딱히 명시를 안해줘서 이런 경우는 그냥 이렇게 풀어야 되는구나로 알고 있었는데 이런 풀이가 백 트래킹이란 것을 오늘 알았다. 백트래킹이란? 해결책을 구하기 위해, 후보군을 구하다가, 해당 후보군이 문제의 조건을 만족하지 않으면, 다시 이전의 상태로 돌아가 다른 후보군을 찾는 기법이다. map에서 빈 곳일때(0) 울타리를 세우는(1) 과정이다. dfs 탐색을 하여 해당 함수가 끝나면 울타리.. 2023. 4. 3. [14502] 연구소 Javascript https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 옛날에 책 보고 풀던시절 몇 번을 풀어도 이해가 안갔는데 지금은 풀린다 답지랑 풀이가 비슷하다 이코테 책으로 풀어서 zeroSum, reduce 함수는 그냥 따로 써봤다. 한번 직접 사용해 볼겸 0의 갯수를 세는 거는 아무렇게나 해도 됨 원본 코드 const fs = require('fs'); const PATH = process.platform === 'linux' ? '/dev/stdin' : './bae.. 2023. 4. 1. [10026] 적록색약 javascript https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 나는 같은 색이면 dfs를 수행하고 적록색이면 한 번 더 dfs를 수행하는 방식으로 풀었다. 코드 const fs = require('fs'); const PATH = process.platform === 'linux' ? '/dev/stdin' : './baekjon/input.txt'; const input = fs.readFileSync(PATH).toString().trim().sp.. 2023. 4. 1. 자바스크립트 힙(javascript heap) 야! 너 좀 힙한데?(이것만 보면 힙 가능) 자바스크립트로 코딩 테스트 문제를 풀면 우선순위 큐를 사용할 시간이 오게 된다. 하지만 아쉽게도 자바스크립트는 직접 코드를 작성해야 한다. 🥲 우선순위 큐를 알아보기 전에 우선순위 큐는 힙으로 되어있다. 그렇기 떄문에 근본인 힙을 알아야 한다. 힙부터 알아보자. 힙이란? 트리 구조의 일종으로 이진 트리와 비슷해 보이지만 다르며, 최대 이진 힙, 최소 이진 힙이 있다. 힙이랑 이진 힙이랑 같다고 보명 된다. 😀 힙은 이것만 알면 된다능~ 최대 이진 힙 기준 1. 트리의 루트는 최대 값이다. 2. 자식 노드는 항상 부모노드보다 작다. 3. 자식 노드는 순서가 없다. -> 이진트리랑 핵심 차이이다. 4. 최대 2개의 자식노드를 가질 수 있다. 이것만 알면 끝이다. 아래 사진은 이진트리와 최대 이진 힙의 차이다.. 2023. 1. 30. 이전 1 2 3 다음
