문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 풀이 function solution(n, arr) { // dy[i]는 i분 안에 풀 수 있는 최대 점수 // 해당 문제를 풀 것인지, 아닌지에 따라 최대 점수 구하기 const dy = Array.from({ length: n + 1 }).fill(0); for (let i = 0; i < arr.length; i++) { const [ps, pt] =..
문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 풀이 /** * 다이나믹 프로그래밍(동적 계획법) * - 점화식(관계식)을 만드는 것이 중요 * - 문제를 작은 단위로 쪼개서 구하고, 이걸 기록해뒀다가 문제 범위(데이터 범위) 넓히기 * - dy[n] = dy[n-1] + 3처럼 관계를 구한다. * - 많은 문제를 풀어봐야 한다. */ function solution(n) { const dy = Array.from({ length: n + 1 }).fill(0); dy[1] = 1; dy..
문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 풀이 function solution(m, coin) { let dy = Array.from({ length: m + 1 }, () => 1000); // 가장 작은 동전으로 금액 m 만들 때보다 크게 설정 dy[0] = 0; // 각 동전을 사용할 경우 for (let i = 0; i < coin.length; i++) { // 해당 동전 사용 시 금액마다 필요한 동전 개수 세기 for (let j = coin[i]; j
문제 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다. 풀이 function solution(arr) { const n = arr.length; let dy = Array.from({ length: n }, () => 0); dy[0] = 1; for (let i = 1; i < n; i++) { // 현재까지의 최장 증가 수열 길이는 현재 원소보다 앞에 위치한 작은 수 중 dy 값이 가장 큰 요소에서 1..
문제 현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려 고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력 하는 프로그램을 작성하세요. 만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값 은 22입니다. 풀이 #1 배열 사용 function solution(N, K, arr) { arr.sort((a, b) => b - a); let cnt = 0; const picked = []; for (let i = 0; i < N; i++) { for (let j = i +..
문제 선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라 고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다. 풀이 // 각 학생을 포함시킬 때 pp에 상품가를 저장하고 pd에 배송비를 더한다. // pp에서 최댓값에 50%를 계산해 모두 더한다. // 더한 값이 최댓값이라면 answer에 cnt를 할당한다. function solution(M, arr) { const N = arr.l..
문제 N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력 하는 프로그램을 작성하세요. 자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 합니다. 만약 235 와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력해야 합니다. 풀이 function solution(N, arr) { let maxVal = Number.MIN_SAFE_INTEGER; let answer = Number.MIN_SAFE_INTEGER; for (let num of arr) { const total = [...(num + "")].map(Number).reduce((a, b) => a + b); if (maxVal
문제 N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하 는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출 력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다. 풀이 #1 /** * 소수인지 확인하는 방법 * 1. 2~n 떨어지는 수가 없는 경우 * 2. 2~n/2까지 나눠서 떨어지는 수가 없는 경우 * 2. 2~n의 제곱수까지 나눠서 떨어지는 수가 없는 경우 */ function isPrime(n) { if (n === 1) return false; for (let i = 2; i < Math.sqrt(n / 2); i++) { if (n !== i && n % i === ..
