문제 출처 https://www.acmicpc.net/problem/11066 정답 코드 전략1. 주어진 파일을 순서대로 합치고, 파일을 합치는 비용은 두 파일 크기의 합이다. 2. 여러 파일을 합치기 위해 최적 부분 구조를 활용한 dp를 사용하여, 부분 문제들의 최솟값을 저장하며 문제를 해결한다. 3. 합칠 파일의 범위를 설정하고, 그 범위 내에서 파일을 합치는 최소 비용을 찾는 방식으로 접근한다.  해결 과정1. 먼저 각 파일의 크기를 저장하고, 파일의 누적합 배열을 미리 구한다. 2. dp 테이블을 설정하여 각 구간에서의 최소 비용을 기록한다. 3. 주어진 파일들을 두 그룹으로 나누고, 각 그룹을 합친 뒤 다시 합치는 비용을 반복적으로 계산한다.  누적합 배열 : 0번째 부터 i 번째 파일까지의 크..

문제 출처 https://www.acmicpc.net/problem/1949 정답 풀이 백준의 "우수마을" 문제는 트리 DP(dynamic programming on trees)를 사용하는 전형적인 문제입니다. 이 문제는 트리를 기반으로 우수 마을을 선정하여 마을 주민 수의 최대합을 구하는 문제입니다.문제 접근 방법:각 마을이 트리 형태로 연결되어 있다는 점을 이용해 DFS 탐색을 기반으로 DP를 적용해야 합니다.각 마을은 우수 마을이 될 수도 있고, 아닐 수도 있습니다.우수 마을이 될 경우, 이 마을과 연결된 다른 마을은 우수 마을이 될 수 없습니다.각 마을을 우수 마을로 선정하는 경우와 그렇지 않은 경우를 나눠서 DP로 해결합니다.알고리즘트리에서 DP를 사용하기 위해 DFS로 각 노드를 탐색합니다.각..

문제 출처 https://www.acmicpc.net/problem/11054 정답 풀이  increaseDP 배열:앞에서부터 현재 원소까지의 가장 긴 증가 부분 수열의 길이를 저장합니다.각 원소에 대해, 이전 원소들과 비교하여 자신보다 작은 값을 만나면 그 길이에 1을 더해 더 긴 수열로 갱신합니다.decreaseDP 배열:뒤에서부터 현재 원소까지의 가장 긴 감소 부분 수열의 길이를 저장합니다.각 원소에 대해, 이후 원소들과 비교하여 자신보다 작은 값을 만나면 그 길이에 1을 더해 더 긴 수열로 갱신합니다.결과 계산:각 인덱스에서 증가 부분과 감소 부분 수열을 더한 값을 구하고, 이 값 중 가장 큰 값을 선택합니다.증가 부분과 감소 부분에서 현재 원소가 두 번 더해지므로 마지막에 1을 빼줍니다.  각 ..

문제 출처 https://www.acmicpc.net/problem/2293 정답 풀이 주의 : js로는 메모리 초과가 난다.  아래와 같이 2차원 그래프를 만들어줄 것이다. 세로 줄에는 동전의 가치 가로 줄에는 가치의 합이다. 그리고 각 그래프 안에는 해당 동전과 이전 동전으로 해당 합을 만들 수 있는 경우의 수를 구할 것이다.  우리는 저 빨간 부분을 return 해주면 된다.    아래 같은 경우에는 1 동전으로 1의 가치를 만들 수 있는 경우의 수는 1이다. (1 동전 1개)1 동전으로 8의 가치를 만들 수 있는 경우의 수는 8이다. (1 동전 8개)  그리고 아래와 2동전으로 가치의 합의 경우의 수를 구할 때, 가치의 합 2부터 생각해주면 된다. 왜냐하면 동전 2로는 가치 1을 만들 수 없기 때..

문제 출처 https://www.acmicpc.net/problem/2293 정답 풀이 알아보니, 이 문제는 js언어로 메모리 초과가 나는 문제인 것 같다.  이 분의 풀이를 보면 이해가 더 쉬울 것 같다. https://www.youtube.com/watch?v=LBOQikSpfNg 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,k] = input.shift().split(' ').map(v => +v); const arr = []; for(let i=0; i틀린 코드 완전탐색의 방법밖에 떠오르지 않았다.. 메모리 초과... 가 될 걸 알았지만 작성한 이유는, 요즘에는 ..

문제 출처 https://www.acmicpc.net/problem/12865 정답 풀이 풀이 보니까, dp로는 유명한 문제라는데 아직도 못 푸는 나 자신 머리 한대 때리고 시작하자.  이해하면 코드는 간단하나, 이해하기 생각보다 빡셌다. 다른 분들의 블로그를 봐도 잘 이해가 안갔고, 그래서 내가 이해한 방식대로 글을 작성해볼 예정이다.  ## dp 그래프 생성 아래와 같이 2차원 그래프 dp를 생성해줄 것이다. 세로 의미: 각 물건의 무게와 가치 가로 의미: 준서가 버틸 수 있는 무게  그렇다면 dp 그래프의 의미는 어떻게 될까? 각 물건을 넣고, 안넣고에 따라서 + 준서의 배낭 각 무게에 따라의 '가치'를 계속 update 해줄 것임. (이해가 안가도 아래 쭉 예시를 읽어보자 !) ## 초기화 아래 ..

문제 출처 https://www.acmicpc.net/problem/9251 정답 풀이 - 두 문자열의 공통 부분 수열 중 가장 긴 부분 수열을 찾는 것. - 부분 수열은 원래 문자열에서 문자를 순서를 유지한 채 일부를 선택하여 만든 문자열이다.  DP 접근 방법 - 두 문자열의 각 문자 쌍을 비교하면서 최장 공통 부분 수열을 점진적 계산 - 2차원 배열 사용 - 각 셀 DP[i][j]는 첫번째 문자열의 첫 i개 문자와 두번째 문자열의 첫 j개 문자를 비교했을 때의 LCS 길이를 나타낸다.  테이블 초기화 - DP[i][0]와 DP[0][j]는 0을 초기화한다. 왜냐하면 공백과 어떤 문자열을 비교하면 공통 부분 수열의 길이는 항상 0이다.  점화식 - str[i-1] 과 str[j-1]이 같으면 dp[i..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이 힌트 정답 풀이 코드 function solution(n, tops) { const MOD = 10007; const dp = new Array(n + 1).fill().map(() => new Array(2).fill(0)); dp[0][0] = 1; for (let i = 0; i Only 풀이 코드 function solution(n, tops) { const M..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이 힌트 DP를 활용하는 문제이다.  DP 배열 dp[i][j] : (알고력 i, 코딩력 j) 상태에 도달하는 데 필요한 최단 시간 DP 배열 업데이트 알고리즘을 공부하여 알고력을 1 높이는 경우:dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)코딩을 공부하여 코딩력을 1 높이는 경우:dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)문..

문제 출처 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000..