아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[동적계획법 : 다이나믹 프로그래밍]
계단오르기
총 N계단일 때, 한 계단 혹은 두 계단씩 올라갈 수 있다. 철수가 올라 갈 수 있는 방법의 수는 몇 가지인지 구하시오
📌 내가 푼 방법
function solution(n) {
let answer = 0;
let dy = []; // dy[i]는 i번 계단까지 오르는 방법의 수
dy[1] = 1;
dy[2] = 2;
function DP(n) {
if(n===1) return 1;
if(n===2) return 2;
else {
return dy[n] = DP(n-2) + DP(n-1);
}
}
answer= DP(n);
return answer;
}
console.log(solution(7));1일때와 2일떄의 값은 직관적으로 알 수 있으니 배열에 저장을 해두고, 그 뒤로 그 이상의 값들을 재귀를 이용해서 찾는다.
📌 강사님 방법
function solution(n) {
let answer = 0;
let dy = []; // dy[i]는 i번 계단까지 오르는 방법의 수
dy[1] = 1;
dy[2] = 2;
for(let i =3; i<=n; i++) {
dy[i] = dy[i-2] + dy[i-1];
}
answer= dy[n];
return answer;
}
console.log(solution(7));다이나믹 방법 --> 복잡한 문제를 한번에 푸는 것이 아닌, 아주 작은 단위로 쪼개서 푸는 것(점화식)
배열에다가 그 값을 저장해서(초기화 해서) 풂 (1차원 배열을 잡아서)
계단이 1개만 있다고 가정 --> 방법 1가지
계단이 2개만 있다고 가정 --> 방법 2가지
계단이 3개 있다고 가정 --> 3개의 계단에서 오르기 위해 어디에서 왔는지 확인! --> 첫 번째 계단 혹은 두 번째 계단에서 올 수 있음
돌다리 건너기
철수가 개울을 만났는데 그 안에 N개의 돌다리가 있다. 철수가 개울을 건너는 방법은 몇 가지인가?
📌 내가 푼 방법
📌 강사님 방법
function solution(n) {
let answer = 0;
let dy = []; // dy[i]는 i번 계단까지 오르는 방법의 수
dy[1] = 2;
dy[2] = 3;
for(let i =3; i<=n; i++) {
dy[i] = dy[i-2] + dy[i-1];
}
answer= dy[n];
return answer;
}
console.log(solution(7));돌다리 건너기에서 마지막돌에 서있으면 안돼서 +1씩 더해주면 dy[1] = 2, dy[2] = 3으로 초기화 시켜서 문제를 푼다.
최대 부분 증가수열
N개의 자연수로 이루어진 수열에서 가장 길게 증가하는 원소들의 집합을 찾아라
📌 내가 푼 방법
📌 강사님 방법
function solution(nums) {
let answer = 0;
let dy = Array.from({length:nums.length}, () => 0); // dy[i] i번째 항이 마지막 항이 되는 최대부분증가수열의 길이!
dy[0] = 1;
for(let i = 0; i<nums.length; i++) {
let max = 0;
for(let j = i-1; j>=0; j--) {
if(nums[j] < nums[i] && dy[j] > max){
max = dy[j];
}
}
dy[i] = max+1;
answer = Math.max(answer, dy[i]);
}
return answer;
}
console.log(solution([5, 3, 7, 8, 6, 2, 9, 4]));dy배열을 i번째 항이 마지막 항이 되는 최대부분증가수열의 길이로 설정해 두고 이중포문을 돌면서 dy배열 안의 값들을 채워나가는데 max변수를 두어서 앞의 항이 자신보다 작은 배열의 값중 가장 큰 값 + 1을 자신의 dy배열에 넣는다.
그렇지 않은 경우(자신보다 큰 항 밖에 없는 경우) max는 기본 그 상태인 0 에서 +1을 해주어 1로 초기화를 시켜준다.
배열을 출력하는 경우
function solution(nums) {
let answer = 0;
let point = 0;
let dy = Array.from({length:nums.length}, () => 0); // dy[i] i번째 항이 마지막 항이 되는 최대부분증가수열의 길이!
let pa = Array.from({length: nums.length});
dy[0] = 1;
pa[0] = -1;
for(let i = 0; i<nums.length; i++) {
let max = 0;
let index = -1;
for(let j = i-1; j>=0; j--) {
if(nums[j] < nums[i] && dy[j] > max){
max = dy[j];
index = j;
}
}
dy[i] = max+1;
pa[i] = index;
if(answer < dy[i]) {
answer = dy[i]
point = i;
}
}
let path = [];
function DFS(index) {
if (index === -1) {
return;
} else {
DFS(pa[index]);
path.push(nums[index]);
}
}
DFS(point);
console.log(pa);
console.log(path);
return answer;
}
console.log(solution([5, 3, 7, 8, 6, 2, 9, 4]));pa배열을 만들어 인덱스 값을 저장하고, 재귀를 이용하여 dy배열에 큰 길이를 가지고 있는 곳의 인덱스부터 거꾸로 올라가서 출력한다.
효율적인 공부
매개변수 times에 구간의 시작시간, 끝나는 시간, 공부효율성이 주어질 때, 가장 높은 효율성은 얼마인지 출력하여라.
📌 내가 푼 방법
function solution(times, r){
let answer= 0;
times.sort((a, b) => a[0] - b[0]); // 끝나는 시간으로 초기화해야함
let dy = [];
dy[0] = times[0][2];
for(let i = 1; i<times.length; i++) {
let max = 0;
for(let j = i-1; j>=0; j--) {
if(times[j][1]+r <= times[i][0] && dy[j] > max) {
max = dy[j];
}
}
dy[i] = max + times[i][2];
}
answer = Math.max(...dy)
return answer;
}
console.log(solution([[3, 5, 20], [4, 7, 16], [1, 2, 5], [11, 13, 7], [9, 10, 6]], 2));앞의 최대부분 증가수열과 로직이 같아서 비교를 할 때 r을 고려해서 시작시간이 겹치지 않는 경우의 dy배열의 값을 가져와 그만큼에서 현재의 공부효율성을 더해 dy배열에 저장하여 최대값을 반환한다.
끝나는 시간으로 초기화해야하므로times.sort((a, b) => a[1] - b[1]);로 바꾸어야함
📌 강사님 방법
function solution(times, r){
let answer= 0;
let m = times.length;
let dy = Array.from({length:m}, () => 0);
times.sort((a, b) => a[1] - b[1]); // 끝나는 시간으로 초기화해야함
for(let i = 0; i<m; i++) {
dy[i] = times[i][2];
for(let j = i-1; j>= 0; j--) {
if(times[j][1]+r <= times[i][0] && dy[j] +times[i][2] > dy[i]) {
dy[i] = dy[j] + times[i][2];
}
}
answer = Math.max(answer, dy[i]);
}
return answer;
}
console.log(solution([[3, 5, 20], [4, 7, 16], [1, 2, 5], [11, 13, 7], [9, 10, 6]], 2));dy[i]를 미리 초기화 시켜두고 비교!
가방문제(냅색 알고리즘)
최고 11kg의 무게를 저장할 수 있는 가방이 있을 때, 보석을 담으면서 최대의 가치가 되도록 하여라
📌 내가 푼 방법
function solution(nums, m){
let answer= 0;
let dy = Array.from({length: m+1}, () => 0); // i무게까지 가방에 담을 수 있을 때의 최대 가치
for(let i = 0; i < nums.length; i++) {
let weight = nums[i][0];
let value = nums[i][1];
for(let j = weight; j < m+1; j++) {
if(dy[j-weight] + value > dy[j]) {
dy[j] = dy[j-weight] + value;
}
}
}
answer = dy[dy.length-1];
return answer;
}
console.log(solution([[5, 12], [3, 8], [6, 14], [4, 7]], 11));📌 강사님 방법
function solution(nums, m){
let answer= 0;
let dy = Array.from({length: m+1}, () => 0); // i무게까지 가방에 담을 수 있을 때의 최대 가치
for(let i = 0; i<nums.length; i++) {
for(let j = nums[i][0]; j<=m; j++) {
dy[j] = Math.max(dy[j], dy[j-nums[i][0]] + nums[i][1]);
}
}
answer = dy[m];
return answer;
}
console.log(solution([[5, 12], [3, 8], [6, 14], [4, 7]], 11));dy[i]: i무게까지 가방에 담을 수 있을 때의 최대 가치 --> dy배열의 정의를 잘 내리는 것이 중요!
첫 번째 보석만 있다고 가정하였을 시, 배열 dy의 인덱스 0~4까지는 가치가 0, 5~9는 12, 10~11까지는 24까지 담을 수 있음
그 다음 보석들을 첫 번째 보석만 있다고 가정한 dy배열에 넣으면서 가치들을 비교하면서 가장 큰 가치가 될 수 있도록 dy의 인덱스의 값들을 바꾸어 주어야함.
동전교환(냅색 알고리즘)
여러 단위의 동전들이 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환하려면 어떻게 해야 하는 가?
📌 내가 푼 방법
📌 강사님 방법
// 동전이 무한정인 경우!
function solution(nums, m){
let answer= 0;
let dy = Array.from({length: m+1}, () => 10000); // i원을 거슬러 줄 때 최소 동전 개수. 최소를 구해야하므로 큰 숫자로 초기화
dy[0] = 0;
for(let i = 0; i<nums.length; i++) {
let coin = nums[i];
for(let j = nums[i]; j <= m; j++) {
dy[j] = Math.min(dy[j], dy[j-coin] + 1);
}
}
answer = dy[m];
return answer;
}
console.log(solution([1, 2, 5], 15));위의 가방문제 냅색 알고리즘과 똑같은 문제
최대점수 구하기(냅색 알고리즘)
제한시간 M안에 N개의 문제를 풀어 최대점수를 반환하여라. 배열에 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어진다.
📌 내가 푼 방법
📌 강사님 방법
// 한 유형당 한개만 풀 수 있음!
function solution(nums, m){
let answer= 0;
let dy = Array.from({length: m+1}, () => 0); // i분을 사용해 얻을 수 있는 최대점수
for(let i = 0; i<nums.length; i++) {
let hour = nums[i][1];
let score = nums[i][0];
for(let j = m; j>=hour; j--) {
dy[j] = Math.max(dy[j], dy[j-hour]+score);
}
}
answer = dy[m];
return answer;
}
console.log(solution([[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]], 20));
한 유형당 한개만 풀 수 있어서 이러한 중복을 피하려면 뒤에서 부터 채워주면 된다!
최대공통부분문자열(LCS)
최대공통부분문자열의 길이를 출력하여라.
📌 내가 푼 방법
function solution(s1, s2){
let answer= 0;
let dy = Array.from(Array(s1.length+1), () => Array(s2.length+1).fill(0)) // dy[i][j]의 의미: s1[0~i]와 s2[0~j]의 최대공통부분문자열의 길이
let s1Arr = s1.split("");
let s2Arr = s2.split("");
s1Arr.unshift(0);
s2Arr.unshift(0);
for(let i = 1; i<s1.length+1; i++) {
for(let j = 1; j<s2.length+1; j++) {
if(s1Arr[i] === s2Arr[j]) {
dy[i][j] = dy[i-1][j-1] + 1;
} else {
dy[i][j] = Math.max(dy[i-1][j], dy[i][j-1]);
}
}
}
answer = dy[s1.length][s2.length];
return answer;
}
console.log(solution('acbehf', 'abefc'));
📌 강사님 방법
function solution(s1, s2){
let answer= 0;
let len1 = s1.length;
let len2 = s2.length;
let dy = Array.from(Array(1001), () => Array(1001).fill(0)) // dy[i][j]의 의미: s1[0~i]와 s2[0~j]의 최대공통부분문자열의 길이
for(let i = 1; i<=len1; i++) {
for(let j = 1; j<=len2; j++) {
if(s1[i-1]===s2[j-1]){
dy[i][j] = dy[i-1][j-1] + 1;
}
else {
dy[i][j] = Math.max(dy[i-1][j],dy[i][j-1]);
}
}
}
answer = dy[len1][len2];
let path= [];
// DFS는 공통부분문자열 출력을 위해!
function DFS(p1, p2) {
if(p1===0 || p2===0) return;
if(s1[p1-1] === s2[p2-1]) {
DFS(p1-1, p2-1);
path.push(s1[p1-1]);
}
else {
if(dy[p1-1][p2]>dy[p1][p2-1]) DFS(p1-1, p2);
else DFS(p1, p2-1);
}
}
DFS(len1, len2);
console.log(path);
return answer;
}
console.log(solution('acbehf', 'abefc'));
dy[i][j]의 의미: s1[0~i]와 s2[0~j]의 최대공통부분문자열의 길이
출력부분은 다음과 같음
출력하라하는 경우에는 끝의 문자가 서로 다른 경우 왼쪽하고 위쪽을 보고 큰 쪽으로 이동한다.
큰쪽으로 이동해서 문자가 같은 경우에는 대각선으로 호출을 한다 --> 호출 밑에서 프린트를 해줌(역으로 나와야 하기 때문)
반복
