DS & Algorithm/baekjoon

[백준] 1182번 부분수열의 합 - JavaScript(NodeJS)

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 정수 N개를 가지고, 모든 부분수열을 구한다. 부분수열 원소들의 합이 S가 되는 부분수열의 개수를 출력한다. N개의 정수를 배열에 받아서 dfs를 실행한다. 부분수열을 만족하기 위해서 재귀의 매 단계에서 L번째 정수를 선택하거나, 선택하지 않는 두가지 경우를 모두 조회해보면 된다. 코드 const sol = (input) => { const [N, S] = input[0].split(" ").map(Number); ..

[백준] 6603번 로또 - JavaScript(NodeJS)

문제 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 입력으로 여러 테스트 케이스가 주어지고, 각 테스트 케이스마다 로또 번호를 선택한다. 로또 번호는 각 테스트 케이스마다 집합 S에서 6개를 뽑은 숫자의 집합이며 모든 경우의 수를 출력해주면 된다. 즉, 각 테스트 케이스마다 N개 중 6개를 뽑는 조합을 모두 모두 나열하면 된다. 입력이 아래와 같이 주어지므로, 첫 번째 수를 변수 N으로 선언하고, 배열 S에 뽑을 수 있는 로또 번호들을 담아 진행한다. 크게 어렵지 않으므로 바로 코드를 보자...

[백준] 14889 스타트와 링크 - JavaScript(NodeJS)

문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 항상 짝수인 N명의 사람들이 있다. 스타트 팀에 N/2명이 들어가는 모든 경우의 수를 구하고, 스타트팀이 아닌 사람은 링크팀에 넣어준다. 그리고 문제에서 주어진 것과 같이, 각 팀 별로 능력치의 합계를 구하고, 차이의 최솟값을 구하면 된다. N은 짝수이며 4 str.split(" ").map(Number)); const check = new Array(N).fill(0); let min = Number.MAX_SAFE_INTEGER; function dfs(L, K) { i..

[백준] 14888번 연산자 끼워넣기 - JavaScript(NodeJS)

문제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 문제가 길고 복잡해보이지만, 결론은 숫자 사이에 연산자를 끼워 넣은 모든 경우의 수를 조회하면 된다. 연산자의 연산은 앞에서부터 진행됨을 유의하면서 모든 연산을 진행하고, 최댓값과 최솟값을 구한다. 풀이 방향 연산자의 갯수가 주어지고, 이를 배열에 순차적으로 담는다. 0:+, 1:-, 2:*, 3:/ 에 대응하는 배열 인덱스를 활용해서 문제를 풀어본다. 수의 개수가 2 oper1 + oper2, 1..

[백준] 1339번 단어 수학 - JavaScript(NodeJS)

문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 브루트 포스 문제지만, 억지로 브루트 포스를 적용해보려고 하다가 좀 헤맨 문제다. 모든 경우의 수를 조회할 수 있는 방법도 있지만, 각 단어를 구성하는 알파벳에 숫자를 대입한 합의 최대값을 출력하는 문제이기 때문에 다르게 접근해봤다. 단어에서 위치한 알파벳들의 자릿수 합을 계산하고, 자릿수의 합 순으로 정렬한다. 자릿수의 합이 큰 알파벳부터 순차적으로 가능한 가장 큰 숫자를 대입한다. "AAA", "BCD"일 때 111A + 100B + 10C ..

[백준] 2529번 부등호 - JavaScript(NodeJS)

문제 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 풀이 Brute Force(무차별 대입, 무식하게 풀기?) 문제이다. 정수의 개수 k의 범위가 2 max ? result : max; min = result < min ? result : min; return; } if (inequality[L] === "