https://www.acmicpc.net/problem/2293  해당 문제는 DP를 사용해 주어진 동전의 가치로 해당 금액(k)을 만들 수 있는 경우의 수를 구하는 문제이다.문제 예제와 같이 3가지의 동전과 각각의 가치 1,2,5가 주어졌을 때이 세 가지 종류의 동전으로 10을 만들 수 있는 가지수를 구하는 것이다.  1원 10개1원 8개 + 2원 1개1원 6개 + 2원 2개1원 4개 + 2원 3개1원 2개 + 2원 4개2원 5개1원 5개 + 5원 1개1원 3개 + 2원 2개 + 5원 1개1원 1개 + 2원 3개 + 5원 1개5원 2개쉽게 하나하나 구해보면 위와 같은 총 10가지의 경우의 수가 나오게 될 것이다. 이제 이 문제를 동적계획법(DP)로 풀이해보자.우선, 동전의 가치를 저장할 정수형 배열을..

https://www.acmicpc.net/problem/11049 해당 문제는 이전에 풀이했던 동적계획법 문제와 유사하되, 행렬 곱셈의 최솟값을 찾는 문제이다.이 문제는 행렬 곱셈의 최소 연산 횟수를 구하기 위해 DP를 사용해야 한다. 머릿속에서 개념이 정확히 안 잡힌 탓인지 DP는 볼 때마다 헷갈리고 모르겠다...나만 그러나..나만 그러겠지  문제 분석 1. 주어진 행렬들은 순서를 바꿀 수 없기 때문에, 순서를 유지하되 곱하는 방식만 고려해야 한다.2. DP 배열을 정의하여 최소 연산 횟수를 계산해 나간다. DP 접근 방식(1) DP 배열 정의 : dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱하는 최소 연산 횟수를 저장한다.(2) 구간 나누기 : 이 문제의 핵심은 구간을 어떻게 나누느냐이다. ..

https://www.acmicpc.net/problem/11066 해당 문제는 백준 "동적계획법2" 단계의 문제이다.DP 알고리즘 이해를 위해 간략한 설명과 함께 문제를 풀이해보겠다. 1. 동적 계획법(Dynamic Programming, DP): 큰 문제를 작은 하위 문제로 나누어 각 문제의 결과를 저장하고, 재사용해 효율적으로 해결하는 알고리즘 기법이다.DP를 사용하면 중복 계산을 피할 수 있어 반복적인 구조가 있는 문제를 더 빠르게 풀 수 있다. 문제의 핵심파일을 합치려면 인접한 두 파일을 하나로 합쳐야 하고, 이때 두 파일 크기의 합이 비용이 된다.이렇게 파일을 하나로 합칠 때 최소 비용을 구하려면 파일을 합치는 순서를 잘 정해야 할 것이다.예를 들어, 작은 파일들끼리 먼저 합치는 것이 비용을 ..

https://www.acmicpc.net/problem/12015   이분 탐색의 핵심은 *배열을 반씩 쪼개가며 찾기*이다.그래서 배열 내에 특정 타겟값이 들어올 때, 왼쪽과 오른쪽은 이 타겟이 들어갈 위치를 찾기 위한 탐색 범위를 의미한다.​public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 수열의 크기 입력 int N = Integer.parseInt(br.readLine()); int[] arr = new int[N]; // 수열 ..