알고리즘/다이나믹프로그래밍(Dynamic Programming)
-
[백준 2156] - [다이나믹프로그래밍] - 포도주 시식 (JAVA)알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 12. 27. 13:33
문제 링크 : https://www.acmicpc.net/problem/2156 이 문제는 다이나믹 프로그래밍 (DP) 으로 접근 하면 된다. 다이나믹 프로그래밍에서 제일 중요한건 점화식이다. 같은 규칙으로 계산이 되고 그 규칙을 찾고 찾은 규칙에서 점화식을 구하면 문제는 아주 쉽게 풀린다. 모든 DP 문제는 점화식 구하는게 일이다. 이 문제에서 제공하는 조건은 두가지가 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 일단 첫번째 조건은 한 잔에 들어 있는 포도주를 찔끔찔끔 마실수 없다는걸 말하는 거고 두번째 조건은 연속으로 3잔을 마실수 없다는걸 말한다. 이 두번째 조건이 점화식을 구..
-
[백준-1912]-[다이나믹프로그래밍] - 연속합알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 11. 14:29
문제경로 : https://www.acmicpc.net/problem/1912 이문제는 굉장이 간단하게 접근 할 수 있다. 제공된 예제를 바탕으로 문제를 풀어보자. 10 10 -4 3 1 5 6 -35 12 21 -1 총 10개의 정수가 제공 되고 연속된 구간의 합 중에서 제일 큰 값이 무엇인지 출력해주면 된다.출력은 33이 출력이 돼야 한다. 이문제를 간단하기 풀기 위해선 배열의 크기를 입력받은 사이즈 보다 한칸 더 크게 생성하면 쉽고 짧게 풀 수 있다. 첫번째 입력을 배열의 인덱스 0에 저장하지 말고 1에 저장하면 된다. 이문제를 풀기위해 필요한 변수는 구간합의 최대값을 저장하는 max 라는 변수와 입력받은 값들을 저장할 long 타입의 일차원 배열만 있으면 풀 수 있다. 1234567 public ..
-
[백준-1932]-[다이나믹프로그래밍] - 정수 삼각형알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 15:45
문제링크 : https://www.acmicpc.net/problem/1932 이문제는 백준-1149번 RGB 구하는 문제와 비슷한 형식을 가진다. 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 한칸 한칸 내려가면서 본인의 최대값을 지니고 있고 좌우 대각선 위의 값들을 비교해서 그중 큰 값에 자신의 값을 더한게 본인의 최대값이다. 순서대로 가보면 첫번째 값이 7 이 들어오고 7의 최대값은 7이다. 두번째 줄에 3 8 이 들어오고 각각의 최대 값을 구하면3 의 왼쪽 위 03 의 오른쪽 위 7 8 의 왼쪽 위 78 의 오른쪽 위 0 3의 최대값은 108의 최대값은 15로 아래와 같은 삼각형이 나온다. 710 15 세번째 줄은 8, 1, 0 이 입력 됐고 같은 방법으로 계산하면 정수 피라미드는 아래..
-
[백준-11726]-[다이나믹프로그래밍] - 2 x N 타일링알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 14:58
문제링크 : https://www.acmicpc.net/problem/11726 이 문제는 문제만 그림이지 1과 2로 입력받은 수 N을 만드는 문제이다. 이런식으로 길이 2 * 5의 타일에 2 * 1 타일 로 길이 1을 1 * 2 타일 두개로 길이 2를 채울 수 있다. 그럼 1,2로 5를 만드는 경우의 수를 구하면 된다. 5를 1 또는 2로 만들 수 있는 경우의 수는1 + 1 + 1 + 1 + 11 + 1 + 1 + 21 + 1 + 2 + 11 + 2 + 1 + 11 + 2 + 22 + 1 + 22 + 2 + 1여기서 끝이 1로 끝나는 것들 2로 끝나는 것들을 모아보면- 1로 끝나는 것들 1 + 1 + 1 + 1 + 11 + 1 + 2 + 11 + 2 + 1 + 12 + 2 + 1끝자리 1을 제외하고 나..
-
[백준-2193]-[다이나믹프로그래밍] - 이친수알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 14:11
문제링크 : https://www.acmicpc.net/problem/2193 이 문제는 흠.. 좀 여기에 정리해 가면서 풀어봐야겠다. 머리가 딸리니 연습장에 그려가면서 하기엔 악필이라 영 내가 알아보기가 힘들다 어느정도 풀이법이 보인다. 하나 하나 정리해가면서 해봐야지 자 친절하게 문제에서 이친수가 무엇인지 설명을 해주었다. 이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.위의 두 조건은 잊지 말아야지. 그리고 N 자리 이친수가 몇개 존재하는지 알아봐 달라고 한다. 별걸 다 알고 싶어하네 또다시 빡친다.그래도 뭐 풀어야지 일단 자리수 별로 이친수를 구해보면서 규칙을 찾아봐야겠다. 1 자리는 1 2 자리는 1 03 자리는 1 0 ..
-
[백준-1003]-[다이나믹프로그래밍] - 피보나치 수열알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 13:06
문제링크 : https://www.acmicpc.net/problem/1003 이문제는 생각보다 쉽게 방법을 찾았다. 다행이다. 문제에서 친절하게 C++ 피보나치 DP 소스를 제공해줬다. 하지만 이문제를 푸는데 대략적인 힌트만 줄 뿐 저 소스를 이용할 필요는 없다. 숫자 5까지의 피보나치를 계산해보면서 이 문제를 어떻게 풀어가야할지 방법을 파악해보자. 1234567891011int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}Colored by Color Scriptercs 숫자 0..
-
[백준-1149]-[다이나믹프로그래밍] - RGB 거리알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 12:28
문제링크 : https://www.acmicpc.net/problem/1149 이문제를 이해하는데 오래걸렸지만 한번 이 문제를 이해하니 쉽게 이해하지 못한 내 자신이 한심해졌다. 문제의 설명을 보게 되면 3개의 행에 입력받는 N개의 열이 존재하고 이웃끼리는 같은 색을 할 수 없다고 한다. 이웃의 조건은 i번째 기준 i-1, i+1 이 기준이라하니 아래 위로는 같은 색을 선택 할수 없다고 하는조건이다. 그냥 같은 색으로 칠하면 안되나 빡친다. R G B 1 번째 26 40 83 2 번째 49 60 57 3번째 13 89 99 이문제를 풀기 위해서는 R,G,B의 색상 최소 값을 가지고 있는 배열이 필요하다. (int[] price index의 0 = R, 1 = G, 2 = B 를 나타낸다.)문제를 푸는 과..
-
[백준-2579]-[다이나믹프로그래밍] - 계단 오르기알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 8. 17:21
문제 경로 : https://www.acmicpc.net/problem/2579 이문제 같은 경우에는 점화식을 찾는데 굉장히 오래 걸렸다. 머리가 별로 안좋은가 보다. 굳이 점수까지 세면서 계단을 올라야 하나 좌절을 하던중 주변의 힌트와 오랜 시간의 고뇌덕에 찾았다 방법을 문제에서 제공하는 조건은 이렇다.연속된 계단 두개는 밟을 수 있고 세개는 밟을 수 없다. 한계단을 오른 뒤 다음다음 계단을 바로 밟을 수 있다. 마지막 계단은 무조건 밟아야 한다. O O X O 이런식이나 O X O O 또는 O X O X 이런식으로 계단을 밟을 수 있다.마지막 계단은 무조건 밟아야 한다 라고 하니 아래와 같이 경우의 수 두가지가 보인다. 마지막 전 계단을 밟은 경우 이 경우는 마지막 전전 계단은 밟지 않았다는거고 전전..