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