-
항해 99 5기 TIL_60항해 99 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://developer.mozilla.org/en-US/docs/Glossary/Preflight_request
▶ 느낀 점
알고리즘의 난이도도 점점 올라가고 웹에 대해서 알아야 할 것도 점점 늘어나고 있다.
여전히 지식의 바다, 홍수 속에 있지만 그래도 이 과정이 꽤나 즐겁기도 하다.
오늘도 이렇게 조금 성장한 자신을 격려해본다.
내일도 화이팅팅! :3
▶ 공부 시 참고 링크들
https://juhi.tistory.com/8#recentComments
https://juhi.tistory.com/9?category=976170
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from
https://sangwoo0727.github.io/network/Network-1_HttpMethod/
'항해 99' 카테고리의 다른 글
항해 99 5기 TIL_62 (0) 2022.03.13 항해 99 5기 TIL_61 (0) 2022.03.12 항해 99 5기 TIL_59 (0) 2022.03.10 항해 99 5기 TIL_58 (0) 2022.03.09 항해 99 5기 TIL_57 (0) 2022.03.08