백준 문제들 추가

minsoftk · minsoftk · commit d3e4b6078219 · 2021-10-28T00:19:19.000+09:00
diff --git a/JS/11.그래프/01.다익스트라 알고리즘.js b/JS/11.그래프/01.다익스트라 알고리즘.js
@@ -60,13 +60,6 @@ function solution(N, road, K) {
 		graph[a].push([b, c]);
 	}
 
-	minH.insert([1, 3]);
-	minH.insert([1, 1]);
-	minH.insert([1, 2]);
-	minH.insert([1, 8888]);
-	minH.insert([1, 88]);
-	minH.insert([1, 8248]);
-	console.log(minH);
 	dist[1] = 0; // 시작점인 1번을 0으로 설정. 사용할 일이 없음.
 	minH.insert([1, 0]); // 시작점을 minheap에 넣어준다.
 
@@ -113,3 +106,4 @@ console.log(
 		5
 	)
 );
+//14
diff --git a/JS/11.그래프/minheap 안쓰는 다익스트라.js b/JS/11.그래프/minheap 안쓰는 다익스트라.js
@@ -1,38 +1,48 @@
 function solution(n, edges, end) {
-	let answer = 0;
-	let graph = Array.from(Array(n + 1), () => Array());
-	let dist = Array(from({ length: n + 1 }, () => 1000));
-	let ch = Array(n + 1).fill(0);
-	for (let [a, b, c] of edges) {
-		graph[a].push([b, c]);
-	}
+	let graph = Array(n + 1);
+	for (let i = 0; i < graph.length; i++) graph[i] = Array();
+	let distances = Array(n + 1).fill(1e9);
+	let checked = Array(n + 1).fill(0);
+
+	// forEach는 배열 요소 각각에 대해서 실행한다.
+	edges.forEach(([start, end, cost]) => graph[start].push([end, cost]));
+
+	// 1부터 시작이므로 check
+	distances[1] = 0;
 
-	/**  min Heap 쓰지 않는 다익스트라 **/
-	dist[1] = 0;
+	// n개의 노드만큼 실행해준다.
 	for (let i = 1; i <= n; i++) {
 		let min = 0;
+		// 0번에 최대값을 이용해서 방문하지 않은 노드 번호를 min 값에 입력해준다.
+		// 방문하지 않았고, dist의 값이 1e9보다 작으면 해당 노드에서 간선을 탐색한다.
 		for (let j = 1; j <= n; j++) {
-			if (ch[j] === 0 && dist[j] < dist[min]) min = j;
+			if (checked[j] === 0 && distances[j] < distances[min]) min = j;
 		}
-		ch[min] = 1;
-		for (let next of graph[min]) {
-			if (dist[min] + cost < dist[next]) {
-				dist[next] = dist[min] + cost;
-			}
+		// 연결된 간선에 도달하는 비용을 저장해준다.
+		for (let [next, cost] of graph[min]) {
+			if (distances[min] + cost < distances[next])
+				distances[next] = distances[min] + cost;
 		}
+		// 처리한 노드는 방문 체크를 해준다.
+		checked[min] = 1;
 	}
-	answer = dist[end];
-	return answer;
+	return distances[end];
 }
 console.log(
 	solution(
 		6,
-		[1, 2, 3, 4, 5],
 		[
-			[1, 3, 6],
-			[2, 2, 5],
-			[1, 5, 2],
+			[1, 2, 12],
+			[1, 3, 4],
+			[2, 1, 2],
 			[2, 3, 5],
-		]
+			[2, 5, 5],
+			[3, 4, 5],
+			[4, 2, 2],
+			[4, 5, 5],
+			[6, 4, 5],
+		],
+		5
 	)
-); // [17, 12]
+);
+// 14
diff --git a/JS/11.그래프/test.js b/JS/11.그래프/test.js
@@ -1,93 +1,48 @@
-class minHeap {
-	constructor() {
-		this.heap = [];
-		this.heap.push([Number.MIN_SAFE_INTEGER, 0]);
-	}
-	insert([a, b]) {
-		this.heap.push([a, b]);
-		this.upheap(this.heap.length - 1);
-	}
-	upheap(pos) {
-		let tmp = this.heap[pos];
-		while (tmp[1] < this.heap[parseInt(pos / 2)][1]) {
-			this.heap[pos] = this.heap[parseInt(pos / 2)];
-			pos = parseInt(pos / 2);
-		}
-		this.heap[pos] = tmp;
-	}
-	get() {
-		if (this.heap.length === 2) {
-			return this.heap.pop();
-		}
-		let res;
-		res = this.heap[1];
-		this.heap[1] = this.heap.pop();
-		this.downheap(1, this.heap.length - 1);
-		return res;
-	}
-	downheap(pos, len) {
-		let tmp, i;
-		tmp = this.heap[pos];
-		while (pos <= parseInt(len / 2)) {
-			i = pos * 2;
-			if (i < len && this.heap[i][1] < this.heap[i + 1][1]) i++;
-			if (tmp[1] <= this.heap[i][1]) break;
-			this.heap[pos] = this.heap[i];
-			pos = i;
-		}
-		this.heap[pos] = tmp;
-	}
-	size() {
-		return this.heap.length - 1;
-	}
-	top() {
-		return this.heap[1];
-	}
-}
-function solution(N, road, K) {
-	let answer = 0;
-	let minH = new minHeap();
-	let distance = Array(N + 1).fill(1e9);
-	let graph = Array(N + 1);
-	for (let i = 0; i < graph.length; i++) {
-		graph[i] = Array();
-	}
-
-	for (let [a, b, c] of road) {
+function solution(n, edges, k) {
+	let answer;
+	let graph = Array(n + 1);
+	for (let i = 0; i < graph.length; i++) graph[i] = Array();
+	let check = Array(n + 1).fill(0);
+	let dist = Array(n + 1).fill(1e9);
+	edges.forEach(([a, b, c]) => {
 		graph[a].push([b, c]);
-		graph[b].push([a, c]);
-	}
+	});
 
-	minH.insert([1, 0]);
-	distance[1] = 0;
-	while (minH.size() > 0) {
-		let [now, time] = minH.get();
-		if (time > distance[now]) continue;
-		for (let [next, nextTime] of graph[now]) {
-			if (time + nextTime < distance[next]) {
-				distance[next] = time + nextTime;
-				minH.insert([next, distance[next]]);
-			}
+	dist[1] = 0;
+	for (let i = 1; i <= n; i++) {
+		let min = 0;
+
+		// min을 이용해서 찾아야하는 노드를 min에 입력
+		for (let j = 1; j <= n; j++) {
+			if (check[j] === 0 && dist[j] < dist[min]) min = j;
 		}
-	}
 
-	for (let x of distance) {
-		if (x <= K) answer++;
+		// min과 연결된 노드들 탐색
+		for (let [next, cost] of graph[min]) {
+			if (dist[min] + cost < dist[next]) {
+				dist[next] = dist[min] + cost;
+			}
+		}
+		check[min] = 1;
 	}
-	return answer;
+	return dist[k];
 }
 
 console.log(
 	solution(
-		5,
+		6,
 		[
-			[1, 2, 1],
-			[2, 3, 3],
-			[5, 2, 2],
-			[1, 4, 2],
-			[5, 3, 1],
-			[5, 4, 2],
+			[1, 2, 12],
+			[1, 3, 4],
+			[2, 1, 2],
+			[2, 3, 5],
+			[2, 5, 5],
+			[3, 4, 5],
+			[4, 2, 2],
+			[4, 5, 5],
+			[6, 4, 5],
 		],
-		3
+		5
 	)
-); // 4
+);
+// 14
diff --git a/boj/1654_랜선자르기.js b/boj/1654_랜선자르기.js
@@ -0,0 +1,32 @@
+const { count } = require('console');
+const fs = require('fs');
+const filePath =
+	process.platform === 'linux' ? '/dev/stdin' : './boj/input.txt';
+let input = fs.readFileSync(filePath).toString().trim().split('\n');
+let [n, m] = input[0].trim().split(' ').map(Number);
+let arr = [];
+for (let i = 1; i < input.length; i++) {
+	arr.push(Number(input[i].trim()));
+}
+function solution(n, m, arr) {
+	function count(mid) {
+		let cnt = 0;
+		for (let x of arr) {
+			cnt += Math.floor(x / mid);
+		}
+		return cnt;
+	}
+	let answer = 0;
+	let left = 1,
+		right = 10e10;
+	while (left <= right) {
+		let mid = parseInt((left + right) / 2);
+		if (count(mid) >= m) {
+			answer = mid;
+			left = mid + 1;
+		} else right = mid - 1;
+	}
+
+	return answer;
+}
+console.log(solution(n, m, arr)); // 200
diff --git a/boj/1931_회의실배정.js b/boj/1931_회의실배정.js
@@ -0,0 +1,31 @@
+const fs = require('fs');
+const filePath =
+	process.platform === 'linux' ? '/dev/stdin' : './boj/input.txt';
+let input = fs.readFileSync(filePath).toString().trim().split('\n');
+
+let n = Number(input[0].trim());
+let work = [];
+for (let i = 1; i < input.length; i++) {
+	work.push(input[i].trim().split(' ').map(Number));
+}
+
+function solution(n, work) {
+	let answer = 0;
+
+	// 회의가 일찍 끝나는 기준으로 오름차순 정렬을 해야지 더 많은 선택을 할 수 있다.
+	// 시작 시간과 끝나는 시간이 같은 경우가 있다. 그래서 같을때는 내림차순 정렬을 해줘야 포함이 된다.
+	work.sort((a, b) => {
+		if (a[1] === b[1]) return a[0] - b[0];
+		return a[1] - b[1];
+	});
+
+	let left = 0;
+	for (let x of work) {
+		if (x[0] >= left) {
+			left = x[1];
+			answer++;
+		}
+	}
+	return answer;
+}
+console.log(solution(n, work)); // 4
diff --git a/boj/1940_주몽.js b/boj/1940_주몽.js
@@ -0,0 +1,36 @@
+const { count } = require('console');
+const fs = require('fs');
+const filePath =
+	process.platform === 'linux' ? '/dev/stdin' : './boj/input.txt';
+let input = fs.readFileSync(filePath).toString().trim().split('\n');
+let [n] = input[0].trim().split(' ').map(Number);
+let [m] = input[1].trim().split(' ').map(Number);
+let temp = [];
+let arr = [];
+for (let i = 2; i < input.length; i++) {
+	temp.push(input[i].trim().split(' ').map(Number));
+}
+for (let x of temp[0]) arr.push(x);
+// console.log(n, m, arr);
+
+function solution(n, m, arr) {
+	let answer = 0;
+	let left = 0,
+		right = n - 1;
+	arr.sort((a, b) => a - b);
+
+	// 같으면 안되는 경우가 있기 때문에 같다를 빼줘야 한다. 반례는 아래에 있다.
+	while (left < right) {
+		if (arr[left] + arr[right] === m) {
+			answer++;
+			left++;
+			right--;
+		} else if (arr[left] + arr[right] < m) left++;
+		else right--;
+	}
+	return answer;
+}
+console.log(solution(n, m, arr));
+// 4
+// 3
+// 1 2 3
diff --git a/boj/19598_최소회의실개수.js b/boj/19598_최소회의실개수.js
@@ -0,0 +1,34 @@
+const fs = require('fs');
+const filePath =
+	process.platform === 'linux' ? '/dev/stdin' : './boj/input.txt';
+let input = fs.readFileSync(filePath).toString().trim().split('\n');
+
+let n = Number(input[0].trim());
+let work = [];
+for (let i = 1; i < input.length; i++) {
+	work.push(input[i].trim().split(' ').map(Number));
+}
+
+// 최소로 사용 가능한 회의실을 구해야된다 -> 최대 겹치는 회의실을 구해야 한다.
+function solution(n, work) {
+	let answer = 0;
+	let arr = [];
+	for (let i = 0; i < work.length; i++) {
+		arr.push([work[i][0], 1]);
+		arr.push([work[i][1], -1]);
+	}
+
+	// 종료시간을 오름차순 해줘서 끝나는 회의를 cnt에서 먼저 빼줘야 한다.
+	arr.sort((a, b) => {
+		if (a[0] === b[0]) return a[1] - b[1];
+		return a[0] - b[0];
+	});
+
+	let cnt = 0;
+	for (let [a, b] of arr) {
+		cnt += b;
+		answer = Math.max(answer, cnt);
+	}
+	return answer;
+}
+console.log(solution(n, work)); // 4
diff --git a/boj/2110_공유기설치.js b/boj/2110_공유기설치.js
@@ -0,0 +1,18 @@
+const { count } = require('console');
+const fs = require('fs');
+const filePath =
+	process.platform === 'linux' ? '/dev/stdin' : './boj/input.txt';
+let input = fs.readFileSync(filePath).toString().trim().split('\n');
+let [n, m] = input[0].trim().split(' ').map(Number);
+let arr = [];
+for (let i = 1; i < input.length; i++) {
+	arr.push(Number(input[i].trim()));
+}
+
+function solution(n, m, arr) {
+	let answer = 0;
+	arr.sort((a, b) => a - b);
+
+	return answer;
+}
+console.log(solution(n, m, arr)); // 200
diff --git a/boj/2583_영역구하기.js b/boj/2583_영역구하기.js
diff --git a/boj/2667_단지번호붙이기.js b/boj/2667_단지번호붙이기.js
diff --git a/boj/2910_빈도정렬.js b/boj/2910_빈도정렬.js
diff --git a/boj/tempCodeRunnerFile.js b/boj/tempCodeRunnerFile.js

Original file line number	Diff line number	Diff line change
`@@ -60,13 +60,6 @@ function solution(N, road, K) {`
`60`	`60`	`graph[a].push([b, c]);`
`61`	`61`	`}`
`62`	`62`
`63`		`- minH.insert([1, 3]);`
`64`		`- minH.insert([1, 1]);`
`65`		`- minH.insert([1, 2]);`
`66`		`- minH.insert([1, 8888]);`
`67`		`- minH.insert([1, 88]);`
`68`		`- minH.insert([1, 8248]);`
`69`		`- console.log(minH);`
`70`	`63`	`dist[1] = 0; // 시작점인 1번을 0으로 설정. 사용할 일이 없음.`
`71`	`64`	`minH.insert([1, 0]); // 시작점을 minheap에 넣어준다.`
`72`	`65`
`@@ -113,3 +106,4 @@ console.log(`
`113`	`106`	`5`
`114`	`107`	`)`
`115`	`108`	`);`
	`109`	`+//14`