2 x n 타일링
위 문제는 처음 봤을 때 n의 수를 2 또는 1로 만들 수 있는 경우의 수를 구하라는거구나!
라고 생각하고 문제에 접근하였다. 즉 만약 n=5 라면 1과 2로 만들수 있는 경우의 수는 다음과 같다.
1 1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
2 2 1
2 1 2
1 2 2
이렇게 8가지의 경우의 수를 return 할 수 있는 로직을 구현하면 된다고 생각했다.
이를 구현하려면 어떻게 해야할까? 필자는 이를 BFS로 풀어야할지 DFS로 풀어야할지 감을 잡지 못했었다.
그렇게 다른 분들의 코드를 보며 학습하였다. 먼저 DFS로 푼 분의 코드이다.
function solution(n) {
var answer = 0;
// 타일을 채우는 방법의 가지 수
// 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
search(0);
// DFS
function search(step) {
if (step === n) return answer++; // answer = (answer+1)%1000000007
if (step > n) return;
// 가로
search(step + 2);
// 세로
search(step + 1);
}
return answer; // answer%1000000007
}
코드를 보면 이해가 가능한데 막상 코드로 접근하려고 하면 이 코드를 떠올리는게 쉽지않다..
하지만 코드를 보고 이해는 가능하다 실행 순서를 정리하면 다음과 같다!
function solution(n) { // 1. 함수 선언 2. 함수 대입
var answer = 0; // 4. 변수 선언 5. 변수 초기화
search(0); // 8. 함수 실행
function search(step) { // 6. 함수 선언 7. 함수 대입 여기서 함수 실행 컨텍스트 형성
if (step === n) return answer++;
if (step > n) return;
search(step + 2); // 9. 함수 실행 => 반복
search(step + 1);// 탈출 후 10 . 함수 실행
}
return answer;
}
solution(n) //3. 함수 실행이건 어떻게 되는걸까? 사실 이 재귀함수의 작동원리를 이해하는데 꽤 오래걸렸다...
search(step+2) 가 스택으로 쌓여 작업을 수행될 때 search(step +1)은 어디에 있는 걸까?
필자가 내린 결론은 아직 스택에 조차 쌓이지 않았다! 가 필자가 생각한 로직이다. 필자는 말솜씨가 뛰어나지 않아 이를 그림으로 표현해보았다.
재귀함수에서 두개가 호출 되었을 때 어떻게 동작하는지 제대로 익히지 못했는데 이제는 이해가 된다.
다음 함수는 아직 스택에 쌓이기도 전인 것이다! 계속 재귀로 호출되기 때문에 앞서 호출된 재귀함수가 빠져나오면 그때 두 번째 재귀함수가 실행될 수 있다.
이를 이용해 DFS / BFS에 접근이 가능하다.
이런식으로 연산을 하면 다음과 같은 접근이 가능하다. 함수가 실행되는 모습을 보면 DFS/BFS랑 굉장히 비슷함을 알 수 있다.
그렇다면 피보나치 수열을 DFS로 표현하면 어떨까?
피보나치 수열은 다음과 같다,
0, 1, 1, 2, 3, 5, 8, 13, 21
function fibo(n){
if(n<2){
return n
}
return fibo(n-2)+fibo(n-1)이렇게 된다면 함수의 실행은 어떻게 될까?
n= 5일경우
fibo(3)+fibo(4)
fibo(3) => fibo(1) + fibo(2)
fibo(4) => fibo(2) + fibo(3)
fibo(2)=> fibo(0) + fibo(1)
fibo(3) => fibo(1) + fibo(2)
이렇게 꼬리에 꼬리를 물고 결국
2+3 가되어 5 을 return 한다.
여기서 아쉬운 점은 반복되어 계산되는 경우가 있다는 것이다. fibo(3)은 위에서 한번 계산이 되는데도 f(4)에 의해 또 다시 계산하게된다. 이를 기억하도록 하면 더 나은 풀이방법이 되지 않을까?
개선하면
function fibo(n){
const arr =[0,1]
for(let i =2; i<=n; i++){
arr[i] = arr[i-2]+arr[i-1]
}
return arr[n]
위 문제는 DFS 방식으로 풀게되면 타임 오류가 발생한다. 왜냐하면 n 의 범위가 60,000 까지이기때문이다.
문제를 다시 보니 위 문제는 피보나치 수열을 따른다. 즉, n = 1 이면 1 n = 2 이면 2 n = 3 이면 3
n = 4 이면 5이다. 즉 피보나치 수열을 구현하면 되기 때문에 위 피보나치수열을 구현한 코드를 사용하면 된다.
그러므로 정답은 다음과 같다.
function solution(n) {
const arr = [0, 1, 2];
for (let i = 3; i <= n; i++) {
arr[i] = (arr[i - 2] + arr[i - 1]) % 1000000007;
}
return arr[n];
}아주 간단하게 해결이 가능했다. DFS 방식으로 n=60000일때의 경우를 따지면 아주 많은 경우를 다 뒤져보아야하기 때문에 좋지않는 방법이다.
모음사전
하..DFS를 이해하고 푸는 날이 오다니!!! 👀 너무 뿌듯하다!! 이해를 못해서 넘어갔던 문제를 드디어 DFS를 이용하여 풀 수 있게 되었다!!
위 문제는 완전 탐색문제로 깊이우선 탐색 DFS를 이용하여 해결하였다.
A, AA, AAA, AAAA, AAAAA AAAAE 순서로 계속 알파벳을 더해 그 값을 확인하는 문제였다.
그렇다면 5개의 자리가 있고 그 자리마다 가능한 모든 알파벳을 집어 넣어주면 되겠구나!!
그렇게 해결한 코드는 다음과 같다.
const word = "AAAE";
function solution(word) {
const arr = ["A", "E", "I", "O", "U"];
let count = 1;
const answer = [];
function dfs(AU, word) {
if (AU === word) {
answer.push(count);
}
if (AU.length > 5) {
return;
}
console.log(AU);
console.log(word);
if (answer.length < 1) {
count = count + 1;
}
dfs(AU + arr[0], word);
dfs(AU + arr[1], word);
dfs(AU + arr[2], word);
dfs(AU + arr[3], word);
dfs(AU + arr[4], word);
}
for (let i = 0; i < arr.length; i++) {
const firstWord = arr[i];
dfs(firstWord, word);
}
return answer[0];
}
solution(word);
위와 같이 count를 계속해주다가 만약 해당 word와 AU가 같아지면 count를 push하고 더이상의 count연산은 하지 않도록 하였다. dfs(AU+arr[0],word)가 먼저 실행 될 것이고 그리고 다음 이어서 계속 arr[0]을 더해주다가 조건이 만족되면 AAAA 부터 E가 들어갈 것이고 AAA부터 E 그림을 그려보면 다음과 같다.
이런식으로 코드는 진행이 될것이다!!
뿌듯하다 정말 벽으로 느껴졌던 DFS와 재귀함수를 이해할 수 있어서 너무 좋다...🥲
