DFS 정복기 🔥

오늘도 DFS에 대해 정리를 해보겠다!!!

저번에 풀었던 문제를 다시 풀어보았지만 결국 해내지못했다.. 하지만 안죽으니까 일어나야지

일어나서 다른 문제를 시도해보았다.

숫자 변환하기

위 문제는 딱보아도 전부 경우를 계산해야하는 DFS로 풀면 좋을 문제이다. DFS/BFS로 풀 수 있는 문제이다. 필자도 위와 같은 알고리즘을 선택하여 풀었다.

부끄럽지만 ㅋㅋ;; 처음 스케치는 다음과 같다. 이게 무슨말이냐면
나만알수있는 허접한그림

결국 2도 곱해보고 3도곱해보고 N도 더해보아야하지않나?

한 시점에서?

DFS/BFS를 공부하면서 재귀적 사고에대해 조금은 이해하게 되었다. 재귀는 결국 그 시점을 기억하고 모든 경우를 더해볼수 있는 장치이다. 1부터 10까지 더하는 반복문도 재귀로 표현할 수 있다.

블로그를 작성하는 시점에서 갑자기 재귀를 통해 덧셈을 하는 코드를 작성해보고싶어 뜬금없지만 작성해보겠다.

function Plus(){
 let Sum;
  const go=(sum,count)=>{
    if(count>10){
      Sum=sum
    return;
    }
    go(sum+count,count+1)
  }
  go(0,1)
  console.log(Sum)
}
Plus()

다음과 같이 표현 할 수 있다. 이제 조금은 재귀를 이해하고있는 거 같아 뿌듯하다.

그럼 다시 문제로 돌아와서 문제는 3가지의 경우가 있다.

x에 3을 곱하는경우
x에 2를 곱하는 경우
x에 n을 더하는 경우

그럼 위 3가지 방법이 한번의 dfs함수가 실행될때마다 연산해가면서 y와 같아지는 시점을 기억할 수 있으면 되지 않을까?

function solution(x, y, n) {
  let target;
  const dfs = (X, count) => {
   
    dfs(X * 3, count + 1);
    dfs(X * 2, count + 1);
    dfs(X + n, count + 1);
  };

  dfs(x, 0);

}
solution(x, y, n);

"대략적으로 위와 같은 코드의 모습이다" 생각했다.

dfs의 첫 번째 x+3, count+1의 재귀함수가 끝나면 그 함수가 시작되는 시점에서 x*2, count+1의 재귀함수가 순차적으로 시행된다.

그럼 세부적으로 코드의 형태를 구성하면 다음과 같다.

function solution(x, y, n) {
  let target;
  // 정답을 저장할 target
  const dfs = (X, count) => {
    if (target !== undefined && count > target) {
      //만약 target보다 count가 커버리면 더 이상 의미없음
      //그래서 return해버린다.
      return;
    }
    // count를 넘어서버리면 계산 더이상하지않고 Return함
    if (X >= y) {
      if (X === y && target === undefined) {
        target = count;
        // X===Y인데 target의 값이 아직 정해지지 않은 경우 
        // 예외적으로 target을 count값으로 할당 시켜준다.
      }
      if (X === y && count < target) {
        target = count;
        //그 후 count의 값이 target보다 작은데 X===y인 경우는 target의 값을 재할당해준다.
      }
      return;
    }
    dfs(X * 3, count + 1);
    dfs(X * 2, count + 1);
    dfs(X + n, count + 1);
    //그 후 dfs 실행
  };

  dfs(x, 0);
  //dfs 함수실행

  return target === undefined ? -1 : target;
  //target이 정해지지않는다면 -1  그렇지 않으면 target을 return한다.
}
solution(x, y, n);

그런데 위와 같이 실행했을 때 점수는 ??

62점

효율성에서 탈락을 하였다. 왜냐하면 y의 값 근처까지 가는데 많은 재귀가 필요하기 때문인 거 같다. 재귀가 너무 많이 일어난다..

그럼 어떻게 줄일 수 있을까?
질문하기에서 다른 분들에게 도움을 청했다. 한 분께서 Y를 기준으로 하향식으로 코드를 짜면 불필요한 재귀를 막을 수 있다고 정보를 주셨다.
그렇겠다. 왜냐하면 Y를 기준으로 나누기 연산을 통해 진행한다면 불필요한 곱셈을 줄일 수 있다. 나머지연산을 통해 나머지가 2 나 3이 아닌경우 2를 곱하거나 3을 곱하는 연산은 하지 않을 수 있기 때문이다.

다음과 같이 코드를 구성하였다.

96점

function solution(x, y, n) {
  let target;
  //target은 정답을 저장하기 위한 변수
  const dfs = (Y, count) => {
    if (!Number.isInteger(Y)) {
      return;
      //여기서 만약 Y의 값이 정수가 아니라 소수라면 해당 재귀에서 탈출하는 것이다. 
      //더이상의 나누기 연산과 더하기 연산이 무의미 하기 때문이다.
    }
    if (target !== undefined && count > target) {
      return;
     
    }
    if (Y <= x) {
      if (Y === x && target === undefined) {
        target = count;
      }
      if (Y === x && target > count) {
        target = count;
      }
      return;
      // 하향식은 0이 아닌 x와 비교가 이루어진다.
    }

    dfs(Y / 3, count + 1);
    dfs(Y / 2, count + 1);
    dfs(Y - n, count + 1);
  };

  dfs(y, 0);

  return target === undefined ? -1 : target;
}
solution(x, y, n);

4점은 어디에서 부족한지 아직 원인을 찾고있다. 시간이 오래걸리기전 지금 공부했던 것들을 정리하기위해 먼저 블로그를 작성하였다. 이 블로그가 작성이 완료되면 다시 리펙토링 해보아야겠다.

큰 수 만들기

위 문제에서 주의할 점은 숫자를 순서대로 놓고 그 속에서 숫자들을 k개수만큼 제거했을 때 가장 큰 수를 return 해야한다. 처음에 풀 때는 그냥 위 숫자들로 만들 수 있는 최대의 수를 만들면 되는 줄 알고 그렇게 dfs로 접근하여 해결하였다.

문제를 다시 읽어보니 number에서 k개수만큼 제거하고 남은 숫자가 가장 클 때를 return하면 된다.

테스트케이스통과!

그렇지만 본 채점에서는 2개 빼고 나머지 케이스에 모두 실패를 하였다. (런타임오류) 결국 해결하지 못한 채 다른 분들의 풀이를 보니 DFS로 해결한 분이 한분도 안계셧다. 결국 이말은 ? DFS로 풀 문제가 아니라 반복문으로 만들면 되는 문제.

하하하하하하 삽질만 정말 오랜시간 했다. 그렇지만 DFS를 공부하는 지금의 시점에서 그 시간들은 더 기본을 다질 수 있는 시간이었다. 코드를 보면서 설명해 보겠다.

let number = "1231234";
let k = 3;

function solution(number, k) {
  let target = 0;
//정답이 저장 될 target
  const dfs = (sum, recentIndex) => {
    if (sum === "0") {
      //number중 0 도 포함되어있다고하여 0이 시작으로 되는 경우는 모두 바로 return으로 dfs 탈출하였다.
      return;
    }

    if (sum.length === number.length - k) {
      if (target === 0) {
        target = sum * 1;
        // target이 초기값 0 일 경우 target은 sum이된다.
      }
      if (target < sum * 1) {
        target = sum * 1;
        // target보다 큰 sum이 등장할 경우 target의 값은 변경된다.
        // *1을 해준 이유는 string 타입을 number타입으로 변경해주기 위해서이다.
      }
      return;
    }

    for (let i = 0; i < number.length; i++) {
      if (i > recentIndex) {
        dfs(sum + number[i], i);
        //sum은 number[i]를 더한 string값이된다.
        //단 이전의 i를 기억하여 i보다 큰 인덱스에서만 더해갈 수 있도록하였다.
  
      }
    }
  };

  dfs(``, -1);

  return String(target);
  //최종적으로 string 타입의 타겟을 return한다.
}
solution(number, k);

비록 20점의 점수이지만..그래도 잘했다고생각한다. 아예 DFS에 대해 구현을 못했었던 지난 달에 비해 지금은 예전 코딩테스트를 처음 접했을 때의 희열을 느낀다. 더더욱 잘 준비해서 다른 문제들도 100점으로 통과할것이다!!

중요한건 어떤 알고리즘을 어떤 상황에서 써도되는지 잘 알아야겠다는 점이다.
DFS 물론 좋지만 너무 재귀가 많을경우 이는 런타임오류를발생시킨다.

상황에 맞게 문제를 해결할 수 있는 노력이 필요하다.