연습장

[백준 11279] 최대 힙 with Python

문제 링크 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 import sys class Heap: def __init__(self): self.arr = [] self.output = [] def heapify_down(self, k, n): while 2*k+1 self.arr[k]: m = L else: m = k if R..

[백준 11724] 연결 요소의 개수 with Node.js

문제 링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); class Node { constructor(value) { this.value = value; this.prev = null; } } class Stack { con..

[백준 5904] Moo 게임 with Python

문제 링크 https://www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 풀이 N = int(input()) def moo(acc, cur, N): prev = (acc-cur)//2 if N prev+cur: return moo(prev, cur-1, N-prev-cur) else: return "o" if N-prev-1 else "m" acc, n = 3, 0 while N > acc: n += 1 acc = acc*..

[백준 18111] 마인크래프트 with Node.js

문제 링크 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n"); const [N, M, B] = input[0].split(" ").map(v => +v); input.shift(); const land = input.join(" ").split(" "); const heightArr = n..

[백준 2104] 부분배열 고르기 with Node.js

문제 링크 https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 www.acmicpc.net 풀이 const input = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/); const N = +input[0]; const A = input.slice(1).map(v => +v); const sums = Array(N+1).fil..

[백준 10830] 행렬 제곱 with Python

문제 링크 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 import sys def prod(a, b): n = len(a) c = [[0 for __ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): c[i][j] += a[i][k] * b[k][j] remainder(c) return c def remainder(A): n = len(A) ..

[백준 1074] Z with Python

문제 링크 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 풀이 def Z(N, r, c, nth): if N == 0: return nth hf = 2**(N-1) if r = hf: return Z(N-1, r, c-hf, nth+hf**2) elif r >= hf and c < hf: return Z(N-1, r-hf, c,..

[백준 1780] 종이의 개수 with Node.js

문제 링크 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 풀이 const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n"); const n = +input[0]; const paper = input.slice(1).map(v => v.split(" ").map(vv => +vv)); const countPaper = n => { const c..

[백준 1992] 쿼드트리 with Node.js

문제 링크 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n"); const n = +input[0]; const screen = input.slice(1).map(v => v.split("").map(vv => +vv)); const genQuadTree = n => { const..

[백준 2630] 색종이 만들기 with Python

문제 링크 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 def count_paper(n): count = [0, 0] def recursion(n, x, y): total = sum([paper[y+yy][x+xx] for yy in range(n) for xx in range(n)]) if total == 0: count[0] += 1 elif total == n*n: count[1] += 1 else: n..