본문 바로가기

반응형

dp

(5)
[삼성 기출 문제] 백준 16235 나무 재테크 문제 링크 어떻게 풀까? 최적화를 조금 많이하다보니 문제를 살짝 극혐으로 풀었습니다. 저는 DP, 슬라이딩 윈도도 함께 사용했습니다.만약 슬라이딩 윈도를 잘 모르신다면 여기를 참고하세요 슬라이딩 윈도를 쓰는 이유! 이 문제를 잘 보시면 이전 년도의 나무들에 대한 정보는 전혀 필요가 없습니다.따라서, 현재 년도와 다음 년도에 쓰일 공간만 필요한 것 입니다. 그림에서 보듯이 이전 년도의 나무 개수 자료는 전혀 쓰지 않습니다. 따라서 위처럼, 현재 나무들의 정보를 토대로 다음 년도의 나무를 저장하기 위해선 딱 2개의 정보 배열이 필요합니다. 2개의 나무 배열을 가지고 있다고 하면, y년 이라고 했을때, [y%2^1] 나무 배열을 현재 배열로, [y%2] 배열을 내년 배열로 쓰면 됩니닷! 그리고! 나무들의 정보..
[삼성 기출 문제] 백준 14501 퇴사 문제 링크 클릭시 이동합니다. 어떻게 풀까? 현재가 X일이 지난 상태이고 일을 할 수 있는 상태라고 가정해봅시다!그럼, X일 에서의 의뢰를 수행할 수 있겠죠! 이 일을 할 때 벌어들인 금액이 가장 최댓값이 되기 위해서는 어떻게 해야할까요? 답은 간단합니다! X일 전까지 일했던 금액이 가장 많게 하면 되죠! 현재가 X일이라고 했을 때, X-1+T[X]일의 금액 값과, X-1일까지 마친 금액 + P[X] 값 중 큰 값을 X-1 + T[X]일의 벌이로 기록하는 것입니다!이렇게 하면, n일에 저장된 값을 바로 출력하면 되죠! 이를 위해, 간단한 DP점화식을 만들 수 있죠. 그리고, 인덱스 오류를 피하기 위해서 X +T[X]가 n을 넘어갈 때에는 무시하도록 합시다! 코드 12345678910111213141516..
[SW Expert Academy] 4335. 무인도 탈출 4335. [연습문제] 무인도 탈출 SW Expert Academy의 문제들은 저작권 때문에 무단 복제가 금지되어있기 때문에 링크로 대체하겠습니다.클릭시 이동합니다! 어떻게 풀까? 우선 직육면체의 특징에 대해서 살펴봅시다! 직육면체는 말 그대로 6개의 면을 가지고 있습니다.하지만, 생각해보면 그 특징은 가로, 세로, 높이의 세 가지 길이로 이루어져있죠! 즉, {가로, 세로}, {세로, 높이}, {높이, 가로}의 세 가지 방향으로 놓을 수 있다는 것을 알 수 있습니다!! 또한, 블록의 특성상 메모이제이션을 쓰면 굉장히 적절할 것 같다는 생각을 해볼 수 있습니다.20개의 블록이니까 비트로 나타내서 비트를 이용한 메모이제이션을 사용하면 될 것입니다! 어떤 비트가 주어지면, 값이 0 으로 세팅되어있는 블록들을 ..
[BOJ] 14925. 목장 건설하기 목장 건설하기클릭시 이동합니다.어떻게 풀까!? 이 문제는 DP 알고리즘 입니다! 정사각형이 어떻게 만들어지는지 알면 점화식을 통해 구할 수 있는 문제이죠! 3x3 에서 정사각형은 어떻게 만들어 질까요?? (i, j)에 3x3의 사각형을 만들 수 있는 경우를 살펴보겠습니다! 3x3 정사각형을 만들 수 있다면, (i, j-1) 에는 2x2의 정사각형을 만들 수 있습니다! 마찬가지로, (i-1, j)에도 2x2의 정사각형을 만들 수 있죠! 그리고! (i-1, j-1)에도 2x2 정사각형을 만들 수 있습니다! 반대로, (i-1, j-1)과 (i-1, j), (i, j-1)에 2x2 정사각형을 만들 수 있다면, (i, j)에는 3x3의 정사각형을 만들 수 있다는 것을 알 수 있습니다! 그럼, 다른 경우를 봅시다!..
[SW Expert Academy] 4701. 경시대회 매니저의 고민 4701. 경시대회 매니저의 고민 SW Expert Academy의 문제들은 저작권이 있기 때문에 링크로 대체합니다!클릭시 이동합니다!! 어떻게 풀까? 이 문제는 경우의 수를 구하는 문제입니다!전에 있던 경우의 수가 어떻게 해서 다음의 경우의 수에 영향을 줄지 잘 생각해서, 이를 점화식으로 표현하는 것이 중요합니다. 더 간단히 요약하면, DP라는 것이죠! 과연, 이전의 어떤 경우에서 DP를 구할 수 있을까요!? 자! 홈페이지의 테스트 케이스 1 번을 가지고 연구를 하겠습니다! 자! 이제 어떻게 답을 찾아가는지 생각해봅시다! 우선, 위와 같은 상황에서 디피를 만들면 이전에 뽑은 수들을 하나하나 다시 비교하면서 승점이 어떻게 되는지 확인하려면, 정렬을 하는것이 좋아보입니다.왜냐하면, 정렬을 한 상태라면 '이..

반응형