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]));

何が集まるの?
共通要素のない2つの集合を意味します
すなわち,分割された2つの部分の集合を加算すると,入力として与えられた元の集合である必要がある->したがって,すべての要素の値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日であれば,その式は2つの場合を合わせて組合せ数を求めることができる

(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からなる組合せは同じであるから!)