211014_자료구조&알고리즘(7)

이진트리 순회(DFS:깊이우선탐색)

• DFS 깊이 우선 탐색으로 루트노드에서 시작해서
  깊게 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다

• 스택과 재귀함수로 구현된다

전위순회: 부모 -> 왼쪽자식 -> 오른쪽자식

function solution(n){
  let answer="";
  function DFS(v){

    if(v>7) return;
    else{
      answer+=(v+' ');
      DFS(v*2);
      DFS(v*2+1);
    }
  }
  
  DFS(n);
  return answer;
  }

  console.log(solution(1));

중위순회: 왼쪽자식-> 부모 -> 오른쪽자식

function solution(n){
  let answer="";
  function DFS(v){
    if(v > 7) return;
    else{
      DFS(v*2);
      answer+=(v+' ');
      DFS(v*2+1);
      }
  }
  DFS(n);
  return answer;
}

console.log(solution(1));

후위순회 : 왼쪽자식-> 오른쪽자식->부모

function solution(n){
  let answer="";

  function DFS(v){
    if(v > 7) return;
    else{
      DFS(v*2);
      DFS(v*2+1);
      answer+=(v+' ');
    }
  }

  DFS(n);
  return answer;
}

console.log(solution(1));

스택 프레임을 그리면서 재귀함수의 호출 순서를 공부하는데 어려움이 있었지만 일단 무조건 그림을 그리면서 진행했다 현재도 이해가 안가면 그리면서 하는중...🔥

부분집합 구하기

• 자연수 n이 주어지면 1부터 n까지의 부분 집합을 모두 출력하라

function solution(n){
  let answer = [];

  let tmp = [];

  function DFS(v){

    if(v === n+1){ //원소가 1부터 시작하기 떄문에  n+1 
      if (tmp.length !==0) // 이 처리 하지 않으면 값이 없을 떄도 slice 처리되어 마지막에 청답에 빈 배열 하나 추가됨 
      answer.push(tmp.slice()); 
    }
    else{ // 가지치기 즉 뻗어가는 애들(사용되는 애들)을 생성해주는 부분이라고 보자 
      tmp.push(v);// 사용하는 원소라면 tmp  push  
      DFS(v+1);// 그 다음 원소를 검사하기 위해 +1 재귀함수 실행
      tmp.pop();// 벡트래킹으로 부분집합으로 사용하지 않는 원소는 tmp에서 제거 
      DFS(v+1); // 그 원소가 사용되는지 검사 하기위한 재귀함수 실행 
    }
  }
  DFS(1); // 재귀함수의 시작 
  return answer;
}



console.log(solution(3));

합이 같은 부분집합

• n 개의 원소로 구성된 자연수 집합 , 이 집합을 부분집합으로 나눴을 때 서로소 집합이 있다면 yes 아니라면 no

function solution(nums){

  let answer = "NO";
  let total = nums.reduce((a,b) => a+b);
  let len = nums.length;
  //let flag = 1; 
  function DFS(n,sum){

    //끝나는 조건에서 합이 같아야지 서로소 집합이 되는 것이다 

    if(n === len ){ 
      if(total-sum == sum ){
        answer = 'YES';
      }
    }
    else{
      DFS(n+1,sum+nums[n]);
      DFS(n+1,sum);
    }
  }


  DFS(0,0);
  
  return answer;
}

console.log(solution([1,3,5,6,7,10])); //YES
console.log(solution([5,2,6,9,10,12])); //YES
console.log(solution([3, 9, 11, 13]));

서로소 집합이란?
공통 원소가 없는 두 집합을 의미한다
즉 나눠진 두 부분 집합을 합하면 입력으로 주어진 원래의 집합이 되어야함 -> 그래서 모든 요소의 값인 total를 구하고 시작하는 것

바둑이 승차(DFS)

• 각각의 무게가 주어진 바둑이들을 철수가 트럭에 태울 때 가장 무거운 무게를 구하는 문제
• nums에 바둑이의 무게정보
• c에 자연수가 주어진다

function solution(nums, m) {
  let answer = 0;
  let n = nums.length;
  function DFS(l, sum) { // 재귀함수 정의
    if (sum > m) return; // sum이 m(조건값)보다 크면 전(?) 재귀함수 실행하던곳으로 돌아간다
    if (l === n) { // 배열을 다 돌면
      console.log(sum);
      answer = Math.max(answer, sum); // m(조건값)에 가까운 값을 answer변수에 넣기
    } else {
      DFS(l + 1, sum + nums[l]); // 재귀함수-배열의 요소를 사용(=그 무게를 사용)
      //console.log(sum);
      DFS(l + 1, sum); // 재귀함수-배열의 요소를 사용하지 않음
    }
  }
  DFS(0, 0); // 함수호출 - 매개변수 0,0으로 넘기기
  return answer;
}
console.log(solution([81, 58, 42, 33, 61], 259));

중복순열 구하기

• 1부터 n까지 번호가 적힌 구슬 이 중 중복을 허락하여 m번을 뽑아 일렬로 나열

// n = 3, m = 2임을 기준으로 주석 기입 
function solution(n,m){
  let answer= [];
  let tmp = []; 

  function DFS(L){
    
    if(L === m ){ // D(2) 로 넘어온 경우로  중복 순열의 하나의 경우의 수가 완성
        answer.push(tmp.slice());   // 경우의 수 완성 시에 answer 에 추가 
    }else{
      for(let i = 1; i<=n; i++){ // n 가닥의 가지가 뻗어진다 생각하자 
        // 시작은 D(0) - > D(0)-1([1,]) ,D(0)-2([2,]) , D(0)-3([3,])  을 실행하는 반복 문 
        tmp.push(i); 
        DFS(L+1); // 다음 레벨 실행 다음 단계로 (ex D(1)로 실행 경우 ) [1,] 인 경우에 [1,1] 으로 추가될 깊이로 이동 
        tmp.pop();  // D(2) 가 실행이 된 후 돌아 오는 경우 pop이 실행이 됨, 다음 요소로 검사하기 위해 제거 
      }
    }
  }
  DFS(0); // 재귀함수의 시작 
  return answer;
}

순열 구하기

• 순열이란 n 개의 항목에서 순서를 가지면서 나열하는 방법이다 [1,2] 와 [2,1]을 순열에서 서로 다른 집합이다

function solution(nums,m){

	let answer = [];
	
	let tmp = [] ; // 순열을 뽑아서 담을 변수 
	let check = Array(nums.length).fill(0); // 체크 되는 부분을 확인 함 이미 쓰인 항목이라면 1, 아니라면 0 으로 세팅

	function DFS(L){

		if(L === m ){
			return answer.push(tmp.slice()); // 얕은 복사 처리 
		}else{
			for(let i = 0; i<nums.length; i++){
				if(check[i] == 0){
					check[i]= 1;
					tmp.push(nums[i]);
					DFS(L+1);
					check[i]= 0;
					tmp.pop();
				}
			}
		}
	} 

	DFS(0);
  return answer;

}
console.log(solution([3, 6, 9], 2)); // [[3, 6], [3, 9], [6, 3], [6, 9], [9, 3], [9, 6]]

순열이기에 check 배열을 만들어 순서 체크를 하는 것이다!

조합의 경우수(메모이제션)

• 기존 조합 경우의 수 공식을 쓰지 않고 아래 보이는 공식을 사용하여 DFS 로 문제를 풀었다

• n : 5 ,r =3 일 경우는 저 공식은 두가지 경우를 더하면 조합수를 구할 수 있다는 것이다

• (n-1) C( r-1 ) : n-1 : 4 , r-1 : 3 으로 4 개중에 5를 포함하고 조합하는 숫자 2개

• (n-1) C (r) : 5가 참여하지 않는 4개 중에 3개를 뽑아서 조합한 수

function solution(n,r){

  let answer = 0; 
  let memoization = Array.from(Array(35), () =>  Array(35).fill(0));

  function DFS(n,r){
    if(memoization[n][r] > 0) return memoization[n][r];

    if(r === 0 || n === r) return 1; 
    else{
      return memoization[r][n] =  DFS(n-1,r-1) + DFS(n-1,r);
    }
  }
  answer = DFS(n,r);

  return answer;
}

console.log(solution(5,3));

메모이제이션으로 호출되었던 값들은 배열에 저장하여 중복으로 사용되는 것들은 꺼내와서 사용하므로 시간복잡도가 매우 줄어든다!

조합구하기

• 1~n까지 번호가 적힌 구슬을 조합의 결과로 출력하여 배열로 반환

function solution(n,m){

let answer = [];
let tmp = [];// 조합을 만들 배열 

  function DFS(L,s){ //DFS(Level, start) level은 무조건 증가하고 s는 조합할 뽑은 숫자를 의미한다 
    if(L === m ){
      answer.push(tmp.slice());  // tmp 배열에 m 개의 조합이 뽑혔다면 모두 뽑았기에 answer 에 추가 
    }
    else{
      for(let i = s; i<=n; i++){ // 시작 자연수 부터 n까지 반복작업 , 재귀함수가 사용되기 때문에 다시 stack으로 돌아왔을 때 i가 뭐였는지 혼돈하기 쉽다 주의하자 
        tmp.push(i);
        DFS(L+1,i+1); 
        tmp.pop();// 넣어줬던 i는 이미 구성을 answer 에 추가한  조합이므로 제거 
      }
    }
  }
  DFS(0,1); 
  return answer;
}

• 조합은 집합에서 다른 n개의 원소 중에서 순서에 상과없이 r개를 선택할수 있고 중복이면 안된다
• 순열에서 [1,2] 과 [2,1]은 다른 결과이지만 조합은 [1,2][2,1] 는 같은 것이다 (1 과 2로 구성된 조합이 같이 때문!)