문제: 퇴사 2 (백준 15486번)문제 분석입력: $N$일 동안 상담을 진행할 수 있으며,각 상담은 걸리는 기간 $T_i$와 얻을 수 있는 금액 $P_i$를 가진다.목표: 상담을 적절히 선택하여 얻을 수 있는 최대 수익을 계산하는 문제.조건: 상담이 끝나는 날을 초과하면 진행할 수 없다.해결 방법: 동적 계획법 (DP)이 문제는 배낭 문제 (Knapsack Problem)와 유사하다.각 날짜별로 상담을 선택할지 말지를 결정해야 하며, 최적의 선택을 누적하면서 해결해야 한다.DP 테이블 정의dp[i]: i번째 날까지 얻을 수 있는 최대 수익즉, i일이 끝났을 때 가능한 최대 이익을 저장한다.점화식현재까지의 최대 수익 유지$$ dp[i] = \max(dp[i], dp[i - 1])$$i번째 날까지의 최대 ..

문제: 팰린드롬? (백준 10942번)문제 분석입력으로 주어진 단어(숫자 배열)의 구간에 대해, 해당 구간이 팰린드롬인지 판별하는 문제다.n개의 수가 주어지고, m개의 질의가 주어진다. 각 질의는 시작 인덱스 S와 끝 인덱스 E가 주어지며, 이 구간이 팰린드롬이면 1, 아니면 0을 출력한다.동적 계획법(DP)을 이용해, 구간 $[i, j]$가 팰린드롬인지 판별하는 2차원 배열 dp를 구성한다. 기저 조건:한 글자짜리 구간은 항상 팰린드롬이므로, $dp[i][i] = true$인접한 두 수가 같으면, $dp[i][i+1] = true$ 점화식:$dp[i][j] = \text{true} \quad \text{if} \quad v[i] = v[j] \quad \text{and} \quad dp[i+1][j-1..

문제: 동물원(백준 1309번)문제 분석3칸짜리 우리에 사자를 배치하는 문제로, 각 줄에 사자를 배치하는 경우의 수를 구하는 DP 문제다.조건: 같은 줄에 사자를 가로로 붙어있게 배치할 수 없다.점화식 도출:dp[i] = i번째 줄까지 사자를 배치하는 경우의 수세 가지 경우의 수:사자를 배치하지 않는 경우왼쪽 칸에 사자를 배치하는 경우오른쪽 칸에 사자를 배치하는 경우이 조건을 고려하면 점화식은 다음과 같다.$dp[i]=(dp[i−1]×2)+dp[i−2]dp[i] = (dp[i-1] \times 2) + dp[i-2]$dp[i-1] × 2: 이전 줄에서의 모든 배치 경우에 대해, 이번 줄에 왼쪽 또는 오른쪽에 사자를 추가하는 경우dp[i-2]: 두 줄 전의 배치에 이번 줄을 빈 상태로 두는 경우 (붙어있을..

문제: 합분해 (백준 2225번)문제 분석0부터 $N$까지의 정수 $K$개를 더해서 그 합이 $N$이 되는 경우의 수를 구하는 문제다.이번 문제도 이전 문제와 비슷하게 지문 자체가 참 짧고 간결하고 DP를 사용한 문제이므로 알고리즘도 간결하다.다이나믹 프로그래밍을 이용한 해결 방법$dp[i][j]$를 $j$를 만들기 위해 $i$개의 숫자를 사용하는 경우의 수로 정의한다.초기화: $dp[1][j]$는 1로 초기화한다. (0부터 $j$까지의 합을 1개의 숫자로 나타낼 수 있는 경우의 수는 1이다)상태 전이: $dp[i][j]$ 는 $dp[i-1][k]$ 의 합이다. 여기서 $k$는 0부터 $j$까지의 값이다. 각 단계에서 현재 숫자를 포함하여 만들 수 있는 경우의 수를 누적한다.점화식$dp[i][j] = \..

문제 링크https://www.acmicpc.net/problem/17404문제 분석비슷한 유형의 RGB 거리보다 조금 더 심화된 DP 문제라고 할 수 있다.이전 문제에서 각 1번째 집의 색깔이 마지막 집(N-1)의 색과 동일하면 안 된다는 조건이 추가된 응용 버전인데, 시작을 1번째 집의 색깔을 R, G, B로 선택했을 때 각각에 대한 DP 배열을 이전 문제와 같이 채우면 되는 문제이다.DP 배열 구성DP 배열의 크기는 3(1번째 집의 색깔을 고르는 경우의 수) * n * 3이다.1번째 집의 색을 R로 선택했을 때의 경우를 예로 들면, 2번째 집에서는 1번째 집의 G, B에 해당하는 값을 선택하면 안 된다.여기서 아이디어가 필요한데, 본인은 DP 배열에서 1번째에서 선택한 집을 제외한 나머지를 임의의 ..

파이프 옮기기 문제 정리 및 풀이문제 개요파이프 옮기기 1: nn의 최대 크기가 16으로, 단순한 탐색 알고리즘으로도 풀이 가능.파이프 옮기기 2: nn의 최대 크기가 32로, 단순 탐색은 시간 초과 발생.두 문제는 기본적인 로직은 동일하지만, 입력 크기에 따라 효율적인 접근 방식이 필요하다. 파이프 옮기기 1 (탐색 방식)탐색 방식으로 모든 경로를 BFS로 탐색하여 풀이한다.탐색할 때 파이프의 세 가지 상태(가로, 대각선, 세로)를 기준으로 이동 가능 여부를 판단한다.코드 설명BFS 탐색queue를 이용해 파이프의 현재 상태를 관리한다.이동 가능한 위치를 계산하고, 조건을 만족하는 경우 dpdp 배열에 이동 경로를 추가한다.결과 출력dp[n−1][n−1]dp[n-1][n-1]: 도착점까지의 경로 수 출..