🔍 문제링크https://www.acmicpc.net/problem/10844📌 문제 요약길이가 N인 계단 수의 개수를 구하는 문제이다.계단 수는 인접한 자리의 숫자 차이가 항상 1이어야 한다.첫 번째 자리는 0이 될 수 없다.정답을 1,000,000,000으로 나눈 나머지를 출력🛠 풀이 및 알고리즘DP 배열 정의`dp[i][j]`: 길이가 i이고 마지막 숫자가 j일 때 계단 수의 개수`dp[1][0] = 0` (첫 자리가 0이면 안됨)`dp[1][1] ~ dp[1][9] = 1` (한 자리 계단 수는 자기 자신)점화식 `dp[i][0] `= `dp[i+1][1]` (0은 이전 자리가 1인 경우만 가능)`dp[i][9]` = `dp[i-1][8]` (9는 이전 자리가 8인 경우만 가능)`dp[i][..

🔍 문제링크https://www.acmicpc.net/problem/2624📌 문제 요약목표 금액 n을 만들기 위해 k가지 종류의 동전이 주어진다.각 동전은 개수 제한이 있음.주어진 동전을 사용하여 목표 금액을 만드는 방법의 수를 구하는 문제🛠 풀이 및 알고리즘1️⃣ DP(동적 계획법) 활용dp[i] : i원을 만드는 경우의 수배낭 문제와 비슷한 접근 방식을 사용하여 동전의 개수 제한을 고려2️⃣ 점화식 유도기본적인 동전 문제는 개수 제한 없이 무한히 사용할 수 있는 경우→ dp[j] += dp[j - amount]그러나 이 문제는 개수 제한이 존재→ s개의 동전을 사용하는 경우를 고려해야 함for (int s = 1; s dp[j]는 현재 금액 j를 만들기 위해 s개의 동전을 사용했을 때 경우의 ..

🔍 문제링크https://www.acmicpc.net/problem/9455📌 문제 요약각 학생들은 프로젝트 팀을 구성할 때,자신이 원하는 단 한 명의 학생만 선택할 수 있다.팀을 이루는 경우는 사이클(Cycle)이 형성된 경우이다.팀을 이루지 못한 학생의 수를 출력해야 한다.🛠 풀이 및 알고리즘1️⃣ DFS를 활용한 사이클 탐색각 학생이 가리키는 관계를 DFS를 통해 따라가면서 방문 여부를 체크DFS 탐색 중 방문했던 노드를 다시 방문하면 사이클이 형성된 것2️⃣ 방문 체크(visited)와 종료 체크(finished) 배열 활용`visited[now] = 1` : 현재 학생 방문 체크`finished[now] = 1` : 현재 학생이 속한 탐색이 종료사이클을 확인하는 조건`visited[next..

🔍 문제링크https://www.acmicpc.net/problem/10541📌 문제 요약1부터 N까지의 숫자가 하나씩 포함된 순열이 주어질때,  이 순열에서 사이클(Cycle)의 개수를 구하는 문제.🛠 풀이 및 알고리즘1️⃣ DFS를 활용한 순열 사이클 탐색각 숫자가 가리키는 연결 관계를 따라가며 DFS 탐색 수행방문한 노드는 다시 방문하지 않도록 체크 (visited[])DFS 탐색을 수행하다가 이미 방문한 노드를 만나면 사이클이 형성됨 → 사이클 개수 증가2️⃣ 사이클을 찾는 과정`nums[i]`를 따라가며 방문한 적 없는 곳을 탐색DFS 탐색을 수행하다가 이미 방문한 노드를 만나면 사이클 형성 → ans++ 증가💡 코드public class Baekjoon_10451 { static ..

🔍 문제링크https://www.acmicpc.net/problem/1194📌 문제 요약N x M 크기의 미로에서 상근이가 출구('1')까지 도달하는 최소 이동 횟수를 구하는 문제미로에는 벽(#), 빈 공간(.), 열쇠(a~f), 문(A~F)이 존재한다.상근이는 빈 공간(.)과 열쇠(a~f)를 자유롭게 이동할 수 있다.문(A~F)는 해당하는 열쇠(a~f)를 획득해야만 통과 가능하다.출구('1')에 도달할 수 없는 경우 -1을 출력한다.🛠 풀이 및 알고리즘1️⃣ BFS (너비 우선 탐색) 활용 → 최단 거리 탐색미로에서 최단 거리를 구하는 문제이므로 BFS(너비 우선 탐색)를 사용한다.2️⃣ 비트마스킹을 활용한 열쇠 상태 관리1. 열쇠(a~f)를 비트로 변환 미로에는 최대 6개의 열쇠(a~f)가 존재..

🔍 문제링크https://www.acmicpc.net/problem/2206📌 문제 요약N x M 크기의 맵에서 (0,0)에서 (N-1, M-1)까지 최단 경로를 찾는 문제.벽(1)을 한 번만 부수고 이동 가능.빈 칸(0)은 자유롭게 이동 가능.이동할 수 있는 최단 거리를 출력 (-1이면 도달 불가능)🛠 풀이 및 알고리즘 ( BFS + 3차원 visited 배열)BFS를 활용하여 최단 거리 탐색`Point(x, y, isBroken)` 클래스 사용 → 벽을 부순 상태(isBroken)를 추가로 저장.3차원 visited 배열 (visited[n][m][2]) 사용`visited[x][y][0]` →벽을 부수지 않고 방문한 경우.`visited[x][y][1]` → 벽을 부수고 방문한 경우.벽을 부순..

🔍 문제링크https://www.acmicpc.net/problem/5427📌 문제 요약건물 내부에서 불이 확산하는 상황에서 상근이가 탈출할 수 있는 최소 시간을 구하는 문제.벽('#')은 이동 불가, 빈 공간('.')은 이동 가능.불(*)은 상하좌우로 확산하며, 상근이(@)도 상하좌우로 이동 가능.불이 이동한 후, 상근이가 이동 → 불보다 먼저 도달해야 탈출 가능.건물 밖으로 나가면 성공, 불가능하면 "IMPOSSIBLE" 출력.🛠 풀이 및 알고리즘 불(fire())을 먼저 BFS로 확산시킴fireTime[i][j]: 불이 도달하는 최소 시간을 저장.fireTime[i][j]의 초기값을 Integer.MAX_VALUE로 설정.불이 이동하면 fireTime[nx][ny] = fireTime[x][y..

🔍 문제링크https://www.acmicpc.net/problem/2225📌 문제 요약0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는  경우의 수를 구하는 문제.순서가 달라도 같은 경우로 인정 (1+2와 2+1은 같은 경우).한 개의 수를 여러 번 쓸 수 있음( 1+1 )결과를 1,000,000,000으로 나눈 나머지를 출력, 🛠 풀이 및 알고리즘dp[k][n] 정의`dp[k][n]`: n을 k개의 정수로 만드는 방법의 수.초기값 설정`dp[1][n] = 1` → 하나의 숫자로 n를 표현하는 방법은 1개 (n 자체).`dp[k][0] = 1` → 0을 k개로 만드는 방법은 0 + 0 + ... + 0 하나뿐.점화식 (DP)`dp[k][n] = dp[k-1][n] + dp[k][n-1]``d..

🔍 문제링크https://www.acmicpc.net/problem/9251📌 문제 요약두 문자열 str1과 str2가 주어졌을 때, 최장 공통 부분 수열(LCS: Longest Common Subsequence)의 길이를 구하는 문제.LCS는 연속되지 않아도 됨 -> 순서만 유지하면 됨.ACAYKP, CAPCAK에서는 `ACAK`가 LCS🛠 풀이 및 알고리즘dp[i][j] 정의dp[i][j]: `str1[0:i]`와 `str2[0:j]`의 LCS 길이.점화식 (DP)문자가 같으면 `dp[i][j] = dp[i-1][j-1] + 1`-> 두 문자가 같다면 이전 LCS 길이에 1증가.문자가 다르면 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`-> 이전 문자열 중 더 긴 LC..

🔍 문제링크https://www.acmicpc.net/problem/11054📌 문제 요약바이토닉 수열: 증가했다가 감소하는 형태의 수열수열에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제.증가하는 부분 수열(LIS)과 감소하는 부분 수열(LDS)을 결합하여 해결🛠 풀이 및 알고리즘dp1[i]: nums[i]를 마지막 원소로 하는 가장 긴 증가 부분 수열 (LIS).dp1[i] = max(dp1[i], dp1[j] + 1) (nums[i] > nums[j])dp2[i]: nums[i]를 첫 원소로 하는 가장 긴 감소 부분 수열 (LDS).dp2[i] = max(dp2[i], dp2[j] + 1) (nums[i] > nums[j])바이토닉 부분 수열의 길이 계산dp1[i] + dp2[i] - 1..