Skip to content

Commit 412bd09

Browse files
minsoftkminsoftk
committed
graph 문제 추가
1 parent 72ab3fb commit 412bd09

16 files changed

Lines changed: 389 additions & 43 deletions

‎BaekJoon/2805_나무자르기.js‎

Lines changed: 0 additions & 33 deletions
This file was deleted.

‎JS/10.다이나믹프로그래밍/05.가방문제(냅색).js‎

Lines changed: 8 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,14 @@
1-
// 계단 하나로 세분화 시킨다.
2-
function solution(n) {
1+
// 다이나믹은 복잡한 문제를 직관적으로 알 수 있을 정도로 작게 만들어서 bottom-up으로 해결 한다. (점화식)
2+
function solution(arr, m) {
33
let answer;
4-
let dy = Array(n + 1).fill(0);
4+
let dy = Array(m + 1).fill(0); //i kg을 담았을 때 최대가치, dy[m]이 답이 된다.
55

6-
dy[1] = 1;
7-
dy[2] = 2;
8-
for (let i = 3; i <= n + 1; i++) {
9-
if (i === 3 || i === 5) {
10-
continue;
11-
} else dy[i] = dy[i - 2] + dy[i - 1];
6+
for (let i = 0; i < arr.length; i++) {
7+
for (let j = arr[i][0]; j <= m; j++) {
8+
dy[j] = Math.max(dy[j], dy[j - arr[i][0]] + arr[i][1]);
9+
}
1210
}
13-
answer = dy[n + 1];
11+
answer = dy[m];
1412
return answer;
1513
}
1614

‎JS/10.다이나믹프로그래밍/06.동전교환.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
// 다이나믹은 복잡한 문제를 직관적으로 알 수 있을 정도로 작게 만들어서 bottom-up으로 해결 한다. (점화식)
2+
function solution(arr, m) {
3+
let answer;
4+
let dy = Array(m + 1).fill(10000); //i kg을 담았을 때 최대가치, dy[m]이 답이 된다.
5+
6+
dy[0] = 0;
7+
for (let i = 1; i < arr.length; i++) {
8+
for (let j = arr[i]; j <= m; j++) {
9+
dy[j] = Math.min(dy[j], dy[j - arr[i]] + 1);
10+
}
11+
}
12+
answer = dy[m];
13+
return answer;
14+
}
15+
16+
console.log(solution([1, 2, 5], 15)); // 3

‎JS/10.다이나믹프로그래밍/07.최대점수구하기(냅색알고리즘).js‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
// 다이나믹은 복잡한 문제를 직관적으로 알 수 있을 정도로 작게 만들어서 bottom-up으로 해결 한다. (점화식)
2+
function solution(arr, m) {
3+
let answer = 0;
4+
let dy = Array(m + 1).fill(0); //i kg을 담았을 때 최대가치, dy[m]이 답이 된다 = 0.
5+
6+
for (let i = 0; i < arr.length; i++) {
7+
let ps = arr[i][0];
8+
let pt = arr[i][1];
9+
for (let j = m; j >= pt; j--) {
10+
dy[j] = Math.max(dy[j], dy[j - pt] + ps);
11+
}
12+
}
13+
answer = dy[m];
14+
return answer;
15+
}
16+
17+
console.log(
18+
solution(
19+
[
20+
[10, 5],
21+
[25, 12],
22+
[15, 8],
23+
[6, 3],
24+
[7, 4],
25+
],
26+
20
27+
)
28+
); // 41

‎JS/10.다이나믹프로그래밍/08.최대공통부분문자열(LCS).js‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// 다이나믹은 복잡한 문제를 직관적으로 알 수 있을 정도로 작게 만들어서 bottom-up으로 해결 한다. (점화식)
2+
function solution(s1, s2) {
3+
let answer = 0;
4+
let len1 = s1.length;
5+
let len2 = s2.length;
6+
let dy = Array.from(Array(1001), () => Array(1001).fill(0)); //i kg을 담았을 때 최대가치, dy[m]이 답이 된다 = 0.
7+
8+
for (let i = 1; i <= len1; i++) {
9+
for (let j = 1; j <= len2; j++) {
10+
if (s1[i - 1] === s2[j - 1]) {
11+
dy[i][j] = dy[i - 1][j - 1] + 1;
12+
} else {
13+
dy[i][j] = Math.max(dy[i - 1][j], dy[i][j - 1]);
14+
}
15+
}
16+
}
17+
answer = dy[len1][len2];
18+
return answer;
19+
}
20+
21+
console.log(solution('acbehf', 'abefc')); // 4

‎JS/10.다이나믹프로그래밍/09.최소편집.js‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// 다이나믹은 복잡한 문제를 직관적으로 알 수 있을 정도로 작게 만들어서 bottom-up으로 해결 한다. (점화식)
2+
function solution(s1, s2) {
3+
let answer = 0;
4+
let len1 = s1.length;
5+
let len2 = s2.length;
6+
7+
let dy = Array(1001);
8+
for (let i = 0; i < 1001; i++) {
9+
dy[i] = Array(1001).fill(0);
10+
}
11+
12+
for (let i = 1; i <= len1; i++) dy[i][0] = i;
13+
for (let i = 1; i <= len2; i++) dy[0][i] = i;
14+
for (let i = 1; i <= len1; i++) {
15+
for (let j = 1; j <= len2; j++) {
16+
if (s1[i - 1] === s2[j - 1]) {
17+
dy[i][j] = dy[i - 1][j - 1];
18+
} else {
19+
dy[i][j] = Math.min(dy[i - 1][j], dy[i][j - 1], dy[i - 1][j - 1] + 1);
20+
}
21+
}
22+
}
23+
answer = dy[len1][len2];
24+
return answer;
25+
}
26+
27+
console.log(solution('acbehf', 'abefc')); // 4

‎JS/10.다이나믹프로그래밍/10.동전교환1.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
// 다이나믹은 복잡한 문제를 직관적으로 알 수 있을 정도로 작게 만들어서 bottom-up으로 해결 한다. (점화식)
2+
function solution(coin, m) {
3+
let answer = 0;
4+
5+
let dy = Array(m + 1).fill(0); // i원을 만들 수 있는 경우의 수를 저장한다.
6+
dy[0] = 1;
7+
for (let x of coin) {
8+
for (let i = x; i <= m; i++) {
9+
dy[i] += dy[i - x];
10+
}
11+
}
12+
answer = dy[m];
13+
return answer;
14+
}
15+
16+
console.log(solution([2, 3, 5], 10)); // 3

‎JS/11.그래프/01.다익스트라 알고리즘.js‎

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
class minHeap {
2+
constructor() {
3+
this.heap = [];
4+
this.heap.push([Number.MIN_SAFE_INTEGER, 0]);
5+
}
6+
insert([a, b]) {
7+
this.heap.push([a, b]);
8+
this.upheap(this.heap.length - 1);
9+
}
10+
upheap(pos) {
11+
let tmp = this.heap[pos];
12+
while (tmp[1] < this.heap[parseInt(pos / 2)][1]) {
13+
this.heap[pos] = this.heap[parseInt(pos / 2)];
14+
pos = parseInt(pos / 2);
15+
}
16+
this.heap[pos] = tmp;
17+
}
18+
get() {
19+
if (this.heap.length === 2) {
20+
return this.heap.pop();
21+
}
22+
let res;
23+
res = this.heap[1];
24+
this.heap[1] = this.heap.pop();
25+
this.downheap(1, this.heap.length - 1);
26+
return res;
27+
}
28+
downheap(pos, len) {
29+
let tmp, i;
30+
tmp = this.heap[pos];
31+
while (pos <= parseInt(len / 2)) {
32+
i = pos * 2;
33+
if (i < len && this.heap[i][1] < this.heap[i + 1][1]) i++;
34+
if (tmp[1] <= this.heap[i][1]) break;
35+
this.heap[pos] = this.heap[i];
36+
pos = i;
37+
}
38+
this.heap[pos] = tmp;
39+
}
40+
size() {
41+
return this.heap.length - 1;
42+
}
43+
top() {
44+
return this.heap[1];
45+
}
46+
}
47+
function solution(N, road, K) {
48+
let answer = 0;
49+
let minH = new minHeap();
50+
let graph = Array.from(Array(N + 1), () => Array());
51+
let dist = Array.from({ length: N + 1 }, () => 1000);
52+
for (let [a, b, c] of road) {
53+
graph[a].push([b, c]);
54+
}
55+
dist[1] = 0;
56+
minH.insert([1, 999]);
57+
minH.insert([1, 312]);
58+
minH.insert([1, 21]);
59+
minH.insert([2, 2]);
60+
minH.insert([1, 263]);
61+
console.log(minH); //4
62+
minH.insert([1, 0]);
63+
while (minH.size() > 0) {
64+
let tmp = minH.get();
65+
let now = tmp[0];
66+
let nowCost = tmp[1];
67+
if (nowCost > dist[now]) continue;
68+
for (let [next, cost] of graph[now]) {
69+
if (nowCost + cost < dist[next]) {
70+
dist[next] = nowCost + cost;
71+
minH.insert([next, dist[next]]);
72+
}
73+
}
74+
}
75+
if (dist[K] === 1000) answer = -1;
76+
else answer = dist[K];
77+
return answer;
78+
}
79+
console.log(
80+
solution(
81+
6,
82+
[
83+
[1, 2, 12],
84+
[1, 3, 4],
85+
[2, 1, 2],
86+
[2, 3, 5],
87+
[2, 5, 5],
88+
[3, 4, 5],
89+
[4, 2, 2],
90+
[4, 5, 5],
91+
[6, 4, 5],
92+
],
93+
5
94+
)
95+
);

‎JS/11.그래프/02.플로이드와샬.js‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
// 모든 정점에서 모든 정점으로의 최단 거리를 구한다.
2+
// 2차원 배열 distance를 가진다.

‎JS/11.그래프/leet_743_다익스트라.js‎

Whitespace-only changes.

0 commit comments

Comments
 (0)