# dynamicprogramming

30개의 포스트
post-thumbnail

<종만북> 08. 동적계획법_폴리오미노 (polyomino) c++

구하고자 하는 것은 세로 단조 폴리오미노이다. 세로 단조 폴리오미노가 되려면 각 가로줄에 포함된 정사각형은 항상 일렬로 연속해 있다. 첫 줄에 i개의 정사각형이 속한 폴리오미노의 개수는 나머지 n-i개로 구성된 정사각형들로 폴리오미노를 만든 뒤, 이들을 적절히 맨 윗

2021년 11월 4일
·
0개의 댓글
post-thumbnail

<종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++

먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다.2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로

2021년 11월 3일
·
0개의 댓글
post-thumbnail

<종만북> 08. 동적계획법_우물을 기어오르는 달팽이 c++

확률과 경우의 수는 밀접한 관련이 있기 때문에 많은 경우 확률을 계산하는 문제에도 동적 계획법을 써먹을 수 있다. 먼저 책의 예제에서 각 날짜에 비가 올 확률이 정확히 50%라고 가정할 때, m일 안에 달팽이가 우물 끝까지 올라갈 확률을 먼저 본다. m일 간 비가

2021년 11월 2일
·
0개의 댓글
post-thumbnail

<종만북> 08. 동적계획법_삼각형 위의 최대 경로 개수 세기 (Tripath Count) c++

먼저 삼각형 위의 최대 경로 갯수를 세기 위해서는 최대 경로를 푸는 알고리즘을 먼저 짜야한다. (y,x) 의 위치에서 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있기 때문에 (y+1, x)와 (y+1, x+1) 중에 큰 숫자를 찾아 더해서 내려가면 된다.

2021년 11월 1일
·
0개의 댓글
post-thumbnail

<종만북> 08. 동적계획법_외발 뛰기 (Jumpgame)

밑에 그림처럼 n x n 크기의 격자에 1부터 9까지 정수를 쓴 게임판이 있다. 이 게임의 목적은 게임판의 왼쪽 위 칸에서 시작해 게임파의 맨 오른쪽 아래 칸에 도착하는 것이다. 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있다.코드 8.4기저사례: 게

2021년 10월 25일
·
0개의 댓글
post-thumbnail

<종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence

앞에서 LIS 문제는 많이 다뤘다. 하지만 이번에 다룰 내용은 더 심화된 JLIS 문제이다. 근데 책에서는 난이도가 하 라고 되어있다..하하..예를 들어 '1 3 4 7 9'은 '1 9 4'와 '3 4 7'의 JLIS이다. 문제는 정수 수열 A, B가 주어질 때 JLI

2021년 10월 24일
·
0개의 댓글
post-thumbnail

<Baekjoon>#1309 동물원 (Zoo) c++

이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다.먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다.사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다.다음 동물원의 크기가 가로2 세로2

2021년 10월 21일
·
0개의 댓글
post-thumbnail

<Baekjoon>#1149 RGB 거리 (RGB street) c++

먼저 dpN 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다.dp0= 1번 집이 R를 색칠했을 경우 비용의 최솟값, dp0= 1번 집이 G를 색칠했을 경우 비용의 최솟값,dp0= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장

2021년 10월 21일
·
0개의 댓글
post-thumbnail

<Baekjoon>#2133 3n 타일 채우기 (3n Tiling) c

처음 타일링 문제를 접했을 때는 이게 도대체 뭐지? 하는 생각이 들었다. 동적 프로그래밍을 처음 접한 문제가 타일링 이었기 때문에 더욱 더 낯설고 이상(?)했다.이 문제를 풀기 전에 타일링 문제의 경우 끝을 기준으로 나눠서 생각해야 한다. 3 x k 인 타일의 경우 3

2021년 10월 20일
·
0개의 댓글
post-thumbnail

<Baekjoon>#1699 제곱수의 합 (Sum of square number) c++

문제만 봐서는 아무런 아이디어도 떠오르지 않아서 표에 채워 넣어가면서 규칙을 찾아보려 했다.여기서 얻었던 몇 개의 단서는dp1=1dpi\*i=1 (어떤 수의 제곱 수는 1)dp3=dp3-1\*1+1dp5=dp5-2\*2+1dp6=dp6-2\*2+1…이런 규칙을 찾을 수

2021년 10월 16일
·
0개의 댓글
post-thumbnail

<Baekjoon>#13398연속합2 (Largest sum of continuous subarray) c++

앞에서 푼 연속합의 문제와 다른 점은 수열에서 수를 하나 제거할 수도 있고 안 해도 된다는 것이다.표를 그리면서 여러가지 생각을 했다.(dynamic programming 진짜 안 풀린다..) 먼저 한 생각은 연속된 수가 0보다 크거나 같은 양수일 경우에는 그냥 더하고

2021년 10월 14일
·
0개의 댓글
post-thumbnail

<Baekjoon>#1912 연속합 (Largest sum of continuous subarray) c++

이 문제 푸는데 삽질을 엄청 엄청 많이 했다.. 다시 생각해도 눈물난다..첫 번째 아이디어dp를 2차원 vector로 만들어서 dy의 값은 Ay에서 시작해서 Ax에서 끝나는 합을 저장하고 저장 할 때마다 result 에 있는 값과 비교해 큰 값을 갱신해 주는 방법으로

2021년 10월 13일
·
0개의 댓글
post-thumbnail

<Baekjoon>#11054 가장 긴 바이토닉 부분 수열 (Longest bitonic subsequence) c++

문제에서 주어진 대로 바이토닉 부분 수열은 수열 A가 주어졌을 때 Ai값을 기준으로 A0에서 Ai-1중 증가하는 부분 수열이 존재하고, Ai+1에서 AN중 감소하는 부분 수열이 존재하는 경우를 말한다.'가장 긴 증가하는 부분 수열' 알고리즘과 '가장 긴 감소하는 부분

2021년 10월 13일
·
0개의 댓글
post-thumbnail

<Baekjoon>#11055가장 큰 증가하는 부분 수열 (Bigget increasing subsequence) c++

먼저 Ai에 값을 입력 받으면서 Bi에도 값을 똑같이 넣어준다.A의 부분수열이 증가수열이면서 현재 비교대상값(Bi) 보다 이전까지의 합+ 현재값 (Bj+Aj)이 더 큰 경우 이 값을 현재 비교대상값(Bi)에 넣어준다.코드 짜면서도 자꾸 헷갈려서 표에 값을 채워가며 생각

2021년 10월 10일
·
0개의 댓글
post-thumbnail

<Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++

바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다. dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다. (처음에 dp의 값이 가장 작은 A값부터 B에 pus

2021년 10월 10일
·
0개의 댓글
post-thumbnail

<Baekjoon>#11053 가장 긴 증가하는 부분 수열 (Longest increasing subsequence) c++

종만북 P.232 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘을 공부하다가 도저히 이해가 안 돼서 일단 다른 사람들이 풀어 놓은 코드를 참고해서 코드를 작성했다.중첩 for문을 사용하여 Ai의 값과 Ai 이전의 값 Aj, 예를 들면 A5일 경우 A0부터 A

2021년 10월 10일
·
0개의 댓글

Dynamic Programming

입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결하는 방법Memoization 기법을 활용 : 이전 계산 값을 저장하여 다시 계산하지 않도록 하여 실행 속도를 빠르게 함

2021년 9월 16일
·
0개의 댓글
post-thumbnail

알고리즘 패러다임: Dynamic Programming

1. 컨셉 Dynamic Programming은 중복되는 부분문제들을 전부 계산하지 않고 해결하는 방법. 이 방법은 2가지 조건이 있을 때 사용할 수 있음. 최적부분구조(Optimal Substructure) 중복되는 부분문제(Overlapping Subproblem

2021년 5월 13일
·
0개의 댓글
post-thumbnail

Python Algorithm class (Dynamic Programming - 4)

Dynamic Programming (동적 계획법 - 4) > 8. 연속하는 수들의 최대 합 구하기 > 9. 그리드(Grid)에서 경로 찾기 > 10. LCS(Longest common subsequence) 문제 8. 연속하는 수들의 최대 합 구하기

2021년 5월 5일
·
0개의 댓글