Computer science/알고리즘

[백준, node.js] 2004번 "조합 0의 개수" 문제 해결방법

문제 예제 입력 & 출력 입력 출력 소스코드 조합 nCm의 끝자리 0의 개수를 출력하는 문제 2의 승수(a1 - b1, c1) 와 5의 승수(a2 - b2 - c2) 가 구해졌으면 겹치는(짝지을 수 있는) 개수를 구하면 되므로, 2와 5의 승수 중 최솟값을 출력 const fs = require('fs'); let [n, m] = fs.readFileSync('./dev/stdin').toString().split(' '); n = Number(n) m = Number(m) function getPowerN(num, power) { let count = 0; while(num >= power) { count += parseInt(num / power); num /= power; } return count..

Computer science/Data Structure

[자바스크립트] 큐(Queue) 자료구조 예시를 통해 쉽게 이해하기

큐(Queue) 자료구조란? 큐(Queue)는 가장 먼저 들어온 데이터가 가장 먼저 나가는(선입선출, FIFO(First In First Out)) 자료구조입니다. 일상생활에서도 쉽게 접할 수 있는데요. 영화관에서 영화를 보러 들어가기 위해 대기하거나, 비행기를 탑승하기 위해 대기를 할 때 먼저 줄을 선 사람이 먼저 들어가는 경우가 바로 큐 자료구조와 같습니다. 코드 구현 예시 굉장히 단순하게 구현할 경우 자바스크립트 배열 자료구조를 활용해서 쉽게 구현할 수 있습니다. 배열 활용 예시 배열의 push, pop, unshift, shift 메서드를 사용할 때 시간복잡도는 O(1)이지만, 데이터를 할당/제거 후 배열을 재구성해야되기 때문에 O(N) 복사 비용이 발생합니다. 그렇기 때문에 배열을 통해 구현할 ..

Computer science/Data Structure

[자바스크립트] 연결리스트(Linked List) 예시를 통해 쉽게 이해하기 (1)

연결리스트(Linked List)란? 연결리스트는 모든 요소(a.k.a 노드)가 다음 요소에 연결된 자료구조입니다. 예를 들어 학교의 한 반에 있는 학생들을 데이터로 저장한다면, 1번 학생 데이터를 노드로 생성할 때 2번 학생 데이터가 어디에 있는지 노드의 위치를 표시하는 방식입니다. 자료가 연결되어있기 때문에 새로운 자료를 앞쪽에 추가/삭제할 때 굉장히 유용하게 사용할 수 있습니다. 하지만 특정한 자료를 불러올 때는 무조건 순회하며 찾아가는 과정이 필요하기 때문에 특정한 노드를 찾기 까다롭다는 단점이 있습니다. 위 예시에서 3번 학생 데이터를 확인하기 위해선 2번 학생 데이터를 무조건 거쳐야 3번 학생 데이터가 어디있는지 알 수 있습니다. 만약 1만명의 학생들이 엮여있다면, 특정 학생을 찾을 때마다 꽤..

Computer science/알고리즘

[백준, node.js] 11729번 "하노이 탑 이동 순서" 문제 해결방법

문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 예제 입력 & 출력 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 ..

Computer science/알고리즘

[백준, node.js] 2133번 "타일 채우기" 문제 해결방법

문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 예제 입력 & 출력 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다. 소스코드 기존에 타일 문제라고 생각하고, 간단히 생각했다가 바로 틀려버린 문제. 문제에 힌트가 있었던 이유가 있었다. DP 점화식을 만들기 위해 N=1, N=2...를 직접 만드는 과정에서 홀수의 경우 타일을 만들 수 없기 때문에 홀수 케이스의 경우 0으로 리턴하면 될 것이고, 짝수의 경우 N-2의 경우의 수 * 3만하면 끝나는 문제라고 생각했다. 힌트를 유심히 살펴보면, N=4의 경우 중간에 끼어있는 예외 케이스가 존재한다는 사실을 깨닫게 된다. 각 케..

Computer science/알고리즘

[백준, node.js] 9461번 "파도반 수열" 문제 해결방법

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 예제 입력 & 출력 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 소스코드 DP로 간단..

Computer science/알고리즘

이진 탐색(Binary Search) 알고리즘 개념 이해 및 예제 feat. Javascript

이진탐색(Binary Search)? 이진 탐색이란 *정렬된* 배열에서 특정한 값을 찾아내는 알고리즘입니다. 배열의 중간 값과 찾고자 하는 값을 비교하며 찾아냅니다. 찾고자 하는 값이 X라고 하면, X가 중간 값보다 작으면(x high) return -1; const mid = Math.floor((low + high) / 2); // console.log('search...', low, mid, high) if (arr[mid] === target) return mid; if (arr[mid] > target) { return bSearch(arr, target, low, mid - 1); } else { return bSearch(arr, target, mid + 1, high); } } const ..

Computer science/알고리즘

[백준, node.js] 2225번 "합분해" 문제 해결방법

문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 예제 입력 & 출력 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 소스코드 문제 자체는 굉장히 단순해서 쉬울줄 알았으나 역시나 DP 문제는 점화식 구해내기가 정말 어러운 것 같다. // 점화식 DP[K][N] = DP[K-1][0] + DP[K-1][1] + ... + DP[K-1][N] const fs = require('fs'); let [n, k] = ..

Computer science/알고리즘

[백준, node.js] 10610번 "30" 문제 해결방법

문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 예제 입력 & 출력 입력 N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 소스코드 이 문제를 해결할 때 아래와 같은 정보를 알고 있다면 굉장히 쉽게 해결할 수 있다. 30배수의 끝자리는 무조건 0으로 끝나야 한다. 다르게 말하면, 0을 포함하지 않는 값은 -1을 출력하면 된다. 각..

Computer science/알고리즘

[백준, node.js] 2875번 "대회 or 인턴" 문제 해결방법

문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다. 예제 입력 & 출력 입력 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ..

Computer science/알고리즘

[백준, node.js] 11052번 "카드 구매하기" 문제 해결방법

문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카..

Computer science/알고리즘

[백준, node.js] 2156번 "포도주 시식" 문제 해결방법

문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 ..

Computer science/알고리즘

[백준, node.js] 11047번 "동전 0" 문제 해결방법

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 예제 입력 & 출력 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 소스코드 전형적인 그리디 알고리즘으로 해결할 수 있는 문제다. 동전 개수 최솟값을 구하기 위해서는 가장 큰 가치를 지닌 동전으로 나눠가면서 해결하..

Computer science/알고리즘

[백준, node.js] 2193번 "이친수" 문제 해결방법

문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 예제 입력 & 출력 소스코드 패턴을 살펴보면 피보나치 방식의 문제임을 파악할 수 있다. 피보나치 점화식은 아래와 같다. memo[i..

Computer science/알고리즘

[백준, node.js] 11726번 "2xn 타일링" 문제 해결방법

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 예제 입력 & 출력 소스코드 "2xn 타일링" 문제는 다이나믹 프로그래밍(DP, 동적계획법)을 활용해서 풀 수 있는 문제입니다. 사용할 수 있는 타일은 1x2, 2x1 두 가지 타일 타입이 존재합니다. 아래는 n이 4일 경우에 대한 예시입니다. n이 1일 경우 2x1 타일 하나만 사용이 가능하기 때문에 1, n이 2일 경우 1x2 타일 2개, 2x1 타일 2개를 사용해서 총 2개의 경우의 수를 낼 수 있습니다. 2x3부터 패턴을 잘 살펴보시면 되는데 아래 그림의 오른쪽 색상으로 표시한 직사각형을 살펴보면 우측에 2x1 타일이 들어갈 경..

Computer science/알고리즘

[백준, node.js] 1463번 "1로 만들기" 문제 해결방법

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력/출력 1 // 입력 2 // 출력 1 예제 입력/출력 2 // 입력 10 // 출력 3 소스코드 다이나믹 프로그래밍(DP, 동적계획법)을 통해 쉽게 해결이 가능한 문제이다. 정수 X에 사용할 수 있는 연산은 1을 뺀 경우, 2로 나누는 경우, 3으로 나누는 경우가 있다. 우선 이 문제를 풀기 위해 정수 X - 1을 했을 경우 정수 X -..

Computer science/알고리즘

[백준, node.js] 10818번 최소, 최대 문제 해결방법

문제 N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. 출력 첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다. 예제 입력/출력 1 // 예제 입력 5 20 10 35 30 7 // 예제 출력 7 35 소스코드 Math.max, Math.min apply를 활용해서 구현하려고 했으나 런타임 에러(Maximum call stack size exceeded)가 발생해서 원인을 찾아본 결과 Math.min의 최대 스택 사이즈는 1..

Computer science/알고리즘

[백준: 9093번] 단어 뒤집기 문제 | 자바스크립트(Javascript(JS), Node)

✍️ 문제 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다. 출력 각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 ..

Computer science/알고리즘

[백준: 9012번] 괄호 문자열(Parenthesis String, PS) 문제 | 자바스크립트(Javascript(JS), Node)

문제 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x..

Computer science/알고리즘

자바스크립트로 피보나치 수열 구현 (fibonacci in javascript)

피보나치 수열이란? 0항을 0, 1항을 1로 두고, 두번 째 항부터는 바로 앞의 두 수를 더한 수로 놓는 것이 피보나치 수열이다. 아래와 같은 점화식을 가지고 있다. F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn;자바스크립트로 구현 임의의 숫자를 매개변수로 받아서 그 숫자만큼 피보나치 수열의 값을 나열하는 로직을 구현해보자. // 피보나치 구현 함수 export function getFibonacci(num) { let i = 0; let value1 = 0; let value2 = 1; let result = []; while (i < num) { let newValue = value1 + value2; result.push(newValue); value1 = value2; value2 =..