DFS(깊이 우선 탐색)

DFS(깊이 우선 탐색)

현재 유데미와 인프런 강의를 통해 알고리즘을 학습하고 있습니다.
본 포스트는 해당 강의에 대한 내용 정리를 목적으로 합니다.

1. 재귀함수와 스택프레임

• 문제
  자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.

• 입력 설명
  첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.

• 출력 설명
  첫째 줄에 출력한다.

• 입력 예제 1
  3

• 출력 예제 1
  1 2 3

function solution(n) {
  function DFS(L) {
    if (L === 0) return;
    else {
      DFS(L - 1);
      console.log(L);
    }
  }
  DFS(n);
}

solution(3); // 1 2 3

0. solution(3) 함수가 호출되면 먼저, DFS(3) 함수가 호출됩니다.
   -> stack 1층에 쌓임
1. 매개변수 L은 0이 아니므로 DFS(2) 함수가 호출됩니다.
   -> stack 2층에 쌓임
2. 매개변수 L은 0이 아니므로 DFS(1) 함수가 호출됩니다.
   -> stack 3층에 쌓임
3. 매개변수 L은 0이 아니므로 DFS(0) 함수가 호출됩니다.
   -> stack 4층에 쌓임
4. 매개변수 L은 0이므로 return 됩니다.
5. 이제 stack의 4층부터 1층까지 차례대로 실행되면서 결과값을 반환합니다.

메모리의 스택(stack)영역은 함수의 호출과 관계되는 지역 변수와 매개변수, 반환 주소값 등이 저장되는 영역입니다.
함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장됩니다.
이렇게 스택 영역에서 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다.
참고로 스택이 할당된 공간보다 많은 공간을 차지하면 stack overflow에러가 발생합니다.

스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸된 후 돌아갈 반환 주소값(중단된 시점)부터 다시 시작합니다.

2. 이진수 출력(재귀)

• 문제
  10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요.

• 입력설명
  첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.

• 출력설명
  첫 번째 줄에 이진수를 출력하세요.

• 일력예제 1
  11

• 출력예제 1
  1011

function solution(n) {
  let answer = "";
  function DFS(n) {
    if (n === 0) return;
    else {
      DFS(parseInt(n / 2));
      answer += String(n % 2);
    }
  }
  DFS(n);
  return answer;
}
console.log(solution(11)); //1011

3. 이진트리순회(DFS:깊이우선탐색) 연습

• 전위 순회

function solution(v) {
  let answer;
  function DFS(v) {
    if (v > 7) {
      return;
    } else {
      console.log(v);
      DFS(v * 2);
      DFS(v * 2 + 1);
    }
  }
  DFS(v);
  return answer;
}

solution(1)

// 1 2 4 5 3 6 7

• 중위 순회

function solution(v) {
  let answer;
  function DFS(v) {
    if (v > 7) {
      return;
    } else {
      DFS(v * 2);
      console.log(v);
      DFS(v * 2 + 1);
    }
  }
  DFS(v);
  return answer;
}

solution(1)

// 4 2 5 1 6 3 7

• 후위순회

function solution(v) {
  let answer;
  function DFS(v) {
    if (v > 7) {
      return;
    } else {
      DFS(v * 2);
      DFS(v * 2 + 1);
      console.log(v);
    }
  }
  DFS(v);
  return answer;
}

solution(1)

// 4 5 2 6 7 3 1

---

취뽀하는 그날까지 꾸준히 업데이트 예정입니다.