연습장/백준(BOJ) 문제풀이

[백준 9461] 파도반 수열 with Python

문제 링크 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 import sys t = int(sys.stdin.readline()) n = [int(sys.stdin.readline()) for _ in range(t)] dp = [0]*101 dp[1] , dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2 for i in range(6, max(n)+1): dp[i] = dp[i-1] + dp[i-5] for i in n: pri..

[백준 18258] 큐 2 with Node.js

문제 링크 www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n"); class Queue { constructor() { this.head = null; this.tail = null; this.size = 0; } createNode(value, prev, next) { return ..

[백준 11727] 2×n 타일링 2 with Python

문제 링크 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline()) dp = [0]*1001 dp[1] , dp[2] = 1, 3 for i in range(3, 1001): dp[i] = dp[i-1] + dp[i-2] * 2 print(dp[n]%10007) 2 x n 직사각형을 채우는 경우의 수를 f(n)이라고 할 때 f(n)은 아래의 두 경우의 수의 합과 같다. 1. f(n-1)에 2 x 1 타일을 붙이는 경우 ..

[백준 11656] 접미사 배열 with Node.js

문제 링크 www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 풀이 const word = require("fs").readFileSync("/dev/stdin").toString().trim(); const suffix = []; for (let i=0; i

[백준 2193] 이친수 with Python

문제 링크 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline()) dp = [0]*91 dp[1], dp[2] = 1, 1 for i in range(3, n+1): dp[i] = sum(dp[1:i-1]) + 1 print(dp[n]) 이친수는 0으로 시작할 수 없으므로 맨 앞자리 수는 반드시 1이다. 그리고 1이 두 번 연속 올 수 없으므로, 그 다음 자리수는 반드시 0이다..

[백준 10825] 국영수 with Node.js

문제 링크 www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 let [n, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n"); const names = []; arr = arr .map(v => v.split(" ").map(vv => Number(vv)||vv)) .sort((a, b) => { if (a[1] < b[1]) return ..

[백준 2606] 바이러스 with Python

문제 링크 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 import sys class MyGraph(): def __init__(self, n): self.graph = {} for i in range(1, n+1): self.graph[i] = [] def add(self, start, end): self.graph[start].append(end) self.graph[end].append(start) def dfs(self, start): visite..

[백준 2960] 에라토스테네스의 체 with Node.js

문제 링크 www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 풀이 const [n, k] = require("fs").readFileSync("/dev/stdin").toString().trim().split(" ").map(v => +v); const arr = []; for (let i=2; i { if (v % prime === 0) { arr.splice(arr.indexOf(v), 1); nth = v count++; } if (count === k) return true; }); } console.log(nth); 2부터 n까지 수 중에..

[백준 4949] 균형잡힌 세상 with Node.js

문제 링크 www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 풀이 const arr = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n"); const open = ["(", "["]; const closed = [")", "]"]; let stack; const yesno = []; arr.slice(0, arr.length-1).forEach(v => { let isN..

[백준 1764] 듣보잡 with Node.js

문제 링크 www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 const input = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/); const n = +input[0]; const m = +input[1]; const n_arr = input.slice(2, n+2); const m_arr = input.slice(n+2); function binary_search(arr..