dfs, 완전탐색, 백트래킹 관련 지식 정리

01) 

- return : 값을 반환하거나, 함수를 종료한다는 뜻 

- 이것의 출력은 3 2 1

- 자 봐봐. else {
//이 부분은 또 다른 함수로 넘어가기전 해결하고 갈 것을 넣는것이다. 

DFS(L-1)

//
}

- 이것의 출력은 1 2 3 

 

설명) 모든 함수는 스택에 저장되죠? 콜스택 하잖아요. 함수가 호출되면 스택에 함수 정보가 저장되는 것. 재귀함수도 함수니까 스택에 저장되죠 (스택프레임이라고 한다.)

- 스택프레임이란 (매개변수 L에 대한 정보, 지역변수, 복귀주소) 정보를 가지고 있음. 

- D(3) => D(2) => D(1) => D(0) 순으로 저장된다. 

- D(0)되자마자 return 으로 함수가 끝난다. 

- 함수 끝나면 딱 스택프레임이 사라진다. 

- D(0)이 끝나면서 복귀주소였던 D(1)의 12 라인 주소로 간다. 

- 그리고 cosnole.log(1) 출력 

계속 진행 후 

02) 

03) 이진트리순회 

- 이진트리 

            부모

왼쪽 자식 - 오른쪽 자식 

 

여기선) 왼쪽은 부모 * 2 

           오른쪽은 부모 * 2 + 1 

 

1) 전위 순위 (부, 왼, 오)

명심할것: 출력은 else 쪽에 하면 된다. 

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; 
}

//출력 : 1 2 4 5 3 6 7

2) 중위 순위 (왼, 부, 오)

부모노드 출력안하고 왼쪽 자식으로 간다. 

tip: 4 2 5 만 봐라 왼 부 오 인거 알겠지? 어떤 방식으로 출력하고 있는가?

=> 왼쪽까지 일단 다 간다음에, 

자기 자신을 출력하고 , 

오른쪽으로 간다. 

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