백준

백준 1987번: 알파벳(javascript, DFS, 백트래킹)

말이 지날 수 있는 최대의 칸 수를 구하는 문제이다. 최대의 칸을 구해야 하기 때문에 단순 BFS가 아닌 완전탐색 혹은 백트래킹을 이용해 문제를 풀어야 하겠다고 생각했다. 왜냐하면 DFS나 BFS는 한번 방문한 곳은 다시 방문하지 않는데 이 때문에 방문경로에 따라 최대값이 달라지는 경우가 생기기 때문이다. 백트래킹 풀이를 위해서 방문배열을 만들었는데 아스키코드를 이용해 방문을 체크하였다. 왜냐하면 Set자료형에 방문한 알파벳을 넣을수도 있지만 Set은 원소를 집어넣을 때 O(n)이 필요하지만 아스키코드를 이용해 배열의 인덱스에 바로 접근하면 O(1)로 시간복잡도를 줄일 수 있기 때문이다. 그리고 DFS의 인수로 cnt를 주어서 DFS가 재귀할 때마다 cnt에 1을 더해 최대값을 구하고자 했다. 이를 이용..

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

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

백준 13913번: 숨바꼭질4 (javascript, BFS)

숨바꼭질 문제의 변형판이다. 최단경로와 그 경로를 출력해야 한다. 최단경로는 이전에 구한 것처럼 BFS를 이용해 구할 수 있다. 새로운 배열을 선언하고 방문한 점의 위치에 이전 점의 위치를 저장하고, 목표 위치인 K에 도착했을 때 반복문으로 이전 좌표들을 따라감으로써 방문경로를 확인하였다. 코드는 다음과 같다. const fs = require('fs'); let [N, K] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(a => Number(a)) function BFS(x, k){ let queue = [x] let array = new Array(MAX).fill(0) let path = new Array(MAX).fill(0) ..

백준 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을 더해서 이동거리를 계산해야 한다. 위 생각을 토대로 짠 코드는 다음과 같다. 주의할 ..

백준 1325번: 효율적인 해킹(javascript, DFS)

문제는 쉬웠지만 시간관리를 잘해야 하는 문제였다. 문제는 기본적인 문제인데 트리 구조를 만든 후 부모노드를 통해 자식 노드의 개수들을 세는 문제였다. 최대값을 찾아야 하므로 완전탐색을 이용해야 함을 알 수 있었고 N이 10^4로 좀 컸지만 시간제한이 5초로 매우 넉넉하여 쉽게 풀 수 있을것 같았다. 그러나 시간초과가 여러번 났는데 트리를 탐색하는 방법에 문제가 아닌 트리를 배열로 표현하기 위해 배열을 선언하는 과정에서 문제가 있음을 알 수 있었다. 먼저 원래의 배열 선언 코드는 다음과 같다. let tree = new Array(N+1) for(let i=0; i Number(a)) const tree = Array.from({ length: N + 1 }, () => []); for (let i=1; i

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

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