🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준
-
[백준/알고리즘기초1] 자료구조1. 9012번 괄호(JavaScript)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 10. 12. 21:15
문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 const fs = require('fs'); const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n'); const T = parseInt(input.shift(), 10); let result = []; for (let i = 0; i < T; i++) { let temp = in..
-
[백준/알고리즘기초1] 자료구조1. 10828번 스택(JavaScript)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 10. 10. 10:42
문제 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 첫번째 풀이 : 시간초과 코드는 아래와 같았다. 철저히 .. 문제를 코드로 구현한 .. 수준..ㅋ const fs = require('fs'); const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n'); const N = parseInt(input.shift(), 10); let stack = [];..
-
[백준/그래프탐색] 1743번. 음식물피하기(JavaScript)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 8. 30. 20:36
문제설명 https://www.acmicpc.net/problem/1743 2667번 단지번호붙이기와 비슷하게 푸는 DFS문제이다. 문제풀이 const fs = require("fs"); let input = fs.readFileSync("../test.txt").toString().split("\n"); let NMK = input.shift().split(' ').map(el => parseInt(el, 10)); const N = NMK.shift(); const M = NMK.shift(); const K = NMK.shift(); let graph = Array.from(new Array(N), () => new Array(M).fill(0)); for (let i = 0; i < K; i++)..
-
[백준/완전탐색] 5618번. 공약수(JavaScript)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 8. 2. 12:08
문제 https://www.acmicpc.net/problem/5618 풀이 const fs = require('fs'); const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n'); const n = parseInt(input.shift(), 10); const data = input.toString().split(' ').map(Number); data.sort((a, b) => a - b); let result = []; function solution(n, data) { let arrays = []; for (let i = 0; i < n; i++) { let array = new Array(); for (let j = 1;..
-
[백준/최소 스패닝 트리] 1197번. 최소 스패닝 트리, 1922번 네트워크 연결(Python)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 7. 30. 10:24
문제 https://www.acmicpc.net/problem/1197 https://www.acmicpc.net/problem/1922 풀이 최소 스패닝 트리(Minimum Spanning Tree) : 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리 MST를 구하는 방법은 크루스칼 알고리즘과 프림알고리즘이 있다. 크루스칼 알고리즘 : 모든 간선에 대해 가장 가중치가 작은 간선부터 하나씩 이어나가며 모든 정점을 방문하는 방법 - 사이클이 발생하면 그 간선은 건너 뛰어야 한다. - 사이클 발생유무를 체크하기 위해서는 유니온 파인드 구조를 사용한다. - 간선이 연결하는 두 개의 노드가 같은 집합에 속하면? 사이클이 존재 - 간선이 연결하는 두 개의 노드가 같은 집합..
-
[백준/우선순위큐,힙] 2696번. 중앙값 구하기(Python)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 7. 28. 00:13
문제 중앙값 구하기 https://www.acmicpc.net/problem/2696 풀이 우리가 일반적으로 아는 방법은 일단, 입력을 다 받은 후 정렬하고 가운데 인덱스의 값을 출력하면 되지 않을까?이다. 현재 테스트 케이스 개수가 최대 1000개이고, 각 테스트 케이스 수열 크기가 약 10000개까지인데, 홀수번마다 정렬하여 가운데를 출력하는 방식을 사용하면, 길이가 n인 배열을 정렬할 때는 nlogN이 걸리고, 홀수번마다 정렬하므로 n/2번 x nlogN 해서 약 n^2 logN 으로 계산되고, n이 약 10000(10^4)까지 가능하니까 한개의 테스트 케이스에 10^8 log 10^4이고, 최대 1000개의 테스트 케이스라면 위의 값에 1000을 곱한 10^3 x 10^8 log 10^4 이니까 ..
-
[백준/그리디] 1931번. 회의실배정(JavaScript)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 7. 26. 18:09
문제 이 문제의 시간제한은 2초로 1초 당 간단한 연산을 1억번(10^8) 정도 계산할 수 있기 때문에 2초면 대략 2억번의 연산까지 허용된다고 생각하고 풀어야 한다. 완전탐색으로 풀었을 시 입력이 최대 10만(10^5)인데, 모든 경우의 수(N^2)를 구한 후 각 경우의 회의개수 중 최대 개수를 구할 수 있지만, 최악의 경우 10^5 x 10^5 = 10^10의 시간 복잡도가 요구되어 효율적이지 않다. 따라서 현재 상황에서는 지금 당장 좋은 것만 고르는 그리디 알고리즘으로 풀어야 한다. 이 문제는 그리디 알고리즘의 대표유형 중 하나인 활동선택문제에 해당한다. (*활동선택문제: 한 번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제..
-
[백준/유니온파인드] 20040번. 사이클게임(JavaScript)🧠𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/💛 백준 2021. 7. 26. 17:02
문제 https://www.acmicpc.net/problem/20040 풀이 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 몇번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행중인지 판단하는 문제이다. 즉, 지금까지 그린 선분이 사이클이 이뤄진 것인지 판단하는 문제이다. 현재 제공되는 두 개의 노드의 부모가 같은지 (=하나의 집합인지) 보면 해결되는 유니온 파인드 문제이다. 알고리즘은 다음과 같다. 노드와 노드를 잇기 전에 두 개가 같은 그래프 내에 속해 있는지 두 노드의 부모노드를 확인한다. 부모노드가 같다면 몇 번째 차례에서 완성되었는지 출력한다. 부모노드가 다르다면, 각각의 부모노드를 구한다음 더 작은 값 쪽으로 부모를 합쳐준다. 코드는 다음과 같다. const fs..