알고리즘 문제/DP
-
백준 2133 타일채우기알고리즘 문제/DP 2019. 9. 18. 00:03
백준 2133 타일채우기 해설 흥미로운 문제이다. 정답을 미리 알거나 스포일링 당하는건 괴롭지만, ... 생각해나갈 때는 알쏭달쏭한 즐거운 문제였을 것이다.(구현문제보단 재밌는듯) 가로 길이 2 인 것을 만드는 경우의 수는 3가지이다. ( ||_ ),( _|| ), ( _ _ _ )이다. 임의의 길이 i를 만드는 데에는 i-2 길이를 만드는 경우의 수에 3가지 경우의 수를 조합하는 것이므로, f(i) = f(i-2)*2 이다. 그리고, 길이 4 이상부터 다음과 같은 형태를 만들 수 있다. 이러한 형태는 4, 6, 8, ... i 길이 만큼 만들 수 있고, 뒤집은 형태도 있기 때문에 각 길이마다 2가지의 경우의 수가 있다. 이를 종합하면 i를 만드는 경우의 수는 다음과 같다. f(i) = f(i-2)*2 ..
-
백준 14494 다이나믹이 뭐에요?알고리즘 문제/DP 2019. 9. 17. 23:58
백준 14494 다이나믹이 뭐에요? 해설 n*n의 2차원 공간에서 오른쪽, 아래쪽, 우아래 대각 세 방법만 이용하여 이동한다고 하자. 이때 임의의 점 (x, y)에 도달 할 수 있는 경우의 수 f(x, y)는 f(x-1,y) + f(x, y-1) + f(x-1, y-1)이다. d배열을 1칸 크게 잡는다면 특별히 배열 range-exception 처리를 할 필요 없이 온전하게 연산에만 집중할 수 있다. #include #define MOD ((int)1e9+7) using namespace std; int d[(int)1e3+1][(int)1e3+1]; int main() { int n, m; cin >> n >> m; d[0][0] = 1; for (int i=1; i
-
백준 1463 1로 만들기알고리즘 문제/DP 2019. 9. 17. 23:32
백준 1463 1로 만들기 해설 Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS) 하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다. n/2 에서 1까지 가는 최단경로 길이 + 1 n/3 에서 1까지 가는 최단경로 길이 +1 n-1 에서 1까지 가는 최단경로 길이 + 1 아래는 memoization을 이용하여 문제를 해결한 소스코드이다. ````C++ #include #include #include using namespace std; int d[(int)1e6+1]; int go(int cur) { if ( cur = 0) return d[cur]; d[cur] = 1e9; if ( cur%2 ..
-
백준 15483 최소편집알고리즘 문제/DP 2018. 12. 30. 01:27
문제보러가기https://www.acmicpc.net/problem/15483 문제 정의문자열 A와 B가 있다.A를 어떠한 동작을 통해 B와 같게 만들려고 한다. 이 때 최소한의 동작 횟수를 구하시오. 각 순간마다 세가지의 선택을 할 수 있다.- 1 삽입- 2 삭제- 3 교체 이 문제를 어떻게 해결할 수 있을까? 이 문제의 접근법은 모든 가능성을 탐색하는 것이다.재귀를 이용하여 두 문자열의 다름 정도의 비교를 할 수 있다. String S1 의 i 인덱스, S2 의 j 인덱스를 다름을 비교하여, 만약 같다면 다음 비교 스테이지인 S1의 i+1, S2의 j+1로 넘어간다. 만약 다르다면, S1에게 3가지 동작을 수행할 수 있다.삭제, 더하기, 교체 이다.만약 삭제하는 경우 다음 비교 스테이지인 S1의 i+..
-
백준 15991 1, 2, 3 더하기 - 6알고리즘 문제/DP 2018. 10. 23. 12:32
백준 15991 1, 2, 3 더하기 - 6문제 보러가기 https://www.acmicpc.net/problem/15991 문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 합은 대칭을 이루어야 한다.1+1+1+11+2+12+2정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 경우의 수 문제이다. 이 문제를 푸는데 무려 2달 이나 걸렸다. 2달 전 처음 접했을 때 엄청 푸려고 노력했다. 한 4일 정도 노력을 했는데 안풀렸다. 특수한 스킬이 필요한 것이 아니라 이해력 문제였는데 못 풀었기 때문에, 그리고 또 이 문제 시리즈를 1, 2, 3, 4, 5, ... 순서대로 풀려..
-
백준1126 같은탑알고리즘 문제/DP 2017. 12. 5. 02:34
난이도 6/10DP문제, 특히 난이도가 높다고 생각한다. 특히 탑 구현? 부분 즉, dp 2차원을 어떤 정보로 memoization 할것인가가 크게 걸렸다. 나는 온전하게 문제를 풀지 못하였지만, 기억을 잃지 않으려고 포스트를 써본다. 각기 높이가 다른 블록이 여러개 주어지는데, 이것들로 두탑을 만드는데 두 탑의 높이가 같게 만든다.그런데 그것이 최대가 되는 지점을 생각해야한다. 최적화이다.인공지능이라는 어려운 주제를 구현하는 방법을 모르고,쉬운 방법을 원한다면 모든 경우의 수를 다 고려하는게 좋다, 그리고 가장 큰 특성치(두 탑의 높이가 같으며 최대 높이)인 지점을 찾는것.결국은 brute force와 그 지수복잡도를 해결하기 위한 subproblem의 만남이다. 즉 dp문제. 어떤 지점에서 subpr..
-
백준 9095 : 1, 2, 3 더하기알고리즘 문제/DP 2017. 10. 10. 00:18
백준 1, 2, 3 더하기본문보기https://www.acmicpc.net/problem/9095 이번 문제는 경우의 수 구하는 문제이다. 해당문제는 n중 for문으로도 풀 수 있고, 재귀를 이용한 dfs 탐색(트리탐색) 으로도 풀 수 있다. 하지만 또 dp풀듯이도 풀 수 있다. dp 풀듯이라는 뜻은 어쨋든 굉장히 큰 길이 또는 크기를 구하는 문제이지만 서도 낮은 숫자부터 차근차근 sub-answer들을 구해내서 귀납적으로 큰 값에 대한 답 real-answer를 구하는 것이다.이게 바로 sub-problem , overlapping 이라는 개념인데 나는 아직 이 개념에 익숙치 않아서 이 블로그를 포스팅 하는 이유이기도 하다. 이번문제에서 숫자는 어떻게 완성될까? 우선 이전 dp 문제들의 접근법을 확인해..