쉽게 쉽게

📌 핵심 요약위→아래 — "꼭대기에서 여기까지"의 최대 합. 부모를 참조하므로 양 끝 경계 분기 2개가 필요하고, 마지막에 바닥 행을 훑어야 한다.아래→위 — "여기서 바닥까지"의 최대 합. 자식을 참조하는데 아랫 행이 항상 한 칸 넓으므로 경계 분기가 아예 없다. dp[0][0]이 곧 정답이다. 목차프로그래머스 #43105정수 삼각형높이 ≤ 500 · 원소 0 ~ 9,999난이도: [Level 3]숫자가 적힌 삼각형이 주어진다. 꼭대기에서 출발해 아래로 내려가되, 한 칸 이동할 때는 바로 아래 또는 바로 아래 오른쪽 칸으로만 갈 수 있다. 바닥까지 내려가면서 거쳐간 숫자의 합이 최대가 되도록 할 때, 그 합을 구하면 된다.풀이 과정경로 수와 칸 수를 비교해 DP로 접근할지 판단한다.DP 배열 한 칸에..

📌 핵심 요약상태 정의 — dp[i][j] = (i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이점화식 — 왼쪽 · 위 · 대각선 세 값 중 최솟값 + 1. 가장 작은 값이 정사각형 확장의 병목이 된다반환값 주의 — 문제가 요구하는 것은 한 변의 길이가 아니라 넓이(max × max) 목차1 문제 소개Programmers #12905가장 큰 정사각형 찾기board 크기 ≤ 1,000 × 1,000난이도: Level 20과 1로 이루어진 2차원 배열이 주어질 때, 1로만 채워진 가장 큰 정사각형을 찾아 그 넓이를 반환하는 문제다.풀이 과정모든 정사각형을 완전 탐색으로 검사하면 1,000 × 1,000 보드에서 시간 초과가 나므로 DP로 접근한다.dp[i][j]를 "(i, j)를 오..

script.js 에 별도 등록하세요. (티스토리가 서식 내 태그를 자동 삭제합니다) ================================================ -->📌 핵심 요약DP는 큰 문제를 작은 문제로 쪼개고, 이미 계산한 값을 저장해 재사용하는 알고리즘 기법입니다.파스칼의 삼각형은 이항 계수를 DP로 표현한 대표적인 예시입니다.문제풀이 과정에서 이항계수의 로직을 재귀 또는 DP를 활용하여 풀이했을 때, 차이점을 알아보려고 합니다. DP를 활용해 백준 11050 · 1010번을 오버플로우 없이 효율적으로 풀 수 있습니다. 목차1 DP(동적 프로그래밍)란?DP(Dynamic Programming, 동적 프로그래밍)는 큰 문제를 작은 부분 문제로 쪼개어, 이미 계..