cedis 님의 블로그

이번 문제는 문자열 s를 사전에 있는 단어들로 끊어서 만들 수 있는지 판별하는 Word Break 문제입니다. 얼핏 보면 문자열 탐색 문제 같지만, 실제로는 앞에서부터 어디까지 만들 수 있는지를 저장해 가는 전형적인 DP 문제입니다. 이 글에서는 문제 아이디어, 점화식, 시각화, 예제 분석, 그리고 코드 한 줄 설명까지 한 번에 정리해보겠습니다.핵심 요약문자열을 앞에서부터 잘라 보면서 만들 수 있는 위치를 체크합니다.dp[i]는 s의 앞 i글자까지 만들 수 있는지를 의미합니다.어떤 j에 대해 dp[j] == True 이고 s[j:i] 가 사전에 있으면 dp[i] = True 입니다.핵심은 이전까지 만들 수 있었는가 + 이번 조각이 사전에 있는가 입니다.시간 복잡도는 기본적으로 O(n²) 탐색 구조를 가집..

LeetCode · Dynamic Programming · PythonLeetCode House Robber 파이썬 풀이오늘은 DP 입문 문제로 자주 등장하는 House Robber를 정리해보겠습니다. 단순히 정답 코드만 보는 것이 아니라, 왜 이 문제가 DP인지, 어떻게 값이 쌓이는지 시각적으로, 그리고 코드가 실제로 한 줄씩 무슨 역할을 하는지까지 한 번에 이해할 수 있도록 구성했습니다.핵심 요약서로 붙어 있는 집은 동시에 털 수 없습니다.각 위치에서 현재 집을 털지 / 털지 않을지 비교합니다.점화식은 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 입니다.이번 글에는 시각화와 코드 한 줄 한 줄 해설도 포함했습니다.시간 복잡도는 O(n), 공간 복잡도는 O(n) 입니다.1. ..

정렬 후 기준값이 어떻게 갱신되는지 눈에 보이도록 만든 상세형 버전이다.1. 문제를 아주 짧게 말하면다른 지원자보다 서류와 면접이 모두 밀리는 사람은 선발할 수 없다. 이 조건을 만족하며 최대로 몇 명을 선발할 수 있는지 구하는 문제다. [Source](https://www.acmicpc.net/problem/1946)2. 핵심 아이디어한 기준으로 정렬하고 다른 기준만 본다서류 등수로 정렬하면, 현재 사람보다 앞에 있는 사람들은 모두 서류가 더 좋다. 따라서 현재 사람은 면접 등수만 지금까지의 최솟값보다 좋으면 선발 가능하다.3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4t = int(input()) 5 6for _ in range(t): 7 n = int(..

정렬 뒤 어떤 회의가 선택되고 왜 탈락하는지 흐름 중심으로 정리한 상세형 버전이다.1. 문제를 아주 짧게 말하면회의가 서로 겹치지 않게 하면서 최대 몇 개를 선택할 수 있는지 구하는 대표적인 그리디 문제다. 끝나는 시간이 빠른 회의를 먼저 잡는 것이 핵심이다. [Source](https://www.acmicpc.net/problem/1931)2. 핵심 아이디어왜 종료 시간이 빠른 회의를 먼저 고를까?가장 빨리 끝나는 회의를 먼저 골라야 이후에 더 많은 회의를 붙일 여지가 남기 때문이다.정렬 기준: 종료 시간 오름차순 → 종료 시간이 같으면 시작 시간 오름차순3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4n = int(input()) 5meetings = [t..

코인 하나를 반영할 때마다 배열이 어떻게 바뀌는지 보여주는 상세형 정리다.1. 문제를 아주 짧게 말하면주어진 동전들로 목표 금액 M을 만드는 모든 방법 수를 구하는 문제다. 최소 동전 개수가 아니라 조합의 개수를 세는 것이 핵심이다. [Source](https://www.acmicpc.net/problem/9084)2. 핵심 아이디어dp[x]의 뜻금액 x를 만드는 방법의 수초기값: dp[0] = 1업데이트: dp[money] += dp[money-coin]동전이 바깥 루프여야 순서만 다른 경우를 중복 계산하지 않는다.3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4t = int(input()) 5 6for _ in range(t): 7 n = int(input..

상태 정의와 경로 감각이 중요해서 상태 중심으로 풀어 쓴 상세형 버전이다.1. 문제를 아주 짧게 말하면1번 돌에서 N번 돌까지 앞으로만 이동한다. 이전 점프 길이를 기준으로 다음 점프 길이는 -1, 0, +1만 바꿀 수 있고, 몇몇 돌은 밟을 수 없다. 목표는 최소 점프 횟수다. [Source](https://www.acmicpc.net/problem/2253)2. 핵심 아이디어상태를 두 개로 잡아야 한다현재 돌 번호만 알면 부족하다. 직전에 몇 칸을 뛰었는지도 알아야 다음 점프 후보가 정해지기 때문이다.dp[i][v] = i번 돌에 마지막 점프 길이 v로 도착했을 때의 최소 점프 횟수3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4INF = 10 ** 9 5..

한 줄 해설과 용량별 DP 변화 중심으로 정리한 상세형 버전이다.1. 문제를 아주 짧게 말하면무게 제한 K 안에서 여러 물건 중 일부를 골라 담을 때 얻을 수 있는 가치의 최댓값을 구하는 전형적인 0/1 배낭 문제다. 물건은 각각 한 번만 사용할 수 있다. [Source](https://www.acmicpc.net/problem/12865)2. 핵심 아이디어dp[i][cap]의 뜻앞에서 i개 물건만 고려했을 때, 가방 용량 cap으로 얻을 수 있는 최대 가치현재 물건을 안 넣으면: dp[i-1][cap]현재 물건을 넣으면: dp[i-1][cap-weight] + value3. 전체 코드 1import sys 2 3input = sys.stdin.readline 4n, k = map(int, input()..

코드 한 줄 설명과 DP 테이블 변화에 집중한 상세형 정리다.1. 문제를 아주 짧게 말하면두 문자열이 주어졌을 때, 두 문자열에 모두 등장하는 공통 부분 수열 중 가장 긴 것의 길이를 구하는 문제다.예를 들어 ACAYKP 와 CAPCAK 의 LCS는 ACAK 이고 길이는 4다. [Source](https://www.acmicpc.net/problem/9251)2. 핵심 아이디어dp[i][j]의 뜻첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자를 봤을 때 만들 수 있는 LCS의 최대 길이문자가 같으면 dp[i][j] = dp[i-1][j-1] + 1문자가 다르면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])3. 전체 코드 1import sys 2 3s1 = sys.stdi..

백준 · 그리디 · 동전 · 실버4가장 큰 동전부터 최대한 사용하는 대표적인 그리디 동전 문제문제 링크 바로가기문제 한눈에 보기목표주어진 금액 k를 만들기 위한 최소 동전 개수 구하기핵심 전략가장 큰 동전부터 가능한 만큼 사용풀이 방식내림차순 정렬 + 그리디핵심 1동전이 큰 순서로 정렬되어 있으면 항상 큰 값부터 보는 것이 유리하다.핵심 2k // coin 으로 현재 동전 개수를 구한다.핵심 3남은 금액은 k % coin 로 갱신한다.최종 코드n, k = map(int, input().split())coins = []for _ in range(n): coins.append(int(input()))result = 0coins.sort(reverse=True)for coin in coins: cn..

백준 · 그리디 · 문자열 파싱 · 실버2수식에서 괄호를 적절히 쳐서 결과를 최소로 만드는 대표 그리디 문제문제 링크 바로가기문제 한눈에 보기목표괄호를 적절히 넣어 식의 값을 최소로 만들기핵심 전략첫 번째 '-' 뒤의 모든 수를 한꺼번에 빼기풀이 방식문자열 분리 + 그리디핵심 1값을 최소로 만들려면 한 번 빼기 시작한 뒤에는 최대한 많이 빼야 한다.핵심 2그래서 첫 '-' 기준으로 문자열을 나누면 된다.핵심 3맨 앞 부분은 더하고, 그 뒤 부분들은 각각 합쳐서 전부 뺀다.최종 코드s = input()part = s.split("-")result = sum(map(int, part[0].split("+")))for p in part[1:]: result -= sum(map(int, p.split("+..