BOJ_2315 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 주어진 예시 상황에 대해서 생각해보자. |가로등 번호| 1 | 2 | 3 | 4 | 5 | 6 | |:------:|:-:|:--:|:--:|:--:|:--:|----| | 위치 | 3 | 11 | 12 | 13 | 15 | 17 | | 소비량 | 2 | 10 | 18 | 19 | 15 | 19 | 마징가는 5번 가로등에서 출발한다. 다음으로는 4번 또는 6번으로 갈 수 있다. 4번으로 간 경우를 생각해보자. 여기서도 역시 3번 또는 6번으로 갈 수 있다. 그렇다면 예를 들어 5->4->3->2->1->6 인 경우를 살펴

BOJ_11057 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 N=1일 때 0, 1, ⋯, 9까지 총 10개가 존재한다. N=2일 때 오르막 수를 AB라고 두면, A는 0부터 9까지 가능하다. (0으로 시작할 수 있다는 조건에 의해) 그러면 A=0이고 B는 0~9, A=1이고 B는 1~9, ⋯, A=9이고 B는 9까지 총 55개가 존재한다. > 재귀 관계식 DPi : 길이가 j이고 i로 시작하는 오르막 수의 개수 DPi = sum(DPi + DPi+1 + ⋯ + DP9) 💻 구현하자 **길이가 n인 오르막

BOJ_10844 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 먼저, N=2인 경우(AB)를 생각해보자. 10, 12, 21, ⋯ ,87, 89, 98이 가능하다. 다음으로, N=3인 경우(ABC)를 생각해보자. A는 1~9가 가능하다. 이제 뒤의 두자리 BC를 구해야하는데, 이는 이미 N=2인 경우에서 구했다. 하지만 여기서 한가지 신경써야 할 것은 A에 따라서 B에 올 수 있는 수가 정해져있다는 것이다. 예를들어, A=3이면 B는 2 또는 4만 가능하다. 그러면 N=2인 경우에서 2, 4로 시작하는 것들이 가능하다. A가 2~8일 때는 위와 동일하지만, 1과 9일 때는 따로 생각해주어

BOJ_9095 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 먼저, [1 = 1], [2 = 1+1, 2], [3 = 1+1+1, 1+2, 2+1, 3]인 것은 쉽게 구할 수 있다. 주어진 예시 4에 대해서 생각해보자. 4는 1+'3', 2+'2', 3+'1'로 나눌 수 있다. 1) 1+'3' 위에 있는 3에 대한 정보를 활용하면 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3)을 얻을 수 있다. 2) 2+'2' 위에 있는 2에 대한 정보를 활용하면 2+(1+1), 2+(2)를 얻을 수 있다. 3) 3+'1' 위에

BOJ_1463 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 주어진 예시 '10'에 대해서 생각해보자. 10은 3가지 연산 중에서 '2로 나누기'와 '1을 빼기'를 적용할 수 있다. 그렇다면 '5->1'과 '9->1'에 필요한 연산의 수를 비교하여, 작은 쪽을 선택하고 +1('10/2=5' or '10-1=9')을 하면 '10->1'에 필요한 연산의 수를 구할 수 있다. 이렇듯 '10->9->3->1'에서 '10->1'을 구하기 위해서는 '9->1'이 필요하고, '9->1'은 '3->1', '3->1'은 '1->1'이 필요하므로, bottom-up으로 구하면 된다. > 재귀 관계식 M(n)

BOJ_9251 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 주어진 두 문자열을 X = $$x{1}x{2}⋯x{n}$$, Y = $$y{1}y{2}⋯y{m}$$으로 둔다. LCS(i, j)는 X$${i}$$ = $$x{1}x{2}⋯x{i}$$와 Y$${j}$$ = $$y{1}y{2}⋯y{j}$$ 사이의 LCS 길이 값을 의미한다. (1 LCS(i,

BOJ_2579 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 문제의 조건에 의해 마지막 계단(n번째 계단)은 무조건 밟아야 하므로, 경우의 수는 2가지가 존재한다. 1) n-2번째 계단 -> n번째 계단 2) n-1번째 계단 -> n번째 계단 단, 이 경우에는 연속된 3개의 계단을 밟을 수 없다는 조건에 의해 무조건 'n-3 -> n-1 -> n' 의 순서를 가지게 된다. > 재귀 관계식 stairs[n] = n번째 계단의 점수 S[n] : n번째 계단까지 오를 때 얻을 수 있는 점수의 최댓값 S[n] = maximum(S[n-2] + stairs[n], S[n-3

BOJ_11049 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 > 재귀 관계식 Ai : $$M{i}$$부터 $$M{j}$$까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 Ai = minimum(Ai + Ak+1 + d$${i-1}$$d$${k}$$d$$_{j}$$) (i <= k <= j-1) Ai = 0 💻 구현하자 Ai를 구하는 함수 ![](https://images.velog.io/images/choiyhking/post/114aa25a-0db2-41fc-a9ab-fcf4fcc8d463/Kakao

BOJ_11404 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 > 재귀 관계식 $$D{k}i = minimun(D{k-1}i, D{k-1}i + D{k-1}k)$$ 💻 구현하자 D 배열을 초기화 하는 함수 i = j인 경우, $$V{i}$$에서 $$V{j}$$로의 비용은 0이다. 나머지는 임의의 큰 값(INF)로 초기화 해준다. 플로이드-와샬 알고리즘 \- 1번째 for문: $$V_{k}$$를 거칠 경우에 대해.. \- 2, 3번째 for문: 모든 경로에 대해서.. 이전 단계에서 갱신된 비용(D[i][j

BOJ_1992 💡 생각하자 먼저, 주어진 영상이 모두 0 또는 1로 되어있는지 판단하는 함수를 만든다. 만약 주어진 영상이 0과 1이 섞여있으면, 같은 수로 이루어진 영상이 나올 때 까지 4등분 한다. 💻 구현하자 주어진 영상이 모두 같은 수로 이루어져 있는지 판단하는 함수 \- pivot: 영상에서 첫번째 원소 영상을 4등분하는 함수 \- 종료조건: 주어진 영상이 모두 같은 수로 이뤄져있거나(res = TRUE), 영상의 길이가 2보다 작은 경우(n < 2) 더이상 4등분 할 필요가 없다. 초기 호출문 💥 발전하자 에러 및 해결 divideMat() 내부의 반복문에서 아무생각없이 i=0, j=0부터 시작하여 무한루프가 발생했다. 주의하자! 📌

BOJ_1780 💡 생각하자 먼저, 주어진 행렬이 같은 수로 이루어졌는지 판별하는 함수를 만든다. 위의 함수를 재귀적으로 수행할 때, 전달되는 행렬이 분할된 9개 중 어떤 것인지 알려줘야한다. 그러므로 해당 행렬의 첫번째 원소의 좌표를 전달한다. 💻 구현하자 주어진 행렬이 같은 수로 이루어졌는지 판별하는 함수 \- srow, scol: 주어진 행렬의 첫번째 원소 좌표 행렬을 돌면서 첫번째 원소(temp)와 비교한다. -> 다른 값의 원소가 발견되면 FALSE -> 반복문을 끝까지 수행하면 모두 같은 수로 이루어졌음을 의미한다. 그러므로 TRUE \- count()는 temp로만 이루어진 행렬의 수를 세는 함수 행렬을 분할하는 함수 \- 종료조건: 1 by 1 행렬이 되거나 해당 행렬이 모두 같은 수

BOJ_14600 💡 생각하자 > $$2^n$$ ⨉ $$2^n$$ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-Tromino로 모두 채울 수 있다. _지금부터 편의를 위해 정사각형 한 변의 길이를 n으로 둔다. (단, n은 2의 거듭제곱)_ 한 변의 길이가 n인 정사각형에서 'X'가 속한 사분면을 확인하고, 해당 사분면을 제외한 나머지 3개의 사분면에 4등분 선을 중심으로 1칸씩 채워서 L-Tromino 하나를 생성한다. ![](https://images.velog.io/images/choiyhking/post/9397d2b9-24dd-4ebd-bb22-8e3d