항해 99 5기 TIL

항해 99

항해 99 5기 TIL_60

Dream Herb 2022. 3. 12. 03:07

▶ Today I Learned

<알고리즘>

[평범한 배낭]

소요시간: 1시간 37분 + 33분 = 2시간 10분

해결여부: 해결

백준 12865번

https://www.acmicpc.net/problem/12865

let fs = require("fs");
let knapsack = fs.readFileSync("dev/stdin").toString().split("\n");
const N = Number(knapsack[0].split(" ")[0]);
const K = Number(knapsack[0].split(" ")[1]);
knapsack = knapsack.map((element) =>
  element
    .trim()
    .split(" ")
    .map((value) => Number(value))
);
const weight = [];
const value = [];
for (let n = 0; n <= N; n++) {
  weight.push(knapsack[n][0]);
  value.push(knapsack[n][1]);
}

const dp = Array.from(new Array(N + 1), () => new Array(K + 1));
// 가로 세로 길이가 N + 1, K + 1 인 테이블을 만든다고 생각하면 쉬움

for (let i = 0; i <= N; i++) {
  dp[i][0] = 0; // 행렬 중 열이라 보면 됨, 몇번째 물건인지를 나타냄
}
for (let j = 0; j <= K; j++) { 
  dp[0][j] = 0; // 행렬 중 행이라 보면 됨, 물건의 무게를 나타냄
}
//테이블의 0번째 행이나 열은 모두 0을 채워넣어줌!
// 물건의 갯수가 0인 경우가 없고 감당 가능한 무게가 0인 경우 역시 없기 때문!
// 각 행과 열이 만나는 지점은 n번째 물건의 k무게에 대한 가치를 나타냄
for (let j = 1; j <= K; j++) {
  if (knapsack[1][0] <= j) {
    dp[1][j] = knapsack[1][1];
  } else {
    dp[1][j] = 0;
  }
}

for (let i = 2; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    if (j < weight[i]) {
      dp[i][j] = dp[i - 1][j];
    } else {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      // dp[i - 1][j]: 예를 들어 현재 물건이 2번쨰고 감당가능 무게가 4라면 첫번째 물건이 감당가능 무게가 4일때 갖는 가치가 몇인지를 나타냄,
      // 이 경우는 dp[1][4]가 될 것이고 해당하는 가치는 0임, 첫번째 물건의 무게가 6이기 때문에 감당가능 무게가 4일 때 배낭에 들어갈 수가 없음
      // dp[i - 1][j - weight[i]] + value[i]: 예를 들어 현재 물건이 2번째고 감당가능 무게가 4인 경우, 두번째 물건은
      // 예제에서 무게가 4이므로 배낭이 감당가능, 그렇다면 배낭에 집어넣은 두번째 물건의 무게인 weight[2]만큼을 수용가능 무게에서 뺴줄 것이고
      // 남은 감당가능무게인 [4 - weight[2]]를 가지고 첫번째 물건인 dp[1]를 찾음, dp[1][0] === 0 이므로 
      // 0 + 8(value[2]임) === 8 임, 그렇다면 0과 8 중 최댓값은 8이므로 8이 출력되는 구조임
      // 이런 식으로 끝까지 연산하면 답이 나옴,
      // 여기서 반복문을 i=1인 경우와 i=2인 경우로 나눈 이유는 i=2인 경우의 식을 적용할 때 i-1이 사용되고
      // i=1인 경우를 같이 넣어버리면 0으로만 이루어져있어 의미없는 dp[0]이 들어가버리기 때문!
    }
  }
}
console.log(dp[N][K]);

처음엔 이해가 힘들었지만 아래 참고자료의 표 설명을 읽고 난 후 해설을 하나하나 들여다보니

이해할 수 있었다.

다음 번에 해설을 참고하지 않고 스스로 식을 짜본다면 분명히 더 이해가 잘 될 것이다!

cf) 이런 문제 유형을 동적 프로그래밍 중 배낭 문제라 칭한다고 한다.

배낭 문제 참고자료:

https://nyang-in.tistory.com/279?category=855466

https://nyang-in.tistory.com/280

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/from

<CS>

[Preflight]

공식문서에 따르면 다음과 같다.

A CORS preflight request is a CORS request that checks to see if the CORS protocol is understood and

a server is aware using specific methods and headers.

즉, CORS 프로토콜이 식별되고 서버가 특정한 메소드와 헤더를 사용한다는 것을 알고 있는지 확인하는 CORS의 request라고 한다.

Preflight 요청은 브라우저에서 어떤 요청을 보내기 전 Options라는 요청으로써 자동으로 이루어지기 때문에 프론트엔드

개발자가 이를 직접 만들어 줄 필요가 없다.

OPTIONS는 Access-Control-Request-Method, Access-Control-Request-Headers, 그리고 Origin header라는

세 가지의 HTTP 헤더를 사용한다.

예를 들어 클라이언트에서 서버에게 DELETE라는 메소드를 요청할 수 있는지 요청 전에 Preflight 요청을 먼저 하게 된다.

만약 서버가 이 메서드를 허용한다면 아래와 같이 해당 DELETE를 담고 있는 Access-Control-Allow-Methods라는 응답 헤더로 응답하게 된다.

HTTP/1.1 204 No Content
Connection: keep-alive
Access-Control-Allow-Origin: https://foo.bar.org
Access-Control-Allow-Methods: POST, GET, OPTIONS, DELETE
Access-Control-Max-Age: 86400

cf) 여기서 동일한 URL에 대해서는 Access-Control-Max-Age라는 것을 사용하여 지정된 시간 동안 해당 URL의 해당 요청에 대한 응답을 캐쉬로 저장할 수도 있다.

참고자료:

https://wonit.tistory.com/571

https://developer.mozilla.org/en-US/docs/Glossary/Preflight_request