cedis 님의 블로그

코드 한 줄 설명과 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("+..

백준 · DP · 점화식 · 실버3피보나치 형태의 점화식을 이용해 01 문자열 개수를 구하는 DP 문제문제 링크 바로가기문제 한눈에 보기목표길이 n인 01타일 수열의 개수 구하기핵심 개념DP, 점화식, 나머지 연산점화식dp[i] = dp[i-1] + dp[i-2]주의매 계산마다 15746으로 나눈 나머지를 저장해야 한다.핵심 1맨 뒤가 1로 끝나면 길이 i-1 문제로 연결된다.핵심 2맨 뒤가 00으로 끝나면 길이 i-2 문제로 연결된다.핵심 3그래서 결국 피보나치 형태 점화식이 나온다.최종 코드n = int(input())def tile(n): if n == 1: return 1 if n == 2: return 2 dp = [0] * (n + 1) dp[1]..

백준 · DP · 메모이제이션 · 브론즈1메모이제이션을 이용해 피보나치 수를 빠르게 구하는 DP 기초 문제문제 링크 바로가기문제 한눈에 보기목표n번째 피보나치 수 구하기핵심 개념재귀 + 메모이제이션(하향식 DP)점화식fib(n) = fib(n-1) + fib(n-2)핵심 1일반 재귀는 같은 값을 계속 다시 계산해서 매우 느리다.핵심 2이미 구한 값은 memo 에 저장해서 재사용한다.핵심 3메모이제이션의 흐름은 확인 → 계산 → 저장 → 반환 이다.최종 코드def fib_memo(n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] if n == 0: return 0 if n..

종료 시간이 가장 빠른 회의부터 고르면 최대한 많은 회의를 배정할 수 있는 대표 그리디 문제문제 한눈에 보기입력회의 목록 [(시작, 종료), ...]목표겹치지 않게 최대한 많은 회의를 선택하기핵심 전략종료 시간이 가장 빠른 회의부터 선택예시선택 예: [(1,4), (5,7), (8,11), (12,14)]핵심 1빨리 끝나는 회의를 먼저 고르면 뒤에 더 많은 회의를 넣을 여지가 생긴다.핵심 2이미 선택한 마지막 회의의 종료 시간 last_end 만 추적하면 된다.핵심 3새 회의 시작 시간이 last_end 이상이면 선택 가능하다.왜 종료 시간 기준 정렬일까?회의를 최대한 많이 배정하려면, 회의실을 빨리 비워 주는 선택이 유리하다. 그래서 시작 시간이 아니라 종료 시간이 빠른 회의를 우선 선택한다.그리디의 ..

매 순간 가장 큰 동전부터 최대한 사용하는 그리디 알고리즘의 대표 입문 문제문제 한눈에 보기입력거슬러줄 금액 change, 동전 종류 coins출력총 동전 개수와 동전별 사용 개수핵심 전략가장 큰 단위 동전부터 최대한 많이 사용예시1260원 → 500원 2개, 100원 2개, 50원 1개, 10원 1개 = 총 6개핵심 1현재 순간에 가장 큰 동전을 쓰는 것이 이득이라고 판단하고 바로 선택한다.핵심 2change // coin 으로 현재 동전 개수를 바로 구할 수 있다.핵심 3나머지 금액은 change % coin 으로 갱신한다.왜 그리디가 통하나?500원, 100원, 50원, 10원처럼 단위가 규칙적인 동전 체계에서는 큰 동전을 먼저 쓰는 것이 전체 동전 수를 줄이는 데 유리하다.다만 모든 동전 체계에서..

작은 문제부터 차례대로 쌓아 올리며 n번째 계단까지 가는 방법의 수를 구하는 Bottom-up DP 대표 문제문제 한눈에 보기문제한 번에 1칸 또는 2칸씩 올라갈 때, n번째 계단까지 가는 방법의 수 구하기부분 문제dp[i] = i번째 계단까지 오르는 방법 수점화식dp[i] = dp[i-1] + dp[i-2]예시n = 4 → 5핵심 1현재 계단에 도착하는 마지막 동작은 1칸 또는 2칸 뿐이다.핵심 2그래서 현재 값은 이전 두 값의 합이 되어 피보나치와 비슷한 구조가 된다.핵심 3Bottom-up은 3부터 n까지 순서대로 dp를 채워 나가는 방식이다.왜 점화식이 이렇게 나올까?i번째 계단에 도착하려면 마지막에 두 가지 방법만 가능하다.i-1번째 계단에서 1칸 올라오기i-2번째 계단에서 2칸 올라오기따라서 ..

Dynamic Programming · Fibonacci · Top-down · Memoization동적 프로그래밍 - 피보나치 수열 (하향식 / Top-down)재귀 피보나치를 메모이제이션으로 최적화해서 O(2^n) → O(n) 으로 바꾸는 대표적인 DP 입문 예제문제 한눈에 보기목표메모이제이션을 사용해 n번째 피보나치 수를 효율적으로 계산하기입력정수 n출력n번째 피보나치 수예시n = 10 이면 결과는 55핵심이미 계산한 값을 memo 에 저장하고 재사용한다핵심 1피보나치 정의는 fib(n) = fib(n-1) + fib(n-2) 이다. 이 정의가 틀리면 전체 코드가 무너진다.핵심 2메모이제이션은 memo 확인 → 없으면 계산 → 저장 → 반환 순서로 동작해야 한다.핵심 3재귀 호출마다 같은 memo ..

설명하려고 보니, 이번 주 배운 것들이 한 줄로 묶이기 시작했다이번 주는 트리와 그래프를 다시 붙잡았고,문제에 꽂아 보면서 구조를 읽는 연습을 했고,정글베이직 시리즈로 문법을 설명 가능한 문장으로 정리했고,마지막에는 Virtual DOM과 Diff를 직접 구현해 봤다.많이 한 주라기보다, 흩어져 있던 것들이 조금씩 연결되기 시작한 주였다.WIL문제해결이진 트리, BST, 그래프, BFS, DFS, 위상 정렬을 다시 봤다. 예전에는 각각 따로 외워야 하는 개념처럼 느껴졌는데, 이번에는 조금 다르게 보였다. 결국 핵심은 무엇을 어떤 순서로 방문하느냐였다. 트리 순회도 방문 시점의 차이였고, BFS도 큐라는 형식 위에서 움직이는 탐색이었고, 위상 정렬도 순서를 만들어 내는 그래프 읽기였다.특히 이번 주에는 개..