DS & Algorithm/baekjoon

[백준] 14226 이모티콘 - JavaScript(NodeJS)

문제 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 처음 시작은 이모티콘 1개로 시작한다. 다음 3가지 연산으로 이모티콘을 S개로 만들면 된다. 모든 연산은 1초가 걸린다. 1. 화면의 이모티콘을 모두 복사해서 클립보드에 저장 2. 클립보드에 있는 이모티콘을 모두 화면에 붙여넣기 3. 화면의 이모티콘 중 한 개 삭제 클립보드에 대한 조건은 다음과 같다. 클립보드에 이모티콘을 복사하면, 이전 클립보드가 덮어씌워진다. 클립보드가 비었다면, 2번 명령 붙여넣기 불가능. 풀이 방향 처음에는 이모티콘 1개로 시작해..

[백준] 13549 숨바꼭질3 - JavaScript(NodeJS)

문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 수빈이가 N의 위치로부터 동생의 위치 K까지 가는 가장 빠른 시간을 구해야 한다. 1초마다 위치 X로부터 X-1, X+1로 이동할 수 있고, 순간이동을 하면 0초 후 2X의 위치로 이동한다. 방법 최소 시간을 구해야 하는 문제로, BFS 알고리즘을 사용한다. 작업마다 소요되는 시간이 다르므로 다음 위치에 방문할 때 우선순위를 고려해야 한다. 수빈이가 동생 위치에 도달하면 재귀가 멈추므로, 0초가 걸리는 2X를 최우선적으..

[백준] 13913 숨바꼭질4 - JavaScript(NodeJS)

문제 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1697번 문제의 연장선이다. 수빈이가 동생에게 도달하기까지의 최소 시간과 지나온 경로까지 구하면 된다. 방법은 BFS를 이용할 것인데, 지나온 경로..

[백준]1697번 숨바꼭질 - JavaScript(NodeJS)

문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 수빈이가 동생이 있는 위치에 도달하기까지 최소 시간을 구하는 문제이다. X 위치의 수빈이는 1초마다 X-1, X+1, 2X 로 이동할 수 있다. 이 문제는 bfs로 쉽게 해결할 수 있다. 주의할 점은 다음과 같다. 계산 속도 향상을 위해서 동일 위치를 수빈이가 다시 방문하지 않도록 해야 한다. 방문할 위치 V는 0 0); function bfs(N) { const queue = []; queue.push([N, 0]); vi..

[백준] 16947번 서울 지하철 2호선 - JavaScript(NodeJS)

문제 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 정답 코드만 보고 싶으신 분은 맨 아래 코드를 참고! 이전 문제였던 (Two Dots 문제)[https://gobae.tistory.com/35] 에서 힌트를 얻었다. 이 문제에서는 2번의 절차가 필요해 보였다. 사이클(순환선)에 해당하는 노드들을 구한다. 모든 노드들을 조회하면서, 사이클까지의 최단거리를 구한다. 대충 이해한 바로는, 1번 절차는 dfs 쓰고, 2번 절차는 bfs를 쓰면 해결이 될 듯 했다. 시간초과 이슈에 ..

[백준] 16929번 Two Dots - JavaScript(NodeJS)

문제 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 풀이 N x M 크기의 게임판에서 사이클을 발견하는 문제이다. 문제에서의 사이클은 아래의 그림과 같이 4개 이상의 점들을 연결했을 때, 선이 아닌 도형을 이루면 된다. 풀이의 흐름은 다음과 같다. dfs를 이용해보자. 1. 현재 위치로부터 동서남북 위치에 있는 노드로 이동이 가능한지를 판단한다. 2. 이동하려는 노드가 처음 출발한 노드와 색이 동일한지 판단한다. 3. 이동하려는 노드가 이미 방문한 곳인지 판단한다. 방문하지 않았다면? => 방문한다...