알고리즘||코딩테스트/DP

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 사용한 알고리즘: DP 풀이전략 펠린드롬수는 쉽게 말해서 앞으로 읽으나 뒤로 읽으나 같은 수를 뜻한다. 문제 해결 접근 방식으로 질문이 주어질 때마다 해당 수가 펠린드롬 수인지 파악하려고 한다면 최악의 경우 1,000,000번의 펠린드롬 수 판단 연산을 수행해야 한다. 수열의 크기가 최대 2000까지 가능하므로 최악의 경우 2000 * 1,000,000 = 2,000,000,000(20억)번 연산이 필요하다. 이는 JAVA가 초당 1억..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 사용한 알고리즘 : DP 풀이전략 1. 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이 (실패, 메모리초과) 처음엔 우선순위 큐를 이용한 다익스트라 알고리즘을 사용하여 문제를 풀이했다. 그런데 메모리 초과 문제가 발생했다. 문제에서 주어진 메모리 제한은 128MB인데, 내가 선언한 클래스를 원소로 가지는 우선순위 큐는 노드 하나 당 8 byte를 차지했다. 그런데..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 사용한 알고리즘 : DP 풀이전략 위의 문제에서 주어진 입력을 표로 나타내면 아래와 같다. 이중배열 d[i][j]는 i와 i번 째 이전에 입력된 동전들로, 수 j를 만들 수 있는 경우의 수를 저장한다. d[i][0]은 공집합인 상태로, 공집합 또한 하나의 경우의 수를 가지므로 1을 가진다. d[0][j]은 d[i][j]의 규칙성을 찾아낸 식에서 d[i-1][j]의 i-1에서 IndexOutOf..