LeetCode 53. Climbing Stairs
https://leetcode.com/problems/maximum-subarray/?envType=study-plan-v2&envId=top-interview-150
문제 설명
계단 정상에 가기 위해서 n걸음이 걸린다. 한번에 1계단 혹은 2계단을 오를 수 있을 때 정상까지 오를 수 있는 방법의 갯수를 반환
예시 1
입력 : n = 2
출력 : 2
설명 :1 + 1 / 2
예시 2
입력 : n = 3
출력 : 3
설명 : 1 + 1 + 1 / 1 + 2 / 2 + 1
제약 조건
1 <= n <= 45
풀이 전략
1. 완전 탐색 - 재귀
- ways(n) = ways(n - 1) + ways(n - 2)를 재귀 호출
- 시간 복잡도가 O(2n)으로 제약 조건 내 실행 불가
2. 재귀 + 메모이제이션(Top-Down DP)
- 한 번 계산한 값은 다시 계산하지 않고 저장해서 쓸 수 있지 않을까?
- 한 번 계산한 n을 cache[n]에 저장, 저장된 값은 계산하지 않고 반환
- 시간 복잡도가 O(N)으로 효율적
3. 데이터 테이블(Bottom-Up DP)
- 이전에 계산한 값을 활용하면 다음 값을 구할 수 있지 않을까?
- dp[1] = 1, dp[2] = 2로 초기화하고 dp[i] = dp[i - 1] + dp[i - 2]로 계산
- 현재 공간복잡도는 O(N)인데 배열을 꼭 사용해야 할까? -> 이전 값 두개만 기억하면 되므로 배열 필요 없음
- cur = prev1 + prev2로 반복 계산해서 n번째의 cur을 구함
- 시간복잡도가 O(N)으로 효율적, 공간복잡도도 O(1)로 효율적
풀이
재귀 + 메모이제이션(Top-Down DP)
class Solution {
public int climbStairs(int n) {
int[] cache = new int[n + 1];
Arrays.fill(cache, -1);
return dfs(n, cache);
}
private int dfs(int n, int[] cache) {
if (n <= 1) return 1;
// 이미 계산한 값은 재활용
if (cache[n] != -1) return cache[n];
return cache[n] = dfs(n - 1, cache) + dfs(n - 2, cache);
}
}
데이터 테이블(Bottom-Up DP)
class Solution {
public int climbStairs(int n) {
if (n == 1) return 1;
int prev2 = 1; // (2칸 전)
int prev1 = 1; // (1칸 전)
for (int i = 2; i <= n; i++) {
int cur = prev2 + prev1;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}
LeetCode 198. House Robber
https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=top-interview-150
문제 설명
각 집에 있는 돈이 nums로 주어질 때, 털 수 있는 최대 금액을 반환
단, 연결되어 있는 두집을 연속으로 털 수 없음
예시 1
입력 : nums = [1,2,3,1]
출력 : 4
설명 :1번집, 3번집을 터는 것이 최대
예시 2
입력 : nums = [2,7,9,3,1]
출력 : 12
설명 : 1번집, 3번집, 5번집을 터는 것이 최대
제약 조건
1 <= nums.length <= 100
0 <= nums [i] <= 400
풀이 전략
1. 완전 탐색 - 재귀
- 현재 집에서 털거나 털지 않거나 두 가지 경우만 존재
- max(i) = max(nums[i] + max(i + 2), max(i + 1))
- 시간 복잡도가 O(2n)으로 제약 조건 내 실행 불가
2. 재귀 + 메모이제이션(Top-Down DP)
- 한 번 계산한 값은 다시 계산하지 않고 저장해서 쓸 수 있지 않을까?
- 한 번 계산한 최대 금액을 cache[i]에 저장, 저장된 값은 계산하지 않고 반환
- 시간 복잡도가 O(N)으로 효율적
3. 데이터 테이블(Bottom-Up DP)
- 이전에 계산한 값을 활용하면 다음 값을 구할 수 있지 않을까?
- dp[1] = nums[1], dp[2] = nums[2]로 초기화하고 dp[i] = max(nums[i] + dp[i + 2], dp[i + 1]) 로 계산
- 현재 공간복잡도는 O(N)인데 배열을 꼭 사용해야 할까? -> 이전 값 두개만 기억하면 되므로 배열 필요 없음
- prevSkip, prevRob만 기록
- curRob = prevSkip + nums[i]
- curSkip = Math.max(prevRob, prevSkip)
- 시간복잡도가 O(N)으로 효율적, 공간복잡도도 O(1)로 효율적
풀이
재귀 + 메모이제이션(Top-Down DP)
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] cache = new int[n + 1];
Arrays.fill(cache, -1);
return dfs(n - 1, nums, cache);
}
private int dfs(int i, int[] nums, int[] cache) {
if (i == 0) return nums[0];
if (i == 1) return Math.max(nums[0], nums[1]);
// 이미 계산한 값은 재활용
if (cache[i] != -1) return cache[i];
return cache[i] = Math.max(nums[i] + dfs(i - 2, nums, cache), dfs(i - 1, nums, cache));
}
}
데이터 테이블(Bottom-Up DP)
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int prevRob = 0; // 이전에 훔친 경우
int prevSkip = 0; // 이전에 훔치지 않은 경우
for (int x : nums) {
int curRob = prevSkip + x; // 이번에 훔칠 경우
int curSkip = Math.max(prevRob, prevSkip); // 이번에 훔치지 않을 경우
prevRob = curRob;
prevSkip = curSkip;
}
return Math.max(prevRob, prevSkip);
}
}
LeetCode 139. Word Break
https://leetcode.com/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150
문제 설명
문자열 s와 문자열 사전 wordDict가 주어질 때, s를 공백으로 구분된 하나 이상의 사전 단어로 분할할 수 있는지 확인
사전에 있는 동일한 단어가 불할 시 여러번 재사용 될 수 있음
예시 1
입력 : s = "leetcode", wordDict = ["leet","code"]
출력 : true
설명 :"leet code"로 분할 가능
예시 2
입력 : s = "applepenapple", wordDict = ["apple","pen"]
출력 : true
설명 : "apple pen apple"로 분할 가능(apple 재사용)
예시 3
입력 : s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
출력 : false
제약 조건
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s와 wordDict[i]는 소문자로만 구성되어 있으며 wordDict[i]의 모든 문자열은 고유합니다
풀이 전략
1. 완전 탐색 - 재귀
- s를 매 위치마다 분기를 나눠서 재귀
- 시간 복잡도가 O(2n)으로 비효율적
2. 재귀 + 메모이제이션(Top-Down DP)
- 한 번 확인한 값은 다시 확인하지 않고 저장해서 쓸 수 있지 않을까?
- 한 번 확인해서 분할 가능한지를 cache[start]에 저장, 저장된 값은 확인하지 않고 반환
- 예시 : s = "leetcode", wordDict = ["leet","code"]
- 초기 : start = 0, cache = [null, null, null, null, null, null, null, null, null]
- dfs(0) 호출 : end를 늘려가며 "leet"가 사전에 존재하므로 dfs(4) 호출
- dfs(4) 호출 : end를 늘려가며 "code"가 사전에 존재하므로 dfs(8) 호출
- dfs(8) 호출 : 종료 조건에 따라 true 반환 -> dfs(4), dfs(0) 및 cache[4], cache[0] true
- 결과 : cache = [true, null, null, null, true, null, null, null, null]
- 각 start는 한번 씩만 확인하고 내부 end만큼 루프를 돌기에 시간 복잡도가 O(N²)으로 효율적
3. 데이터 테이블(Bottom-Up DP)
- 이전에 계산한 값을 활용하면 다음 값을 구할 수 있지 않을까?
- dp[i] : s[0..i) 분할 가능, j < i일 때 dp[j]가 true이고 s[j..i)가 사전에 있다면 true를 이용해서 dp[n]을 반환
- 예시 : s = "leetcode", wordDict = ["leet","code"]
- 초기 : dp[0] = true
- i = 1~3 : wordDict에 없음 dp[i] = false;
- i = 4 : j = 4일 때 dp[0] = true, s[0:4]는 wordDict에 있음, dp[4] = true;
- i = 5~7: wordDict에 없음 dp[i] = false;
- i = 8 : j = 4일 때 dp[4] = true, s[4:8] 은 wordDict에 있음, dp[8] = true;
- 각 j에 대해 i만큼 루프를 도는데 j를 최장 단어 길이(20) 만큼만 돌면 시간 복잡도가 O(N)으로 효율적
풀이
재귀 + 메모이제이션(Top-Down DP)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
// Boolean 배열은 기본값이 null이므로 캐싱 사용에 유리
Boolean[] cache = new Boolean[s.length() + 1];
return dfs(0, s, dict, cache);
}
private boolean dfs(int start, String s, Set<String> dict, Boolean[] cache) {
if (start == s.length()) return true;
// 이미 확인한 인덱스는 재활용
if (cache[start] != null) return cache[start];
for (int end = start + 1; end <= s.length(); end++) {
if (dict.contains(s.substring(start, end)) && dfs(end, s, dict, cache)) {
return cache[start] = true; // 현재 인덱스부터는 분할 가능
}
}
return cache[start] = false; // 현재 인덱스부터 분할 불가능
}
}
데이터 테이블(Bottom-Up DP)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
Set<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[n + 1];
dp[0] = true;
// 단어의 최대 길이를 통해 최적화
int maxLen = 0;
for (String w : wordDict) {
maxLen = Math.max(maxLen, w.length());
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= maxLen && j <= i; j++) {
// s[0..i-j] 분할 가능할 때 s[i-j.. i]가 사전에 있는지 확인
if (dp[i - j] && dict.contains(s.substring(i - j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
LeetCode 322. Coin Change
https://leetcode.com/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150
문제 설명
다양한 금액의 동전 배열과 총 금액을 나타내는 정수가 주어질 때, 금액을 만들기 위해 필요한 가장 적은 코인의 수 반환
총 금액을 만들 수 없는 경우 -1 반환, 각 종류의 동전은 무한히 많음
예시 1
입력 : coins = [1,2,5], amount = 11
출력 : 3
설명 :5 + 5 + 1
예시 2
입력 : coins = [2], amount = 3
출력 : -1
예시 3
입력 : coins = [1], amount = 0
출력 : 0
제약 조건
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
풀이 전략
1. 완전 탐색 - 재귀
- 모든 동전을 재귀적으로 하나씩 넣으면서 확인
- k개의 동전 종류를 최대 목표 금액 n만큼 단계를 반복하므로 시간 복잡도가 O(Kn)으로 비효율적
2. 재귀 + 메모이제이션(Top-Down DP)
- 한 번 계산한 금액의 최소 갯수는 다시 계산하지 않고 저장해서 쓸 수 있지 않을까?
- 한 번 계산한 금액별 최소 갯수는 cache[remain]에 저장, 저장된 값은 계산하지 않고 반환
- k개의 동전 종류를 각 금액 n만큼만 반복하므로 시간 복잡도가 O(K * N)으로 효율적
3. 데이터 테이블(Bottom-Up DP)
- 이전에 계산한 값을 활용하면 다음 값을 구할 수 있지 않을까?
- dp[i] : 금액 i을 만들기 위한 최소 동전 수, dp[i] = min(dp[i], dp[i - coin] + 1)
- 동전 종류 k번 만큼 금액 n만큼의 내부 루프를 돌기에 O(K * N)으로 효율적
풀이
재귀 + 메모이제이션(Top-Down DP)
class Solution {
public int coinChange(int[] coins, int amount) {
int[] cache = new int[amount + 1];
Arrays.fill(cache, -2); // -2 : 계산 안함, -1 : 불가능
int best = dfs(amount, coins, cache);
return best >= Integer.MAX_VALUE - 1 ? -1 : best;
}
private int dfs(int remain, int[] coins, int[] cache) {
if (remain == 0) return 0;
if (remain < 0) return Integer.MAX_VALUE - 1; // 불가능, 오버 플로우 방지
if (cache[remain] != -2) return cache[remain]; // 계산한 값 재활용
int best = Integer.MAX_VALUE - 1;
for (int c : coins) {
best = Math.min(best, dfs(remain - c, coins, cache) + 1);
}
return cache[remain] = best;
}
}
데이터 테이블(Bottom-Up DP)
class Solution {
public int coinChange(int[] coins, int amount) {
int INF = amount + 1; // 충분히 큰 값으로 초기화
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
// dp[i] : 현재까지 i를 만들기 위해 사용한 최소 동전 갯수 => 동전 사용 X
// dp[i - coin] + 1 : 현재까지 i - coin을 만들기 위해 사용한 최소 동전 갯수 + 1 => 동전 사용
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
}
LeetCode 300. Longest Increasing Subsequence
문제 설명
정수 배열 nums가 주어질 때, 가장 길게 증가하는 부분 수열의 길이를 반환
예시 1
입력 : nums = [10,9,2,5,3,7,101,18]
출력 : 4
설명 : [2 3 7 101]
예시 2
입력 : nums = [0,1,0,3,2,3]
출력 : 4
설명 : [0 1 2 3]
예시 3
입력 : nums = [7,7,7,7,7,7,7]
출력 : 1
설명 : [7]
제약 조건
1 <= nums.length <= 2500
-104 <= nums [i] <= 104
풀이 전략
1. 완전 탐색 - 재귀
- 모든 부분 수열을 나열해 길이 측정
- 시간 복잡도가 O(2n)으로 제약 조건 내 실행 불가
2. 데이터 테이블(Bottom-Up DP)
- 이전에 계산한 값을 활용하면 다음 값을 구할 수 있지 않을까?
- dp[i] : 인덱스 i를 마지막 원소로 하는 LIS, nums[j] < nums[i] 일 때 dp[i] = max(dp[i], dp[j] + 1)
- 각 인덱스만큼 이중 루프를 돌기에 시간 복잡도가 O(N²)으로 효율적
3. 인내 정렬(Patient Sorting, 이진 탐색 + 그리디)
- 인덱스 i마다 모든 j를 반드시 확인해야할까? 증가 수열의 가장 끝값을 가장 작게 유지하는 것이 확장에 유리(그리디)
- tails[i] : 길이가 i + 1인 증가 수열의 마지막 값 중 최소
- 새로운 수 x에 대해 tails에서 x를 덮을 수 있는 가장 왼쪽 인덱스 i를 찾아서(이진탐색) 교체하거나 추가
- 예시 : nums = [0, 1, 0, 3, 2, 3]
- 초기값 : tails = [0, 0, 0, 0, 0, 0], size = 0
- 0 : tails[0] = 0, size = 1
- 1 : tails[1]에 들어갈 수 있음 => tails = [0, 1], size = 2
- 0 : tails[0]에 들어갈 수 있음 => tails = [0, 1], size = 2
- 3 : tails[2]에 들어갈 수 있음 => tails = [0, 1, 3], size = 3
- 2 : tails[2]에 들어갈 수 있음 => tails = [0, 1, 2], size = 3
- 3 : tails[3]에 들어갈 수 있음 => tails = [0, 1, 2, 3], size = 4
풀이
데이터 테이블(Bottom-Up DP)
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int best = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// nums[j]가 nums[i]보다 적을 경우 후보가 될 수 있다
if (nums[j] < nums[i]) {
// nums[j]를 넣는 경우와 안넣는 경우 중 최대를 선택
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]);
}
return best;
}
}
인내 정렬(Patient Sorting, 이진 탐색 + 그리디)
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int l = 0, r = size;
while (l < r) {
int m = l + (r - l) / 2;
// 현재 위치에 넣을 수 없는 경우 오른쪽 확인
if (tails[m] < x) {
l = m + 1;
// 현재 위치에 넣을 수 있는 경우 더 왼쪽을 확인
} else {
r = m;
}
}
tails[l] = x;
// 오른쪽에 새로 붙인 경우 크기 증가
if (l == size) size++;
}
return size;
}
}팁
- 문제 풀이
- 경우의 수 및 각 경우에서 최적 구하기 -> DP 활용
- 점화식 찾기 -> 같은 계산을 메서드 호출로 반복하지 않고 캐싱해서 재활용하기
- 실무 활용
- 반복 호출 : 캐싱후 계산 없이 결과 보여주기
- 자연어 전처리 : 띄어쓰기 없는 문자열을 사전 단위로 토큰화
- 전자 결제 시스템 : 거스름 돈 동전 최소화
- 주가 분석 : 시계열에서 주식 가격이 가장 길게 상승한 구간 길이
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| 예제로 배우는 알고리즘 - 연결 리스트(Linked List) (1) | 2025.07.13 |
|---|---|
| 예제로 배우는 알고리즘 - 다차원 DP (3) | 2025.06.29 |
| 예제로 배우는 알고리즘 - Kadane 알고리즘 (2) | 2025.06.11 |
| 예제로 배우는 알고리즘 - 그래프 BFS (0) | 2025.06.06 |
| 예제로 배우는 알고리즘 - 힙 (0) | 2025.05.25 |
