동적 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법• 중복 계산 감소 : 이미 계산한 결과를 저장하고, 필요할 때마다 재활용하여 중복된 계산을 피함• 점화식 : 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식• 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 함 완전 탐색은 다 탐색하므로 높은 시간 복잡도를 가지므로 ‘체계적’, ‘효율적’으로 탐색하기 위해서 2가지 조건이 있어야 함Overlapping Subproblems (중복 하위 문제) : 중복 계산해야하는 하위 문제가 존재Optimal Substructure (최적 부분 구조) : 하위 문제에서 구한 ..
🔗 가장 큰 정사각형 찾기 dp는 해당 위치에서 확장가능한 정사각형의 한 변의 길이를 저장첫 행, 첫 열은 board 배열과 동일하게 함dp[i][j] 을 기준으로 위쪽, 왼쪽, 대각선 위치의 dp에서 가능한 한 변의 길이를 확인대각선으로 확장되므로 최솟값으로 저장해야 함이때, 한 변이 증가 되므로 최솟값+1🔎 점화식dp[n] = min( dp[i-1][j-1] , dp[i-1][j], dp[i][j-1] ) + 1class Solution{ public int solution(int [][]board) { int rows=board.length; int cols=board[0].length; // 최대 한 변의 길이 int area=0; ..
🔗 등굣길🔎 Dynamic Programming작은 문제를 통해 큰 문제 해결 가능(i, j)의 값을 구하려면 이전 칸들의 값(dp[i-1][j], dp[i][j-1])을 이용하여 구할 수 있음중복계산 많음dp[i][j]에 최단 경로의 개수를 저장해 재사용최적 부분 구조문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있음(i, j)로 가는 경로의 개수는 (i-1, j)와 (i, j-1)에서의 경로 개수만 알면 구할 수 있음점화식 기반의 계산웅덩이인 경우 dp[i][j]=0나머지 dp[i][j]=dp[i-1][j]+dp[i][j-1]class Solution { static int MOD=1000000007; static int[][]dp; public int solution(in..
🔗2 x n 타일링class Solution { // Dynamic Programming public int solution(int n) { // 모듈러 값 int MOD = 1000000007; // dp 배열 초기화 if (n == 1) return 1; if (n == 2) return 2; // 동적 계획법 배열 초기화 int[] dp = new int[n + 1]; dp[1] = 1; // n = 1 dp[2] = 2; // n = 2 // 점화식에 따라 dp 계산 for (int i = 3; i
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
|---|---|
| 새 글 쓰기 |
W
W
|
| 글 수정 (권한 있는 경우) |
E
E
|
|---|---|
| 댓글 영역으로 이동 |
C
C
|
| 이 페이지의 URL 복사 |
S
S
|
|---|---|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
