본문 바로가기

Algorithm272

[ 자바스크립트(JavaScript) ] section10 - 5 - 최대 점수 구하기(냅색 알고리즘) 📍 section10 - 5 - 최대 점수 구하기(냅색 알고리즘) 문제: 선생님이 내주신 N 개의 문제를 풀려고 한다. 각 문제는 그것을 풀 때 얻는 점수와 푸는데 걸리는 시간이 주어진다. 제한시간 M 안에 N 개의 문제 중 최대 점수를 얻을 수 있도록 해야 한다. (해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 한 유형당 한 개만 풀 수 있다.) 첫 번째 줄에 문제의 개수 N과 제한 시간 M이 주어지고 두번째 줄부터 N줄에 걸쳐 문제를 풀 때 얻는 점수와 문제를 풀 때 걸리는 시간이 주어집니다. // 입력 5 20 10 5 25 12 15 8 6 3 7 4 // 출력 41 이전에 동일한 문제를 부분집합 + edgeCut으로 문제를 풀었다. 하지만, 만약에 문제의 개수가 100개 이상이거나 혹은 .. 2021. 10. 14.
[ 자바스크립트(JavaScript) ] section10 - 4 - 동전 교환(냅색 알고리즘) 📍 section10 - 4 - 동전 교환(냅색 알고리즘) 문제: 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. // 입력 3 1 2 5 15 // 출력 // (5, 5, 5) 동전 3개로 거슬러 줄 수 있다. 3 동전교환 문제는 저번에 dfs(부분집합) + edgeCut을 이용해서 푼 적이 있다. 만약에 동전의 종류가 100개 이상, 거스름 돈이 100,000 이상일 경우 DFS로 풀 수 없다. 이럴 때는 DP에서 냅색 알고리즘으로 풀어야 한다. dp는 거슬러줄 돈(m)만큼 배열의 크기를 선언하고 최소 동전의 개수를 구해야 하므로 개수를 제일 많이 거슬러주는 개수보다 큰 값으로 설정한다.(문.. 2021. 10. 14.
[ 자바스크립트(JavaScript) ] section10 - 3 - 최장 부분 증가수열(LIS) 📍 section10 - 3 - 최대 부분 증가수열(LIS) 문제: N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내고 길이가 5인 최대부분증가수열을 만들 수 있다. 이 문제는 LIS 문제인데, 저번에 현대카드 코딩테스트에서 LIS를 사용하는 문제가 나왔었다. (물론 그때는 몰라서 못 풀었다. 🥲 ) 이번기회에 배우고 다음에 LIS 문제가 나오면 말끔하게 풀어버리자. LIS문제도 마찬가지로 DP를 사용하는데, DP의 특징 중 하나인 각 단계별로 쪼갠 다음, 이.. 2021. 10. 14.
[ 자바스크립트(JavaScript) ] section10 - 2 - 돌다리 건너기 📍 section10 - 2 - 돌다리 건너기 문제: 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌다리를 건널 때 한 번에 한 칸 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요?? 이전에 풀었던 계단 오르기 문제와 매우 흡사하다. 하지만 잘 생각해보면, dp[n]을 구하는 것이 아니라 dp[n+1]을 구하는 문제이다. 왜냐하면 개울을 건너기 위해서는 마지막 돌에 서있으면 안되고(dp[n]), 마지막 돌에서 한 칸 앞으로 전진해야 하기 때문(dp[n+1])이다. let n = 7; console.log(solution(n)); function solution(n){ let dp = Array.from({leng.. 2021. 10. 13.
[ 자바스크립트(JavaScript) ] section10 - 1 - 계단 오르기(DP) 📍 section10 - 1 - 계단 오르기(DP) 이번 섹션은 동적 계획 프로그래밍인(DP)에 대해서 배운다. (넷플릭스 DP 꿀잼 😁) DP 문제는 직관적으로 분석하기 어려운데, 이 감을 키우려면 선생님께서는 역시 양치기 즉, 많은 문제를 풀어봐야 한다고 하셨다. DP문제들의 특징을 살펴보자. DP는 큰 문제를 한 번에 풀기보다는 직관적으로 알 수 있는 단위로 잘게 쪼갠다. 작은 단계부터 답을 dp에 저장하고, 범위를 점차 넓혀간다. 이때, 앞에서 사용한 값을 그대로 사용한다. 직관적으로 알 수 있는 값은 dp에 저장하는데 보통은 dp[1]~dp[2] 정도이고 많으면 dp[0]~dp[3]정도까지 저장한다. 작은 단계부터 경우의 수를 한번 세본다. (이후에는 어떻게 활용할지 고민하기!) 이전 단계와의 .. 2021. 10. 13.

티스토리툴바