프로그래머스 level2 - (15)

박상하·2023년 3월 27일

목록 보기

15/37

ㅜㅜㅜㅜㅜㅜ
재귀함수, dfs, bfs 너무어렵다.. 사실 생각으로는 어떻게 풀어야할지 알겠지만 이를 구현하는 능력이 부족하다. 각 알고리즘은 이해했지만 이를 구현하는데 꽤 오랜 시간을 투자하고있다. 저번 소수찾기 문제부터 level2 에서 정답률이 조금 낮아지기 시작하자 재귀함수, dfs, bfds, dp 등을 구현할 수 없으면 손을 델 수 없다.
블로그를 오래 작성하지 못했던 이유도 같은 이유이다. 풀 수 있는 문제가 없어서 계속 헤메고있었다.
그럼 순열문제가 자주 나오니 외우자는 심정으로 유튜브와 각종 블로그 글을 보며 순열을 만드는 방법이라도 학습해보자는 마인드로 하루를 시작했다.

순열

순열은 순서를 신경써서 만들 수 있는 조합을 나열한 것이다.

예를 들어 a, b, c의 배열이 있을 때 이를 사용하여 순열을 만드는 것을 학습하였다.

기본은 위치를 바꾸어 주는 것이다. i 와 j의 이중포문처럼 각 배열을 순회하며
arr[i] 와 arr[j]의 위치를 바꾸어 주면 된다.
정말 그럴까? 그렇지만 위치를 바꾸어주더라도 ABC, BAC, CBA등 이미 바꿔준 위치를 기억할 수 있어야 한다. 이를 위해 dfs를 사용한다. dfs는 클로저의 역할로 그 당시의 변수들을 기억하는 게 아닐까? 라는 생각이 들었다.

즉 BAC에서 BAC는 기억되고 여기서 i와 j가 변경되는 것이다.
그런데 사실 이 부분이 아직 잘 이해가 안된다. For문 안에서 재귀함수가 사용되었을 때 함수의 실행 순서가 이해가 잘 안된다. 이를 보완해야 할 것 같다.
그렇게 유튜브 영상을 보며 세운 로직은 다음과 같다.

1.배열을 순회하며 i와 j에 있는 인자를 변경해주자
2. dfs로 변경된 값을 기억하고 i를 +하자
3. 그때 다시 i와 j의 본래의 위치로 돌려주자

코드는 다음과 같다.

//순열 Permutations
function Permutations(arr) {
  const result = [];

  //DFS
  function dfs(i, arr) {
    //base condition
    if (i === arr.length) {
      return result.push([...arr]);
    }
    for (let j = i; j < arr.length; j++) {
      const arri = arr[i];
      arr[i] = arr[j];
      arr[j] = arri;

      //swap
      dfs(i + 1, arr);
      //dfs
      arr[j] = arr[i];
      arr[i] = arri;

      //swap back
    }
  }
  dfs(0, arr);
  return result;
}