전체 글

[백준 1927] 최소 힙 with Python

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

[백준 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..

[JS] 자바스크립트의 배열 생성 방법

자바스크립트에서 배열은 배열 리터럴, Array 생성자 함수, Array.of 메서드, Array.from 메서드를 통해 생성할 수 있다. 배열을 생성하는 방법이 4가지나 있기 때문에 각각의 생성 방식과 특징을 제대로 이해해야 목적에 맞는 방법을 선택할 수 있을 것이다. 이 외에도 String.prototype.split 메서드처럼 배열을 반환하는 빌트인 객체의 메서드들도 있다. 각각의 배열 생성 방식의 특성을 살펴보고, 몇 가지 기본적이면서도 자주 쓸 수 있는 배열 생성 방법에 대해 알아보자. 1. 배열 리터럴 가장 단순하고 직관적인 배열 생성 방식이다. 거의 대부분의 브라우저에서 가장 성능이 좋은 배열 생성 방법이다. const a = []; const b = [1, 2, 3]; 배열 리터럴 내부에서..

[백준 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*..

[JS] 함수의 매개변수와 RangeError

함수가 호출되면 함수의 매개변수, 반환 주소값, 지역 변수 등의 스택 프레임(Stack Frame)이 호출 스택(Call Stack)에 쌓이게 된다. 재귀함수나 콜백함수에 의해서 함수가 종료되지 않고 너무 많이 호출되면 이러한 스택 프레임들이 호출 스택의 메모리를 초과하게 되면 스택 오버플로우(Stack Overflow)가 발생한다. 함수의 호출이 너무 많아서 스택 오버플로우가 일어날 수도 있지만, 함수를 한 번만 호출했는데 매개변수가 너무 많아서 스택 오버플로우가 발생할 수도 있다. 함수의 매개변수도 호출 스택에 쌓이기 때문이다. const arr = new Array(1000000); const arr2 = [...arr]; 위의 코드에서 length가 1000000인 배열 arr를 스프레드 연산자(..

[백준 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,..