후라이

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/11286  위 문제는 "우선순위 큐" 알고리즘으로 힙 자료구조를 구현한다.우선순위 큐 문제의 최대힙, 최소힙을 풀이하였다면 이 문제도 어렵지 않게 해결할 수 있을 것이다.(근데 난 바보같이 해결했었음) Java에서는 PriorityQueue, 즉 우선순위 큐 클래스를 지원하기 때문에 이를 사용하겠다.java.util 패키지 내의 우선순위 큐는 내부적으로 최소 힙(min-heap)을 사용해 자동으로 "오름차순" 정렬된다.그래서 최대힙의 경우 우선순위 큐를 선언하면서PriorityQueue q = new PriorityQueue; 위와 같이 reverse 정렬을 위한 컬렉션을 사용해서 초기화하면 됐었다. 해당 문제에서는 "절댓값 비교"이다. 즉, P..