javascript

백준 2529번: 부등호 (javascript, DFS, 백트래킹)

완전탐색을 해야하는 문제이며 나는 백트래킹을 이용해서 풀었다. 백트래킹은 DFS의 응용으로 방문하면 안되는 곳은 방문하지 않는 방식으로 탐색범위를 줄이며 탐색표시를 하고 다시 탐색표시를 해제함으로써 모든 범위를 탐색하는 알고리즘이다. 일전에 백트래킹으로 한 문제를 푼 적이 있는데 그 때는 queue에 방문 원소를 넣고 다시 빼고, 방문표시까지 해제하는 식으로 문제를 풀었었다. 그러나 꼭 queue에서 방문 원소를 빼야 하는 것은 아니라는 것을 깨닫고 이 글을 쓰게 되었다. 풀이는 다음과 같다. queue의 길이가 문제에서 주어진 숫자의 개수인 k+1이 되면 queue가 꽉찼다는 의미이므로 배열에 그 값을 넣고 함수를 끝낸다. 그리고 백트래킹의 핵심은 backtract함수에서 보이듯이 for문으로 0~9까..

백준 1697번: 숨바꼭질 (javascript, bfs)

쉬운 문제이나 또 어려운 문제였다. 시간제한도 넉넉하고 문제도 쉬우나 그 시간제한을 맞추게 알고리즘을 짜는게 쉽지 않았다. 가장 빠른 시간, 즉 최소를 묻는 경우는 보통 풀이 알고리즘이 그리디, DP, BFS가 있다. 그 중에 BFS를 이용해 풀었는데 왜냐하면 수빈이가 이동할 수 있는 경우의 수가 3가지로 정해져 있기 때문이다. 처음 푼 풀이는 visited 집합과 queue를 동시에 사용해서 그 점에 방문한 적이 없으면 queue에 넣는 식으로 풀이를 짰다. BFS이므로 queue에 현재 위치와 움직인 시간을 동시에 넣어서 움직인 시간을 계산하고자 했다. const fs = require('fs'); let [N, K] = fs.readFileSync("/dev/stdin").toString().tri..

백준 16234번: 인구이동(javascript, BFS, 완전탐색)

완전탐색이며 BFS로 풀 수 있는 문제이다. 물론 DFS로도 풀어도 되지만 문제 조건에 인접한 국가만 국경을 열 수 있다는 점에서 넓이 우선 탐색이 좀 더 직관적으로 풀 수 있다고 생각해 BFS로 접근하여 풀었다. 예제에서 N이 3이상인, 즉 인구이동이 다른 구역에서 동시에 일어날 때 인구가 어떻게 합쳐지는 지에 대한 설명이 없어 디버깅에 조금 어려움을 겪었던 문제였다. 물론 예제 4,5를 통해 알수는 있지만 그 과정을 일일히 찾기에 어려움이 있었다. 예제 4,5에서 인구이동이 일어나는 과정을 적은 글이 있어 이 문제를 푸는데 어려움을 겪는 사람이 있다면 참고하면 디버깅에 도움이 될 것 같다. const fs = require('fs'); const input = fs.readFileSync("/dev/..

백준 2589번: 보물섬(javscript, BFS, 완전탐색)

전형적인 BFS이며 브루탈 포스(완전탐색) 문제이다. 문제에서 보물이 묻혀있는 곳 두 거리간의 최단거리를 요구하고 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 최단거리로 이동할 수 있는 방법은 BFS 알고리즘이다. 왜 BFS알고리즘이 최단거리인지는 트리를 어떻게 탐색하는 지를 생각해보면 쉽게 이해할 수 있다. 따라서 이 문제는 완전탐색을 통해 BFS로 육지마다 다른 육지들로 이동할 때의 거리들 중 최대거리를 구하면 그 값이 답이 된다. 또한 BFS는 DFS와 다르게 한번의 이동에 주변을 다 탐색하므로 이동할 때마다 이동거리를 증가시키면 안되고 이전 이동거리에 1을 더해서 이동거리를 계산해야 한다. 위 생각을 토대로 짠 코드는 다음과 같다. 주의할 ..

백준 2870번: 수학숙제 (javascript, 구현)

문제 자체는 쉬운 문제였지만 자바스크립트를 공부한 지 얼마 안되다 보니 새롭게 배운 점이 있어 기록을 위해 글을 남겨본다. 먼저 알고리즘은 간단하다. 한 문자열씩 for of문으로 돌면서 숫자인지 아닌지 판별하고 숫자형일 경우 문자가 나올때까지 합쳐서 배열에 넣고, 배열을 마지막에 정렬하여 출력하며 된다. 문제는 문제의 조건에서 각 줄은 최대 100글자라는 조건이 문제다. 엣지케이스를 생각해보면 가장 큰 수는 999...(100자리)일 것이다. 통상적으로 사용하는 javascript의 정수형 자료형은 Number인데 8바이트(64비트)를 사용한다. 이 중 1비트는 부호, 11비트는 지수부이고 52비트가 가수부이므로 Number자료형으로 표현할 수 있는 최대 정수는 2^53-1이다. 이는 당연하게도 문제의..