개발 개발

전체 글

• BOJ 2579 계단 오르기 (JS)

  백준 문제풀이 2023. 7. 16. 18:47

  https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 오래전에 풀었지만 대표적인 dp 문제이고 점화식이 문제 풀기 전에 대충 생각이나서 잘 풀릴줄알았는데 빠르고 깔끔하게 풀지 못하였다. 1. 테이블 정의 d[i] = i번째 계단을 밟았을 때의 가중치 최대값 2. 점화식 계단이 1개 일때 : O 계단이 2개 일때 : OO 계단이 3개 일때 : Max(OXO, XOO) 계단이 4개 일때 : Max(OXOO, OXO) : 일반식 => Max(d[i-2] + arr[i..

  Read More
• BOJ 11054 가장 긴 바이토닉 부분 수열 (JS)

  백준 문제풀이 2023. 7. 15. 16:50

  https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 어려워서 구글링을 통해서 해결하였다. 핵심 아이디어는 다음과 같다. 왼쪽에서 증가하는 증가 부분 수열을 담은 dp배열과 오른쪽에서 감소하는 감소 부분 수열을 담은 dp2배열의 각 인덱스에서의 합들 중 최댓값을 구하고 1을 빼면된다. 1을 빼는 이유는 기준이 되는 값이 두번 계산이 되기 때문이다. 입력값이 만약 1 5 2 1 4 3 4 5 2 1 일 경우, dp 배열 => 1 2 2 1 3 3 4 5 2 1 dp2 배..

  Read More
• BOJ 14002 가장 긴 증가하는 부분 수열4 (JS)

  백준 문제풀이 2023. 7. 13. 23:20

  https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS 시리즈 문제 중 부분 수열을 출력하는 문제다. 문제가 특이하게 만족하는 부분 수열들 중에 아무거나 출력하란다. dp배열의 값이 갱신될 때마다 배열에 값을 넣어서 출력해야 할지 마지막에 모든 계산이 끝난 dp배열을 탐색해야할지 생각하다가 전자는 아닌 것 같아서 일단 후자를 선택하였다. const fs = req..

  Read More
• BOJ 11055 가장 큰 증가하는 부분 수열 (JS)

  백준 문제풀이 2023. 7. 12. 15:57

  https://www.acmicpc.net/problem/11055 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = fs.readFileSync(filePath).toString().trim().split("\n"); const n = Number(input.shift()); const arr = input[0].split(" ").map(Number); const dp = [...arr]; // 5 4 3 2 10 for (let i = 0; i < arr.length - 1; i++) { for (let target = i + 1; targ..

  Read More
• BOJ 14889 포도주 시식(JS)

  백준 문제풀이 2023. 7. 10. 19:55

  https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net dp로 유명한 계단 오르기 문제와 거의 똑같은 문제다. 우선 포도주의 가중치 값을 담은 배열을 wine이라 하자. n = 1 일때, 1번 포도주를 시식한다. n = 2 일때, 1번 포도주와 2번 포도주를 시식한다. n >=3 일때, 경우의 수가 세가지로 나뉜다. 우선 n = 3일때, 1) O O X 2) O X O 3) X O O 인데, 이것을 확장시켜서 생각해보자. 다음의 ㅁ은 해당 인덱스까지의 ..

  Read More
• 최대 부분 배열 합의 효율성 측정하기

  알고리즘 2023. 7. 10. 17:27

  n개의 정수로 이루어진 임의의 수열이 주어지고, 수를 한 개 이상 선택하여 연속된 부분 수열의 합들 중 최대값을 구하려고 한다. BOJ(1912) : 연속합 문제에서는 n이 1~100000 이므로 O(NlogN) 또는 O(N)으로 풀어야하므로 dp를 풀어서 해결하여야 합니다. O(N^3) 풀이 : n이 10이하일 때 가능 let best = 0; for(let i=0; i 8>5 이므로 부분배열에 넣어서 진행합니다. (sum = 8, best = 8) max( (8+2), 2) => 10>2 이므로 부분배열에 넣어서 진행합니다. (sum = 10, best = 10) max( (10-5), -5) => 5>-5 이므로 부분배열에 넣어서 진행합니다. (sum = 5, best = 10) max( (5+2)..

  Read More
• BOJ 14889 스타티와 링크(JS)

  백준 문제풀이 2023. 5. 20. 15:28

  https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = fs.readFileSync(filePath).toString().trim().split("\n"); const n = Number(input.shift()); const arr=[]; for(let i=0; i

  Read More
• 11주차

  알고리즘 2022. 11. 8. 14:44

  Yes? s → t로 가는 길이 있으면 가능함을 보이면 됨 $(s, a_1, a_2, \dots, a_k, t)$ 의 수열에서, 인접한 두 정점 사이에 간선이 존재해야 함 ($s=t$의 경우에도 길이 있는 것, yes) no라고 하자 (귀류법), 즉 $t$가 방문되지 않았다. 경로를 따라가다가 최초로 방문되지 않은 노드가 있다. 이를 $a_i$라고 하면, $a_{i-1}$과 $a_i$를 잇는 간선이 존재함에도 불구하고 방문하지 않을 수 없다(알고리즘에서 기계적). 따라서 모순이므로, $t$는 방문돼야 하고, 정답은 yes while box is not empty: take one node from box O(m*c) if not not marked: mark node, O(n) computation wi..

  Read More