211014データ構造とアルゴリズム(7)
42624 ワード
バイナリツリー遍歴(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));
スタックフレームを描くときに再帰関数の呼び出し順を学ぶのは難しいですが、まず描きながら行わなければなりませんが、今も理解していないなら描きながら...🔥ローカルセットを求める
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));
ホモサブセット
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)
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));
繰り返しシーケンスを求める
// 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;
}
シーケンスを求める
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));
注記呼び出された値を配列に格納し、繰り返し使用する値を取り出して使用すると、時間の複雑さが大幅に低下します.組み合わせを求める
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;
}
Reference
この問題について(211014データ構造とアルゴリズム(7)), 我々は、より多くの情報をここで見つけました https://velog.io/@akk0504/211014자료구조알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol