알고리즘/동적계획법 검색 결과

해당 글 9건

동적계획법의 기초

동적 계획법이 왜 쓰이는지에 대해 궁금한 사람들을 위해 작성합니다. 동적 계획법이란, 이미 계산돼있는 값을 추후에 다시 계산하지 않고 가져다쓰기 위함입니다. 답을 재활용한다고 생각하시면 편합니다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 팩토리얼을 이용한 동적 계획법은, 둘다 시간 복잡도가 log(N) 이기 때문에 적합하지 않습니다. 조금 더 자세한 예를 위해 피보나치 수열 문제를 가져왔습니다. https://www.acmicpc.net/problem/2747 백준 2747번 피보나치 수 위와 같은 방식은 설명을 위한 재귀지, 일반적으로 사용하는 방식은 아닙니다. 시간 단위는 millisecond 입니..
알고리즘/동적계획법 2019. 8. 31. 12:58

[백준] 2156번 포도주 시식

이 문제도 진짜 어려웠다. 계단 오르기 처럼 하면 될 줄알았는데, 예상외로 변수가 많았다. 일단 잔이 1개 있다면, 그 1잔이 바로 최댓값이다. dp[1] = arr[1]잔이 2개있다면 2개를 마시는게 최댓값이다. dp[2] = arr[1] + arr[2]잔이 3개있다면? 여기서부터 문제인데 바로 연속으로 3잔은 마실 수 없는것이다.이제 점화식을 풀어보자 1) N번째로 마시는 포도주를 안마시겠다면?N번째 포도주가 양이 적어 건너뛰는게 나을 수도있다.이럴땐 dp[N] = dp[N-1] (N번째를 마시지 않았으므로) 2) N번째로 마시는 포도주가 1번 연속이라면?1번 연속이다라는건 앞의 포도주를 건너뛰고 처음으로 마셨다는 뜻이다그럼 n-1번째는 절대 마시면 안된다. 대신 n-2번째는 마시든 말든 상관없다.이..
알고리즘/동적계획법 2019. 1. 29. 01:33

[백준] 1912번 연속합

사실 이걸 올려야하나 말아야하나 고민 많이했는데.. 구하는 방법이라도 알 수 있으니 그냥 올렸다.dp보다는 변수2개로 둬서 구했는데.. dp로 구해도 되긴 된다.. 원리는now와 max를 두고arr[2]번째부터 now에 계속 더해주는 것이다. (2번째부터 도는 이유는 첫번째는 무조건 자기 자신이 최대값이기 때문)그리고 더해준 now 와 max를 비교해 둘 중 더 큰값을 MAX 값으로 두면 된다.그리고 now가 더해져 가면서 만약 0보다 작아진다면? 그땐 now를 0으로 (초기화) 시켜주면 된다. 왜냐면 now가 -가 된다면 최대값이 될 수 없다.예외가 있다면 음수들만 arr에 들어온다는 것인데그런 경우엔 arr 중에서 가장 작은 값이 최대 값이다.예를 들어 arr에 5개의 숫자가 들어있고 -1,-2,-3..
알고리즘/동적계획법 2019. 1. 26. 03:58

[백준] 1932번 정수 삼각형

역시나 점화식을 짜놓고, 오류 고친다고 오히려 시간을 더 사용한 문제다...일단 점화식을 짜보자 경로는 무조껀 왼쪽 대각선 혹은 오른쪽 대각선이다. 그렇담 7에서 나가는 3 과 8을 경로로 잡는다고 하면, 7->3(10), 7->8(15) 이다.가운데의 1에 갈 수 있는 방법은 7->3->1 또는 7->8->1 그러나 7->8->1 이 더 크기 때문에 7->3->1 은 무시한다.또한 또하나의 법칙이 있는데, 좌측 제일 하단의 4와 우측 제일 하단의 5가 보이는가?저 길까지 가는 방법은 무조건 첫번째 배열에서 좌측 대각선으로 가거나, 우측 대각선으로 가는 방법밖엔 없다.예) 7에서부터 시작해서 좌측 하단의 4까지 거리를 만드는 방법은7->3->8->2->4 순으로 가는 방법밖엔 없다.우측 또한 마찬가지다...
알고리즘/동적계획법 2019. 1. 26. 01:38

[백준] 1149번 RGB거리

이것도 하나하나 탐색해가며 찾으면 될 것같다. 저번 타일링 문제 처럼 말이다.일단 점화식부터 세워야 하는데 기본적으로 모든 값중 최솟값을 찾는 점화식부터 세워보자N이 0일땐, 아무것도 채워넣을 수 없다. 그러므로 dp[0]은 0,일단 예제에서 N 이 1일땐, 0번째는 26 1번째는 40 2번째는 83이다. 이중 최솟값은 26이니 dp[1]는 26,N이 2일땐 0번째는 49 1번째는 60 2번째는 57이다. 이중 최솟값은 49이니 dp[2]는 dp[1]까지 합친 값인 75그럼 점화식은 결국 dp[i] = dp[i-1] + arr[i]; 이다. (arr[i] 는 현재 N값중 가장 작은 값이다.) 이제 제약조건인 이웃이 이미 칠한 색깔은 칠 할 수 없다 를 풀어보자일단 arr와 dp를 모두 2차원 배열로 설정..
알고리즘/동적계획법 2019. 1. 25. 01:26

[백준] 11727번 2 x n 타일링 2

https://openmynotepad.tistory.com/6 저번 11726번 문제에서 2x2 타일이 하나 더 생겼다.저번 문제랑 바뀔 점이 없는것이, 이미 2x1 타일과 1x2 타일로 채운 방법을 짜봤고,2x1 타일은 2x2과 같은 N을 가지므로, 점화식은 N = (N-1) + (N-2) + (N-2) 가 된다. ( 1x2 타일로 시작해서 채우는 방법 + 2x1 타일로 시작해서 채우는 방법 + 2x2 타일로 시작해서 채우는 방법) 2xn타일링 소스에서 full(n-2)를 한번 더 더해주면 된다.
알고리즘/동적계획법 2019. 1. 24. 04:02

[백준] 11726번 2 x n 타일링

누군가에겐 쉽겠지만 이제 공부하는 나한테는 생각하는데 30분 정도 걸린 문제다..만약 N이 1이라면 1x2 타일 하나밖에 쓸수 없으니 1이다.N이 2라면 ? 1x2 타일 2개를 쓰는 방법 하나, 2x1 타일 1개를 쓰는 방법 하나. 2이다. 결국엔 N의 크기에 따라 뭘로 채울꺼냐는건데, 1x2로 채우는 방법, 2x1로 채우는 방법을 다 구해보면 될 것 같다.(N-1) + (N-2) = 방법N이 예를 들어 3이라면, 1x2 타일로 하나를 채우고(N-1)2로 들어간다, 2에선 또 1x2 타일로 하나를 채우고(N-1)1로 들어간다. 1에선 1x2 타일 하나밖에 채울수 없으니 방법 1개 완료2로 돌아온다. 1x2 타일로 채우는 방법은 다 해봤으니 2x1 타일로 채우는 방법으로 돌아간다.현재 가로 공간은 2가 남..
알고리즘/동적계획법 2019. 1. 24. 03:05

[백준] 2579번 계단 오르기

벌써부터 귀찮다. 점화식부터 세워보자 을 예시로 들고 3번째 계단까지 올라가며, 최대 점수를 구한다고 하면 ( N = 3 )두가지 방법이 있다1 번째 계단을 밟고 3 번째 계단을 밟기 ( 10 + 15 )2 번째 계단을 밟고 3 번째 계단을 밟기 ( 20 + 15 )둘 중 더 높은 점수를 구해야 하니 3번째 계단의 최대 점수는 354 번째 계단까지 올라가며, 최대 점수를 구한다고 하면 ( N = 4 )1 번째 계단을 밟고, 2 번째 계단을 밟고, 4 번째 계단을 밟기 ( 10 + 20 + 25 )1 번째 계단을 밟고, 3 번째 계단을 밟고, 4 번째 계단을 밟기 ( 10 + 15 + 25 )2 번째 계단을 밟고, 4 번째 계단을 밟기 ( 20 + 25 )4 번째 계단의 최대 점수는 55 결국 N번째 계단..
알고리즘/동적계획법 2019. 1. 24. 01:37