본문 바로가기

분류 전체보기162

DP 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. Dynamic Programming이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요는 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. 메모이제이션 기법을 사용한다. 그것이 핵심이다. Dynamic Programming 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 저장해 두어야 한다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복이 일어나는 경우. 같은 문제는 구할 때마다 정답.. 2023. 11. 22.
Greedy와 DP 알고리즘에 대한 고찰 문제를 풀면서, 깨닫는게 많아지면서 변화할 생각을 적어보고자 한다. 결국 DP의 미학은 계산한걸 또 계산하지 않겠다는 것이다. 그래서 메모이제이션이 필요한 것이다. 점화식을 구하는 것이 핵심인데, 점화식이라는 어려운 말보다 다음 껀 어떻게 구할래? 이렇게 생각하면 편할것이다. DP의 경우 N번째가 모두 정답이다. 곧, 정답만 저장된다는 것도 그 정답을 이용해 다음 정답을 이끌어내야하는 과제가 있다. 실버문제의 경우 초기식을 세우고 dp[0] 처럼 하드코딩으로 내가 정의할 수 있는 경우가 많다. 그 후, 문제를 풀때 dp[1], dp[2]는 어떻게 될지 나열하다보면, 결국 문제는 풀리기 마련이다. 골드문제의 경우 dp의 자료구조를 어떻게 정할지에 대해 고민스러웠던 경험이 있었다. dp자체에 어떤 정답을 담.. 2023. 11. 22.
주짓수 #15724 c++ 풀이 https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 전에 이와 비슷한 누적합 문제를 풀었기에 갈피를 잡기 쉬웠다 도형적인 접근이 필요하다. 공식처럼 누적합의 성질을 이용하면 된다. #include using namespace std; int N, M; //영토의 크기 N >> M; for (int i = 1; i population[i][j]; } } dp[1][1] = population[1][1]; dp[1][2] = dp[1][1] + popula.. 2023. 11. 20.
포도주 시식 #2156 c++ 풀이 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 계단 오르기 문제와 매우매우 유사하나, 마지막 계단을 밟지 않아도 되고 꼭 계단을 두칸씩 밟을 필요도 없는 계단오르기라고 생각하면 될 것 같다. #include using namespace std; int n; int arr[10001]; int dp[10001]; int main() { cin >> n; for (int i = 1; i > arr[i]; } //dp[0] = 0; dp[1] = a.. 2023. 11. 15.

티스토리툴바