동적계획법 4

프로그래머스: 등굣길(JAVA)

문제 설명어떤 도시에는 집과 학교가 있고, 학생은 집에서 학교까지 가장 빠른 길로 가려고 한다. 도시의 지도는 m(가로), n(세로) 크기의 격자 형태로 구성되어 있으며, 학생은 항상 오른쪽 또는 아래쪽으로만 이동할 수 있다.그런데 지도에는 물에 잠겨서 지나갈 수 없는 지역들이 있으며, 해당 지역들은 puddles 배열에 좌표로 주어진다.당신은 이 학생이 집 (1, 1)에서 학교 (m, n)까지 갈 수 있는 최단 경로의 개수를 구해야 한다. 단, 경로의 개수가 매우 클 수 있으므로, 정답을 1,000,000,007로 나눈 나머지를 반환해야 한다.입력값m: 격자의 가로 크기 (1 ≤ m ≤ 100)n: 격자의 세로 크기 (1 ≤ n ≤ 100)puddles: 물에 잠긴 지역들의 좌표가 담긴 2차원 배열각 ..

Algorithm 2025.04.24

프로그래머스: N으로 표현(JAVA)

문제 설명숫자 N과 목표 숫자 number가 주어졌을 때, N을 최대 8번만 사용하여 사칙연산(+ - * /)과 숫자 이어 붙이기(N, NN, NNN 등)만으로 number를 만들 수 있는 가장 작은 횟수를 구하는 문제입니다.예: N = 5, number = 12일 때→ 5 + 5 + (5 / 5) = 11은 안 되고,→ 55 / 5 + 2 = 13도 안 되고,→ 5 * 2 + 5 + (5 / 5) = 12 같은 식으로 다양한 조합이 가능합니다.💡 풀이 - DP + Set 활용✅ 핵심 포인트dp[i]는 N을 i번 사용해서 만들 수 있는 모든 숫자 집합입니다.i를 1부터 8까지 순회하며 가능한 연산 조합을 모두 저장합니다.각 단계에서 목표값이 등장하면 바로 i를 리턴합니다.Java 코드import jav..

Algorithm 2025.04.24

프로그래머스: 정수삼각형(JAVA)

문제 설명정수 삼각형이 주어졌을 때, 꼭대기부터 바닥까지 이동 가능한 경로 중 숫자의 합이 가장 큰 값을 구하는 문제입니다.삼각형은 다음과 같이 구성되어 있으며, 한 칸 아래 또는 대각선 아래로만 이동할 수 있습니다. [7] [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5]​예를 들어 7 → 3 → 8 → 7 → 5 경로의 합은 30입니다. 이처럼 가능한 모든 경로 중 최댓값을 구하는 것이 목적입니다.접근 방식 - Bottom-Up DP이 문제는 동적 계획법(DP) 으로 풀 수 있습니다. 위에서부터 내려오는 방식도 가능하지만, 아래에서 위로 올라가는 Bottom-Up 방식이 훨씬 간단합니다.✅ 핵심 아이디어마지막 줄부터 시작하여, 위로 올라가며 ..

카테고리 없음 2025.04.24

백준 1463번: 1로 만들기

문제 설명주어진 정수 N을 다음 세 가지 연산을 이용해 1로 만들려고 합니다.N이 3으로 나누어떨어지면, 3으로 나눈다.N이 2로 나누어떨어지면, 2로 나눈다.N에서 1을 뺀다.이 연산을 최소한으로 사용하여 1을 만드는 방법을 찾는 문제입니다.해결 방법이 문제는 동적 계획법(DP, Dynamic Programming) 을 활용하여 해결할 수 있습니다.dp[i]를 정수 i를 1로 만드는 최소 연산 횟수라고 정의합니다.dp[1] = 0 (1은 이미 1이므로 연산이 필요 없음)dp[i]는 다음의 세 가지 경우 중 최소값을 선택합니다:dp[i-1] + 1 (1을 빼는 경우)dp[i/2] + 1 (i가 2로 나누어떨어지는 경우)dp[i/3] + 1 (i가 3으로 나누어떨어지는 경우)코드import java.io...

Algorithm 2025.03.12