Hello, World & Me Hello, World & Me

📌 백준 2565번 - 전깃줄 (LIS / DP / 이분 탐색)✨ 문제 요약두 전봇대(A, B)가 있고, 각각의 전깃줄이 A의 위치와 B의 위치를 쌍으로 갖는다.전깃줄이 서로 교차하지 않도록 하기 위해 최소 몇 개를 제거해야 하는지 구하는 문제다.🧠 문제 해석전깃줄이 교차하지 않으려면 A에서의 순서가 증가할 때, B에서도 증가해야 한다.즉, A를 기준으로 정렬하면남은 B 값들이 가장 긴 증가하는 부분 수열(LIS)이 되도록 전깃줄을 선택하면 됨.✅ 정답 로직전깃줄 목록을 A 기준으로 오름차순 정렬한다.정렬된 리스트에서 B 값들만 추출한다.B 값들에서 LIS를 구한 뒤,전체 전깃줄 수 - LIS 길이 = 제거할 전깃줄 수🧱 DP 풀이 (O(N²))N = int(input())arr = [tuple(m..

📌 백준 9655번 - 돌 게임 (게임 이론 / DP)✨ 문제 요약1 또는 3개의 돌을 가져갈 수 있는 게임이 있다.총 N개의 돌이 있으며, SK와 CY가 번갈아가며 돌을 가져간다.마지막 돌을 가져가는 사람이 이긴다.SK가 항상 먼저 시작이기는 사람의 이름을 출력 ("SK" 또는 "CY")🧠 문제 해석이 문제는 기초적인 게임 이론 또는 DP로 푸는 대표 문제다.핵심은 "현재 돌 개수에 따라 이기는 사람이 정해진다"는 점이다.✅ 수학적 풀이 (패턴 관찰)N (돌 개수)승자1SK2CY3SK4CY5SK→ 홀수면 SK가 이기고, 짝수면 CY가 이긴다!✨ 정답 코드 (수학 풀이)N = int(input())print("SK" if N % 2 == 1 else "CY")✅ DP 풀이🔧 상태 정의dp[i] = ..

📌 백준 2839번 - 설탕 배달 (DP)✨ 문제 요약당신은 설탕을 정확히 N킬로그램 배달해야 합니다.설탕 봉지는 3kg 또는 5kg 두 종류만 있습니다.가장 적은 봉지 수로 N킬로그램을 배달하려면 몇 개가 필요할까요?만약 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.🧠 문제 해석3kg, 5kg 봉지만 사용 가능조합해서 정확히 N을 만들어야 함최소 봉지 수를 구하는 문제 → 최소값 DP🔧 점화식 설계dp[i] = i킬로그램을 만들기 위한 최소 봉지 수기본 점화식:dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1)i-3에 3kg 하나 추가i-5에 5kg 하나 추가둘 중 최소값 선택초기값:dp[0] = 0 (0kg은 봉지 0개)나머지는 float('inf')로 설정 (..

📌 백준 11722번 - 가장 긴 감소하는 부분 수열 (LDS)✨ 문제 요약수열이 하나 주어졌을 때,그 수열에서 감소하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.🧠 문제 해석LIS(가장 긴 증가하는 부분 수열)와 반대 개념즉, 수열의 요소들이 점점 작아지는 방향으로 이어져야 함연속되지 않아도 되고, 순서만 지켜지면 됨🔧 점화식 설계dp[i] = i번째 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이for i in range(N): for j in range(i): if arr[i] 🧱 DP 테이블 예시입력: arr = [10, 30, 10, 20, 10]i arr[i] dp[i] 의미 (i까지 고려했을 때 감소하는 수열 길이)0101 (처음 원소)1301 (증..

📌 백준 2579번 - 계단 오르기 (DP)✨ 문제 요약각 계단에는 점수가 주어지고, 계단을 밟으면 그 점수를 얻게 됩니다.다음 조건을 지키면서 마지막 계단까지 올라가며 얻을 수 있는 최대 점수를 구하는 문제입니다.조건한 번에 1칸 또는 2칸씩 오를 수 있다연속된 3개의 계단을 밟을 수 없다마지막 계단은 반드시 밟아야 한다🧠 문제 해석이 문제는 최댓값을 구하는 DP 문제입니다.특히, 연속 세 계단 금지라는 제약 때문에 두 가지 경로만 고려할 수 있습니다:✅ i번째 계단을 밟는 두 가지 방법i-2 → i→ 두 칸 점프 → dp[i-2] + arr[i]i-3 → i-1 → i→ 한 칸, 한 칸 → dp[i-3] + arr[i-1] + arr[i]그래서 점화식은 다음과 같습니다:dp[i] = max( ..

📌 백준 9095번 - 1, 2, 3 더하기 (DP)✨ 문제 요약정수 n이 주어졌을 때, 정수 1, 2, 3을 사용해서 합이 n이 되는 경우의 수를 구하는 문제입니다. 순서를 고려한다는 것이 핵심입니다.🧠 문제 해석이 문제는 순서를 고려한 경우의 수 DP 문제입니다. 각 숫자는 다음의 경우들로 쌓일 수 있습니다:마지막에 +1 을 붙이면 → dp[i-1]마지막에 +2 을 붙이면 → dp[i-2]마지막에 +3 을 붙이면 → dp[i-3]🔧 점화식dp[i] = dp[i-1] + dp[i-2] + dp[i-3]🧱 DP 테이블 예시idp[i]의미111 → 1가지221+1, 2 → 2가지341+1+1, 1+2, 2+1, 347총 7가지✅ 코드t = int(input())for _ in range(t): ..

📌 백준 1463번 - 1로 만들기 (DP)✨ 문제 요약정수 N이 주어졌을 때, 아래 연산 중 하나를 선택해서정수 1을 만들기 위한 최소 연산 횟수를 구하는 문제입니다.사용할 수 있는 연산X → X / 3 (단, 3으로 나누어떨어질 때)X → X / 2 (단, 2로 나누어떨어질 때)X → X - 1🧠 초기 접근 시도 (그리디 → 실패)처음에는 아래처럼 단순하게 나눌 수 있을 때마다 나누는 식으로 접근했지만,while N > 1: if N % 3 == 0: N //= 3 elif N % 2 == 0: N //= 2 else: N -= 1이 방식은 항상 최적의 해를 보장하지 않습니다.예를 들어 N = 10일 때,그리디 방식은 10 → 5 → 4 → 2..

쳇 GPT 가 대표적인 DP 유형 10가지를 정리한 것을 공유드립니다.✅ 1. 배낭 문제 (Knapsack DP)✔ 특징: 배낭에 최대한 많은 가치를 넣는 문제.✔ 예제 문제:0/1 배낭: 백준 12865 - 평범한 배낭무제한 배낭: 백준 2293 - 동전 1다중 배낭: 백준 12920 - 평범한 배낭 2점화식 예시 (0/1 배낭):dp[w]=max⁡(dp[w],dp[w−weight]+value)dp[w] = \max(dp[w], dp[w - weight] + value)✅ 2. LIS (Longest Increasing Subsequence, 최장 증가 부분 수열)✔ 특징: 배열에서 가장 긴 증가하는 부분 수열을 찾는 문제.✔ 예제 문제:기본 LIS: 백준 11053 - 가장 긴 증가하는 부분 수열최대..