[백준 알고리즘] 1987번 알파벳 node.js JavaScript JS

1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 😉문제 풀이 설명 문제는 DFS를 사용하여 풀 수 있습니다. 🤨문제 풀이 실패 코드 const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") const [R, C] = input.shift().split(" ").map(Number); const map = input.map((v) => v.split("")); const next =..

• format_list_bulleted 개발관련/백준
• · 2023. 8. 14.
• textsms

[백준 알고리즘] 1208번 부분수열의 합 2 node.js JavaScript JS

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 😉문제 풀이 설명 문제에서 주어진 숫자는 최대 40개. 40개로 부분 수열을 만든다면 경우의 수가 2^40으로 시간초과가 됩니다. 따라서 다음과 같은 전략으로 문제를 풀 수 있습니다. 두 배열을 나누어서 경우의 수를 구합니다. 배열을 두 개로 나누면, 경우의 수가 2^20을 가진 배열 2개를 가지게 됩니다. 2^20은 100만번의 순회가 이루어져 시간 제한을 넘기지 않습니다. 따라서 두 배열 A와 B로 나눈 후 문제를 풉니..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 28.
• textsms

[백준 알고리즘] 2143번 두 배열의 합 node.js JavaScript JS

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 😉문제 설명 두 배열에서 연속된 합의 숫자를 찾은 값의 합이 T가 되는 경우의 수를 찾습니다. A배열에서 찾을 수 있는 경우의 수를 찾아 객체에 넣습니다. 이 객체는 key값으로 만들 수 있는 숫자를, value로 key값을 만들 수 있는 횟수를 넣습니다. B배열에서 찾을 수 있는 경우의 수를 만들며 이 수와 A배열로 만들어진 객체의 값을 더해 T값이 나올 수 있는 경우를 찾습니다...

• format_list_bulleted 개발관련/백준
• · 2023. 7. 28.
• textsms

백준 node.js 1197번 최소 스패닝 트리, 최소 신장 트리 크루스칼 JavaScript JS

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 😉문제 설명 이 문제는 이름 그대로 최소 신장 트리 문제입니다. 최소 신장 트리는 모든 노드를 최소한의 가중치로 모든 간선을 연결 한 것을 말합니다. 문제를 풀기위해서 크루스칼 알고리즘을 사용합니다! 😎문제 풀이 const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") const [V, E] =..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 23.
• textsms

백준 node.js 1916번 최소비용 구하기 다익스트라 알고리즘 JavaScript JS

1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 😉문제 설명 이 문제는 단순한 다익스트라 문제이지만, 주의해야 할 부분이 몇가지 있습니다. 하나의 출발 지점에서 하나의 다른 도착 지점으로 가는 버스 노선이 여러 개 일 수 있습니다. 따라서 최소 비용을 가진 노선만 간선에 넣어주어야 합니다. (모든 노선을 넣으면 시간 초과가 납니다.) 비용이 0인 간선이 있습니다. 아래 코드는 틀린 코드와 맞는 코드입니다. 0은 falsy값 이기 때문에 주의가 필요합니다. 틀린 코드 const..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 21.
• textsms

백준 node.js 11657번 타임머신 벨만-포드 알고리즘 JavaScript JS

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 기본적인 밸만 포드 알고리즘 문제입니다. 각 노드에서 모든 간선을 순회하며 모든 노드를 순회하는 O^2의 시간복잡도를 가집니다. 정확하게는 출발노드를 제외한 N-1개의 노드에서 E개의 간선을 순회하여 NE의 시간복잡도를 가집니다 문제풀이 let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n..

• format_list_bulleted 개발관련/백준
• · 2023. 7. 21.
• textsms