오늘의 학습 키워드
DP
알고리즘 문제
공부한 내용
DFS
DP
- Top-Down: 큰 문제에서 작은 문제로 쪼개가면서 해결. 초기 상태로부터 점차 확장 . 재귀와 메모이제이션을 사용
- Bottom-Top: 작은 부분 문제를 해결하며 전체 문제를 해결
오늘의 회고
처음 시도 (DFS)
- 처음에 순서를 고려해서 모든 조합을 만드는 문제라고 생각해서 DFS로 구현해보려고 했다.
- 먼저 모음 배열이 필요하다. [ a, e, i, o. u]
- 문자열 1개일 때 a, e, i, o, u / 2개일 때 aa, ae, ai, ao, au, ee, ei, eo, eu, ii, io, iu, oo, ou, uu / ... 이렇게 조합이 됨.
- 주어지는 n은 조합할 문자열 길이이기 때문에 조합할 문자열 수를 재귀 호출할 때마다 +1해서 종료조건을 n과 +1씩한 조합할 문자열 수(strlen)가 같아질 때라고 생각했다.
- 종료 조건 이후에 오는 로직에 idx와 같거나 보다 큰 인덱스로 문자열을 만드는 로직이 필요했다.
- 또한 문제 출력 조건은 조합할 수 있는 문자열 총 개수여서 카운팅이 필요했는데 나는 이 때 List에 문자열들을 담아서 List의 size로 카운트를 하려고 했더니 로직이 복잡해지면서 구현이 어려워졌다.
해결 (DFS)
- 카운팅 해결
- count라는 클래스 전역 변수를 두고, "재귀 함수의 return;" 은 원하는 문자열을 만들어서 반환되는 의미이기 때문에 반환 바로 직전에 count를 +1 해주므로써 카운팅을 하면 된다.
- 문자열 조합 해결
- n = 2라고 가정한다.
- 문자열을 출력하지 않아도 되기 때문에 문자열이 생성됐다고 치고 카운트를 하면 된다. 이렇게 하면 List, Map 같은 문자열을 저장할 자료구조가 필요없기 때문에 성능면으로도 로직 복잡성 측면에서도 좋다고 생각한다.
- 내가 처음에 생각한 재귀함수와 매개변수: dfs("", 0, 0)? or dfs("", 0, 1)? ... I don't know..
- 왜 이렇게 생각했나 되짚어보면,
- 처음에 만든 문자열이 없으니까 ""로 시작했다.
- 두번째 파라미터는 추가할 모음의 인덱스(in 모음 배열)여서 0이면 a, 1이면 e 이런식이다.
- 세번째 파라미터는 만든 문자열의 길이이다. 0으로 할지 1로 할지 고민했다.
- strlen이 0이면 현재 만든 문자열이 없는 상태("")이고, 1이면 현재 만든 문자열 길이가 1("a")인 상태이기 때문에 결론적으로 0이 맞다.
=> strlen이 0이면, ""인 상태 > 재귀 함수 호출할 때 현재 문자열("")에 "a"를 추가하면 현재 문자열("a")
=> strlen이 1이면, "a"인 상태 > 재귀 함수 호출할 때 현재 문자열에 "a"를 추가하면 현재 문자열("aa")
- 처음 시작 dfs(0, 0)
- dfs(0, 0) [""] -> dfs(0, 1) ["a"] -> dfs(0, 2) ["aa"] dfs() 호출 시 만든 문자열 "a", "aa", return(카운트+1 )
- dfs(1, 0) [""] -> dfs(1, 1) ["e"] -> dfs(1, 2) 는 "e", "ee", return(카운트+1)
- ...
- dfs(4, 0) [""] -> dfs(4, 1) ["u"] -> dfs(4, 2) ["uu"] -> return;(카운트+1)
DP (Dynamic Programming)
문제 풀이
1번째 방법 DFS (문자열은 생성했다 치고, 카운팅)
class Solution {
int count;
int n;
char[] vowels = {'a', 'e', 'i', 'o', 'u'};
public void dfs(int idx, int strlen) {
//종료 조건 => 주어진 문자열 길이와 조합한 문자열 길이가 같은 경우
if (strlen == n) {
count++;
return;
}
//idx => 현재 사용할 모음의 vowels의 인덱스
//재귀 호출 시 vowels[idx] 으로 strlen+1 길이의 문자열을 만든다.
//ex) n=2; count=0; idx=> 이번에 사용할 모음을 가리키는 인덱스 / strlen=> 현재 만들어진 문자열 길이
//dfs(idx, strlen) [이번에 만들 문자열]
//dfs(0,0) [""] -> dfs(0,1) ["a"] -> dfs(0,2) ["aa"] -> return; (count = 1)
// -> dfs(1,1) ["a"] -> dfs(1,2) ["ae"] -> return; (count = 2)
// -> dfs(2,1) ["a"] -> dfs(2,2) ["ai"] -> return; (count = 3)
// -> dfs(3,1) ["a"] -> dfs(3,2) ["ao"] -> return; (count = 4)
// -> dfs(4,1) ["a"] -> dfs(4,2) ["au"] -> return; (count = 5)
// -> return; (count = 5)
//dfs(1,0) [""] -> dfs(1,1) ["e"] -> dfs(1,2) ["ee"] -> return; (count = 6)
// ->
// -> return; (count = 9)
//...
//
//dfs(4,0) [""] -> dfs(4,1) ["u"] -> dfs(4,2) ["uu"] return;
// -> return; (count = 15)
for (int i = idx; i < vowels.length; i++) {
dfs(i, strlen+1);
}
}
public int countVowelStrings(int n) {
this.count = 0;
this.n = n;
dfs(0, 0);
return count;
}
}
2번째 방법 DFS (문자열 + 카운팅)
class Solution {
int count = 0;
int n;
char[] vowels = {'a', 'e', 'i', 'o', 'u'};
public void dfs(String current, int idx, int depth) {
//카운팅 + 재귀 종료 조건
if (depth == n) {
count++;
return;
}
for (int i = idx; i < vowels.length; i++) {
// 현재 문자열에 모음을 추가해 길이+1 된 새로 조합한 문자열 생성
dfs(current+vowels[i], i, depth+1);
}
}
public int countVowelStrings(int n) {
this.n = n;
dfs("", 0, 0); // 빈 문자열로 시작
return count;
}
}
3번째 방법 (DP : Bottom-Top)
class Solution {
private Map<Integer, int[]> integerMap;
public int countVowelStrings(int n) {
if (Objects.isNull(integerMap)) {
integerMap = new HashMap<>();
integerMap.put(1, new int[]{1, 1, 1, 1, 1});
}
if (integerMap.containsKey(n)) {
return Arrays.stream(integerMap.get(n)).sum();
}
for (int i = 2; i <= n; i++) {
int[] prev = integerMap.get(i-1);
int[] cur = new int[5];
for (int j = 0; j < 5; j++) {
for (int k = j; k < 5; k++) {
cur[j] += prev[k];
}
}
integerMap.put(i, cur);
}
return Arrays.stream(integerMap.get(n)).sum();
}
}
4번째 방법 (DP : Top-Down)
class Solution {
private int[][] memo;
public int countVowelStrings(int n) {
memo = new int[n + 1][6]; // n+1 for length, 6 for vowel count from 0 to 5
return count(n, 5);
}
private int count(int n, int a) {
if (n == 1) return a;
if (a == 1) return 1;
if (memo[n][a] != 0) return memo[n][a];
int result = 0;
for (int i = a; i >= 1; i--) {
result += count(n - 1, i);
}
memo[n][a] = result;
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countVowelStrings(2)); // Expected output: 15
}
}
