본문 바로가기

알고리즘/DP(Dynamic programming, 동적프로그래밍)

 (18)
백준(BOJ) 2407: 조합 https://www.acmicpc.net/problem/2407 기초문제로 BigInteger타입과 그 연산( dp[i][j]=dp[i-1][j-1].add(dp[i-1][j]); )방식에 대해 알아두기. BigInteger에 대하여https://coding-factory.tistory.com/604#google_vignette ==>> int는 메모리 크기는 4byte로 표현할 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이고 long은 메모리 크기는 8byte로 표현할 수 있는 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807입니다. 그 범위를 넘어서게 되면 모두 0으로 출력이 됩니다. 숫자의 범위가 저 범위를 넘을 경..
백준(BOJ) 12849: 본대 산책 https://www.acmicpc.net/problem/12849 매우 상징성이 강한 문제다. 내가 그동안 왜 안나오나... 하고 생각했던 그런문제다. 문제가 조건을 명확하게 주지 않은 면이 있는데, 출발점도 정보관이고 도착점도 정보관으로 놓고 푸는 문제다. 문제에서 묻는것은 출발점에서 시작해 D분이 지났을때 다시 출발점으로 돌아올수 있는 경로의 수이다. 이렇게 총 경로의 수를 구할때 Dynamic programming으로 해결할 수 있음을 유의하자! 정석은 2차원배열을 이용하는 것이지만 배열을 하나더 추가로 두는 조건으로 1차원 배열 2개로도 해결이 가능하다. 두 풀이 모두 소개한다. import java.io.BufferedReader; import java.io.InputStreamReader; ..
백준(BOJ) 2655: 가장높은 탑쌓기 https://www.acmicpc.net/problem/2655 가장높은 탑쌓기: 최장증가 부분수열(LIS, Longest Increaing Subsequence) 문제의 변형 기존과 비슷한 문제여서 기존의 방법으로 뭔가 해결될 수 있을 것 같으면 해보면 된다. 다만 용납해서는 안되는 경우가 같은 문제임에도 불구하고 전혀 다른 풀이를 쓰고 기존의 해결방법을 적용할 줄 모르는 것이다. 만약 기존의 풀이법으로는 안된다면 왜 안되는지 파악해야 한다. 그것이 기존의 문제와 다른 차이점이기 때문이라면 차이점은 명확히 정리해서 알고있어야 한다. 그게 문제를 정리해 가는 것이므로. 대체 어떻게 했길래 dp[i]가 i번째 벽돌을 가장 아래에 뒀을때의 최대높이를 의미하게 할 수 있었던 것인가? (0-1배낭문제)대체 어..
백준(BOJ) 1932: 정수 삼각형 정수삼각형: https://www.acmicpc.net/problem/1932 기타리스트: https://www.acmicpc.net/problem/1495 정수삼각형문제는 최종 결과값들을 조회할 수 있는 틀이 있다. 하지만 기타리스트 문제는 최종 결과값들을 조회할 수 있는 정수삼각형 문제에서말하는 그 틀이 없고 입력으로 주워지는 최댓값이 있어 제한될 수 있는 범위라는 것이 있고 그 범위를 조회하면 답이 구해진다. 위에서 말하는 정수 삼각형 문제에서 틀이라는 것은 아래 그림과 같이 1,2,3,4,5...n 행을 거치는 누적 값들이 결국은 최하위행의 열중 어느 하나의 열에 결국은 들어가게 된다는 것이다. 기타리스트 문제는 이런 틀이 없다. 다만 결과로 얻을 수 있는 값을 제한하고 그로부터 조회할 수 있는 ..
백준(BOJ) 1495: 기타리스트 https://www.acmicpc.net/problem/1495 곡=아이템, 볼륨=무게 와 대응된다는것을 눈치채지 못했다. 왜? 0-1배낭문제는 dp의 안에들어가는 것이 보석의 가치이지만 기타리스트 문제에서는 dp안에 들어가는 값을 무엇으로 해주어야 할지 막막했다. 구하라고 하는 것이 최대볼륨인데 볼륨을 그냥 X축으로 사용해 버리리라고는 생각도 못했다.(문제를 정리해 나아가야 한다) 이문제는 점화식이라고 할게 없다. 그저 가로축, 세로축에 각각 어떤소재가 들어가는지 그리고 dp의 각 슬록값이 무엇이 되는지가 더 중요하다.(하지만 최적해를 구성하는데 부분해가 간접적으로는 쓰이고 있다) 점화식보다는 이것들을 파악하는 것이 더 중요한 문제가 있다. 그게 이 문제다. 문제를 정리해 나가야 한다. 어떻게 해서든..
백준(BOJ) 2579: 계단 오르기 https://www.acmicpc.net/problem/2579 이 문제를 풀게 되면서 하게 되는 생각이지만 2개이상의 선택지 중에 선택을 해야 하는 상황이 오면 DP는 탐욕적 알고리즘의 사고를 포함하게 된다. (이것은 0-1배낭문제 등 여러문제에서 확인할 수 있다) (아래는 0-1배낭문제 에서 나온 말이다. 2개이상의 선택지 중에 최선을 선택해야 하는 상황이 0-1배낭문제에는 존재하고 dp[i][j]는 그때의 무게에서 배낭에 넣을 수 있는 최대가치가 들어가게 된다. ) (나는 가끔가다 0-1배낭 문제에서 이런 걱정을 하곤한다. 점화식으로 dp 테이블을 채워나가던중 중간단계쯤에서 어떤 아이템이 등장하고 그 아이템의 무게는 이전 아이템들에 비해 정말 가볍고 가치는 엄청나다. 그런데 그 가벼운 무게를 담을..
백준(BOJ) 1904: 01타일 https://www.acmicpc.net/problem/1904 무조건 "나는 답을 모른다. 하지만 정답은 어찌됐든 최적의 원리가 적용되어 최적해는 부분해를 이용하여 이미 정의되어 있다"는 것을 기억하고 최적해를 부분해로 정의하기 위해 관계를 찾기 위해 그림도 그리고 그림간의 관계를 살피기 위해 시간을 써야 한다는 것이다. 일종의 영감은 어찌 됐든 그 후다. 이 문제에서 영감이라 함은 0두개가 붙어있으므로 길이가 2인 "00" 타일하나와 길이가 1인 "1"타일 하나, 총 2종류의 타일만이 존재한다는 것이다. 이는 곧 An은 An-1에서 앞에 "1"블럭 하나를 더한 경우와 An-2에서 앞에 "00"블럭 하나를 더한 An=An-1+An-2와 같은 점화식을 생각할 수 있게구나 하는 생각으로 이어진다. DP문..
백준(BOJ) 11726: 2×n 타일링 https://www.acmicpc.net/problem/11726 최적해의 부분해가 또다시 그것의 부분문제의 최적해가 되는 점화식을 쉽게 찾을수 있어 하급문제다. 왜 이와 같은 점화식이 성립할까? 물론 일일히 다 그려가면 왜 가능한지 알수 있지만 글로 풀자면 애초부터(N=1, N=2일때)다른 모양의 타일을 쌓는데서 시작하므로 타일의 모형은 서로 겹치지 않게 되는 것이다. 이문제에 관련된 해설이 넘쳐나는데 그거 보고 있자면 혼동만 가중된다. 분명 나는 훗날에 이 문제를 다시 보고 다른 문제와 비교할 것이다. 그 때 문제들을 잘 정리하기 위해선 기준이 필요하다. 지금 생각하는 이 기준이 나중에도 맞다고 생각할지 모르겠지만 그래도 글로 남겨본다. "부분해로 이루어지는 최적해의 점화식을 찾아야 한다. 그럼 부..

티스토리툴바