Dynamic Programming
왜 만듬?
- Brute Force, DFS, BFS을 이용해서 많은 경우의 수를 전부 따져보는데 시간이 너무 많이 걸리는 경우 즉, 다 따져보기에는 경우의 수가 너무 많아 속도가 느려지는 경우 수행시간을 단축하고자 만들어졌다.
- 다르게 보자면 큰 문제를 작거나 간단한 여러개의 문제로 나눠서 푸는 방법
- 작은 부분을 해결한 후 , 그 해들을 이용해서 큰 문제들을 해결, 최종적으로 원래 주어진 입력의 문제를해결하는 알고리즘 설계 기법
분할정복과 차이점
- 동적 분할
- 부분 문제가 중복되어 상위 문제 해결시 재활용됨
- memoization 기법 사용
- 분할정복
- 부분 문제 중복 안됨
- memoization 사용 안함
메모이제이션의 개념
- Overlapping Subproblems( 중복 부분 문제 )를 해결하기 위한 방법
- 재귀적으로 구현하면 이전 연산을 다시 해야하는 문제가 있다.
- 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행속도를 빠르게 해주는 기법
DP에서 사용되는 메모이제이션
- 작은 문제들의 연산결과를 메모리에 저장한다.
- 큰 문제들에 작은 문제의 연산이 필요한 경우, 다시 연산하는 것 대신에 메모리에 저장된 연산결과를 가져다 사용한다.
도움이 된 문제
- 백준 : 가장 긴 증가하는 부분 수열
- 이전까지는 자료구조 하나당 한 연산에 대한 결과를 쌓아가는 것으로 생각하고 있었다.
- 여기서는 배열 하나에 모든 부분 수열의 길이를 각자 저장하고 있어서 굉장히 새로운 느낌을 받았다.
- 그것도 한 부분 수열 기준 이전 연산들을 저장하고 있는 거니까 확실히 dp적이다라고
- 백준 : 01타일
- 그냥 푼다면 간단하게 피보나치 수열이 된다.
- 근데 왜? 피보나치가 되는지 그 이유를 이해하면 문제가 다르게 보인다.
- 이전 스텝들에 00 ,1 만 추가할 수 있기 때문에 2칸을 잡아먹는 00으로 인한 n-2 스탭 , 1로 인한 n-1스탭 을 더하기 때문에 피보나치 수열이 된다.
문제 구분하는 법
- 사실 특정 유현에만 국한되진 않는다.
- 다양한 유형의 문제 최적화 할 때 고려될 수 있는 알고리즘이다.
- 그치만 대충 예상하는 법
- DFS, BFS로 견적이 보이는데, 경우의 수가 겁나 많은 경우
- 경우의 수 확인하는 법 : 패턴이 보일 때까지 손으로 계산 반복하기
- 정수 삼각형 문제의 경우의 수
- 1줄 : 1개 , 2줄 : 2개 , 3줄 : 4개, 4줄 : 8개 ...... n줄 : 2^(n-1)개
- 이거 500줄이면 2^499 == 1.63*10^150 (겁나 많음)
- 경우의 수들간 중복적인 연산이 많은 경우
- 딱 봐도 최댓값이 안되는 경로도 연산을 반복하고 있는 경우
- 정수삼각형 문제에서 최댓값 빼고 나머지는 다 버린 이유
- 많이 풀어보고 감각 키우기
- 문제 오래 잡지 말고 30분 해보고 안되면 답 보기
- DFS, BFS로 견적이 보이는데, 경우의 수가 겁나 많은 경우
팁
- 축소적으로 생각하기
- k+1 번째의 답을 찾기 위해 그전의 어떤 연산을 가져와서 사용해야 할까
- 정보 저장 방법 생각하기
- 현재 단계까지 연산의 답에 대해서
- 연산을 또 하지 않으려면 어떤 정보를 남겨야 하지?
- 어떤 형태로 저장해야 후에 사용하기 편할까?
- brute force에서 출발하기
- 먼저 무식하게 한 결과에서 시작해 어덯게 줄일지 생각하는 순서로 푸는 것도 좋은 방법이다.
- 처음에 방법을 생각하면 보통 재귀로적으로 정의하게 된다.
- 그 재귀 부분을 어떻게 저장할지 고민하기
- memoization의 구상은 초기값을 가정할 수 있는 위치에서 시작
예시
- lcs 문제
- 위 그림처럼 재귀적으로 구현하면 쉬운데 n이 증가하면 연산이 중복해서 필요한 경우가 기하 급수적으로 많아져 수행시간이 증가한다.
- 시간 복잡도 : O(2ⁿ) , exponential한 시간 복잡도
- => memoization이 필요한 이유
- 위 그림은 top-down방식이지만, 역순 즉 bottom-up으로 풀면
- 맨 아래층 연산을 하고 memoization을 한다면 위층에서는 최대값을 고르기만 하면 된다.
참고자료
https://www.youtube.com/watch?v=0bqfTzpWySY
https://www.youtube.com/watch?v=z8KVLz9BFIo&t=668s
Dynamic Programming
왜 만듬?
- Brute Force, DFS, BFS을 이용해서 많은 경우의 수를 전부 따져보는데 시간이 너무 많이 걸리는 경우 즉, 다 따져보기에는 경우의 수가 너무 많아 속도가 느려지는 경우 수행시간을 단축하고자 만들어졌다.
- 다르게 보자면 큰 문제를 작거나 간단한 여러개의 문제로 나눠서 푸는 방법
- 작은 부분을 해결한 후 , 그 해들을 이용해서 큰 문제들을 해결, 최종적으로 원래 주어진 입력의 문제를해결하는 알고리즘 설계 기법
분할정복과 차이점
- 동적 분할
- 부분 문제가 중복되어 상위 문제 해결시 재활용됨
- memoization 기법 사용
- 분할정복
- 부분 문제 중복 안됨
- memoization 사용 안함
메모이제이션의 개념
- Overlapping Subproblems( 중복 부분 문제 )를 해결하기 위한 방법
- 재귀적으로 구현하면 이전 연산을 다시 해야하는 문제가 있다.
- 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행속도를 빠르게 해주는 기법
DP에서 사용되는 메모이제이션
- 작은 문제들의 연산결과를 메모리에 저장한다.
- 큰 문제들에 작은 문제의 연산이 필요한 경우, 다시 연산하는 것 대신에 메모리에 저장된 연산결과를 가져다 사용한다.
도움이 된 문제
- 백준 : 가장 긴 증가하는 부분 수열
- 이전까지는 자료구조 하나당 한 연산에 대한 결과를 쌓아가는 것으로 생각하고 있었다.
- 여기서는 배열 하나에 모든 부분 수열의 길이를 각자 저장하고 있어서 굉장히 새로운 느낌을 받았다.
- 그것도 한 부분 수열 기준 이전 연산들을 저장하고 있는 거니까 확실히 dp적이다라고
- 백준 : 01타일
- 그냥 푼다면 간단하게 피보나치 수열이 된다.
- 근데 왜? 피보나치가 되는지 그 이유를 이해하면 문제가 다르게 보인다.
- 이전 스텝들에 00 ,1 만 추가할 수 있기 때문에 2칸을 잡아먹는 00으로 인한 n-2 스탭 , 1로 인한 n-1스탭 을 더하기 때문에 피보나치 수열이 된다.
문제 구분하는 법
- 사실 특정 유현에만 국한되진 않는다.
- 다양한 유형의 문제 최적화 할 때 고려될 수 있는 알고리즘이다.
- 그치만 대충 예상하는 법
- DFS, BFS로 견적이 보이는데, 경우의 수가 겁나 많은 경우
- 경우의 수 확인하는 법 : 패턴이 보일 때까지 손으로 계산 반복하기
- 정수 삼각형 문제의 경우의 수
- 1줄 : 1개 , 2줄 : 2개 , 3줄 : 4개, 4줄 : 8개 ...... n줄 : 2^(n-1)개
- 이거 500줄이면 2^499 == 1.63*10^150 (겁나 많음)
- 경우의 수들간 중복적인 연산이 많은 경우
- 딱 봐도 최댓값이 안되는 경로도 연산을 반복하고 있는 경우
- 정수삼각형 문제에서 최댓값 빼고 나머지는 다 버린 이유
- 많이 풀어보고 감각 키우기
- 문제 오래 잡지 말고 30분 해보고 안되면 답 보기
- DFS, BFS로 견적이 보이는데, 경우의 수가 겁나 많은 경우
팁
- 축소적으로 생각하기
- k+1 번째의 답을 찾기 위해 그전의 어떤 연산을 가져와서 사용해야 할까
- 정보 저장 방법 생각하기
- 현재 단계까지 연산의 답에 대해서
- 연산을 또 하지 않으려면 어떤 정보를 남겨야 하지?
- 어떤 형태로 저장해야 후에 사용하기 편할까?
- brute force에서 출발하기
- 먼저 무식하게 한 결과에서 시작해 어덯게 줄일지 생각하는 순서로 푸는 것도 좋은 방법이다.
- 처음에 방법을 생각하면 보통 재귀로적으로 정의하게 된다.
- 그 재귀 부분을 어떻게 저장할지 고민하기
- memoization의 구상은 초기값을 가정할 수 있는 위치에서 시작
예시
- lcs 문제
- 위 그림처럼 재귀적으로 구현하면 쉬운데 n이 증가하면 연산이 중복해서 필요한 경우가 기하 급수적으로 많아져 수행시간이 증가한다.
- 시간 복잡도 : O(2ⁿ) , exponential한 시간 복잡도
- => memoization이 필요한 이유
- 위 그림은 top-down방식이지만, 역순 즉 bottom-up으로 풀면
- 맨 아래층 연산을 하고 memoization을 한다면 위층에서는 최대값을 고르기만 하면 된다.
