algorithm/problems

[백준] 1261번 알고스팟_Node.js

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 해당 문제는 BFS문제이다. 하지만 도달하는 최단 거리가 아닌 벽을 최소한으로 부수는 경우를 찾는 것이다. 그렇기에 탐색에 있어서 우선순위가 존재한다. 벽을 최대한 부수지 않는 방식으로 진행하되 목적지에 도달 할 수 없을 때 최소의 벽을 부순다. 이를 구현하기 위해서는 BFS에서 사용되는 queue에 우선순위 별로 넣으면 된다. 기존의 문제에서 queue를 사..

[백준] 14225번 부분수열의 합 _ Node.js

문제 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 풀이 해당 문제는 부분 수열로 나타낼 수 없는 수 중 가장 작은 수를 출력하는 문제이다. 해당 문제는 조합으로 부분 수열을 탐색이 가능하지만 간단하게 이진수로 나타내어 풀었다. 부분 수열은 해당 수열의 요소가 존재하거나 안하거나로 나타낼 수 있다. 부분 수열에 존재 할 때는 1, 아닐 경우는 0으로 나타낸다. 문제의 1..

[백준] 14226번 이모티콘 - Node.js

문제 문제 풀이 해당 문제는 3가지 진행 방식으로 진행하여 원하는 개수의 이모티콘을 만드는 최소의 방법을 구하는 문제이다. 최소의 방법을 구하기 위해 BFS를 사용하였다. 3가지의 진행 방식을 아래와 같이 오브젝트로 생성하였다. count는 현재 이모티콘의 길이, x는 클립보드의 저장된 이모티콘의 길이이다. const actionCase = { copy (count ,x){ return [count ,count] }, paste (count ,x){ return [count + x, x] }, deleteOne (count,x){ return [count-1,x] } } 해당 진행 방식으로 BFS로 진행하면 된다. 하지만 일반적인 BFS문제와 다른 점이 있다. 그것은 클립보드이다. 일반적인 BFS문제는 ..

[백준] 1697번 숨바꼭질 _ Node.js

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 이 문제는 1초씩 움직이며 동생에게 도착하는 최소 시간을 구하는 문제이므로 BFS를 사용해보았다. 수빈이는 1초마다 +1 , -1 , X2로 세가지 방법으로 움직일 수 있다. 이 때 위치는 0 stdin[line++]; })(); function solution(){ const [N, K] = input().split(" ").map(Number); co..

[백준] 15988번 1, 2, 3 더하기 3

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 예시 입/출력을 보자. 4, 7, 10과 같은 작은 수가 나오더라도 이에 수 십배의 경우의 수가 나온다. n의 최댓값이 1,000,000인 것을 감안하면 완전 탐색은 불가능하다. 문제를 조금 더 분석해보자. 식으로 나타낼 수 있는 숫자는 1, 2, 3이다. 나타내야 하는 수를 k라 할 때, k를 나타내기 위해서는 k보다 작은 수에서 1,2,3을 더하면 된다. 즉 k를 1,2,3으로 나타 낼 수 있는 방법 k-1 +1, ..

[백준] 2178번 미로 탐색

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 해당 문제는 처음에 DFS로 시도하였다. 하지만 시간초과가 나왔다. 미로의 최대 크기는 100X100 사이즈이므로 DFS나 완전 탐색으로 풀이 할 경우 시간 초과가 뜬다. 이 후 BFS로 풀이를 하였다. DFS는 queue의 현재 위치를 shift하여 해당 점에서 움직일 수 있는 모든 방향을 queue에 추가한다. 이 때 막히거나 방문한 곳은 push하지 않는다. 더해서 맵과 같은 크기의 이중 배열 visited..