4. Algorithm

TIL List

DFS,BFS

BACK TRACKING

私のアルゴリズム思考段階

N-QUEENS

1) DFS

Depth First Search、韓国語表記優先探索.
ツリーまたはグラフでルートを検索し、特定の状況でできるだけ深く確認してから別のルートに戻ります.代表的にバックグラウンドトラッキングに使用されます.通常は再帰呼び出し実装が用いられるが、単純なスタック配列として実装することもできる.

(子どものことをよく知っていれば、誰もが知っていて、再び親のそばに戻ります)
DFSは,状態空間を表す木の中で,底に到達するまで,一方向にのみ下降する方式である.迷路を探すのは簡単だと思います.一つの方向から入って、最後の道(=木の底に着く)に着いて、元の道に戻って、もう一つの方向に向かいます.これを目標地点(=希望の年)が現れるまで繰り返す.

2) BFS

breadth First Search、韓国語表記優先探索幅.
探索アルゴリズムでは,DFSと比較して最も近い場所を探索してから距離的なものを探索する方法である.

(レベル別)
BFSはすべての分岐点を検査する方法である.チョルスとヨンヒが階段で石のはさみ布で遊んでいた時、「チョルスが自分の行きたいところに行く最小勝利回数は何回ですか」.同じ問題で役割を果たす.この場合,DFSは深さが無限の場合には逃れられず,重複を防止しても正確な年を見つけるには長い時間がかかる.BFSはすべてのブランチを探索し,同時に状態空間をナビゲートする.チョルスが勝った時、引き分けた時、負けた時にチェックし、それぞれの場合、他の3つの可能性をチェックした.ある場所で希望の年を見つけたら、これは最短の距離になります.

3) BACK TRACKING

すべての場合に数量を考慮するアルゴリズム.これは状態空間をツリーで表すのに適した方法です.ツリー検索アルゴリズムと考えられる.方式によっては深さ優先探索(Depth First Search,DFS)、幅優先探索(Breadth First Search,BFS)、最適優先探索(Best First Search/Hervisic Search)がある.長所は脳がなくても作れることです.
すべての状況の数を考慮する必要がある場合、DFSのほうがいいです.BFS実装は可能であるが,BFS実装を用いるとキューのサイズが非常に大きくなる.そして、DFSに比べて速度も同じです.そのため、通常、DFSは出荷が容易である.ほとんどの問題はDFSでも答えが出ます.(ただし、時間的複雑さの不利な要素に耐えなければならない)

(必要な値がない場合は元の値に戻り、他の値に移動します)

4)私のアルゴリズム思考段階

初めてファイルを見たときにSUBCLASSのようなクラッシュに遭遇しましたが、あらかじめ書かれているHTMLがどのように構成されているのか、JSファイルごとにどのようなインタラクションがあるのかを理解したので、さらに問題を理解することができます.
まず、すべての問題に近づくと、私の基本的な考えは:

この問題を行う必要がある「目的」は何ですか.

この問題は何を解決したいですか?

この問題はどのような形で構成されていますか.

5) N-QUEENS

まず,N−QUEENS sprintの目的はbacktrackingの概念を熟知することであり,backtrackingにおいてDFSの概念をより深く学ぶためともいえる.
BoardViewer.htmlを開くと以下の画像が表示されます.

そしてこの構造をコンソールで撮影すると以下のような内容になります.

以上の事実は以下の通りである.

1. Board 는 배열로 이루어져있다.

2. 각 배열은 총 n개의 요소를 가지고 있다. (n*n 체스판)

3. HTML 에서 말이 있는 자리에는 배열에서 1, 없는 자리에는 0 으로 이루어져있다.

1. Board.js

hasRowConflictAt

指定されたロー(rowIndex)で競合が発生していることを確認します.

hasRowConflictAt: function (rowIndex) {

}

まず、衝突が発生した状況を整理します.競合が発生した場合は、次のようになります.

충돌 나는 상황 예시


0: (4) [0, 1, 0, 1] //  각 행에 1이 하나 이상 있을 경우
1: (4) [0, 0, 0, 1]
2: (4) [1, 0, 0, 0]
3: (4) [0, 0, 1, 0]

=>  TRUE (충돌이 있다!)

💡 私の解決方法

// 1. 입력받은 rowIndex 는 특정 행 (가로) 을 원하는 것이므로 변수에 해당 배열의 주소를 참조해 특정 배열에 접근할 수 있게 한다.


let row = this.attributes[rowIndex]


// 2. 1이 두 개 이면 false 를 리턴해야 하므로 `let num = 0` 이라는 변수를 만들어준다.


let num = 0;


// 3. 우리는 그 배열에 1이 두 개 있을 경우 즉, 그 합이 2 일 경우 TRUE 를 리턴할 것이므로 `num+= row[i]` 를 만들어줘서 요소 중 1이 있다면 num 에 그 합이 저장되게끔 한다.


for (let i = 0; i < row.length; i++) {
  num += row[i]
}

// 4. 그리고 조건문을 만들어줘서 num 이 1 이상이면 true 를 리턴하게 한다.

hasAnyRowConflicts

チェス盤に行の衝突がないかどうかを確認します.

충돌 나는 상황 예시


0: (4) [0, 1, 0, 0] 
1: (4) [0, 0, 0, 0]
2: (4) [1, 0, 0, 0]
3: (4) [0, 0, 1, 1] // 행 충돌이 하나라도 있는 경우 

=>  TRUE (충돌이 있다!)

💡 私の解決方法

// 1. 위에서 만든 함수를 통해 각 배열을 돌아 해당 함수를 통과하면 true 를 리턴하게 한다.

if (this.hasRowConflictAt(i)) {
  return true;
}

hasColConflictAt

指定されたカラム(colIndex)で競合が発生していることを確認します.

충돌 나는 상황 예시


0: (4) [0, 0, 0, 0] 
1: (4) [0, 0, 0, 0]
2: (4) [0, 0, 1, 0]
3: (4) [0, 0, 1, 0] // 각 열에 1이 하나 이상 있을 경우

=>  TRUE (충돌이 있다!)

💡 私の解決方法

// 1. hasRowConflictAt 과 패턴은 비슷한데 열의 요소에 접근해야 한다.
// 즉, 각 배열의 colIndex 값에 접근해야 하므로 반복문을 통해 다음과 같이 접근한다.

for (let i = 0; i < attr.n; i++) {
  num += attr[i][colIndex]
}

// 2. 그리고 num 이 1 이상이면 true 를 리턴하게 한다.

if (num > 1) {
  return true;
}

hasAnyColConflicts

チェス盤に熱的な衝突がないかどうかを確認します.

충돌 나는 상황 예시


0: (4) [1, 0, 0, 0] 
1: (4) [0, 0, 0, 1]
2: (4) [0, 0, 1, 0]
3: (4) [0, 0, 1, 0] // 열 충돌이 하나 이상 있을 경우

=>  TRUE (충돌이 있다!)

💡 私の解決方法

// 1. 위에서 만든 hasColConflictAt 함수를 이용해 각 배열을 돌아서 해당 함수를 통과하면 true 를 리턴하게 한다.

for (let i = 0; i < arr.length; i++) {
  if (this.hasColConflictAt(i)) {
     return true;
}

hasSlashConflictAt

与えられたスラッシュの対角線(/)に衝突する馬があることを確認します.

충돌 나는 상황 예시


0: (4) [0, 0, 1, 0] 
1: (4) [0, 1, 0, 0] // 대각선에 충돌이 있을 경우
2: (4) [0, 0, 0, 0]
3: (4) [0, 0, 0, 0] 

=>  TRUE (충돌이 있다!)

💡 私の解決方法

第一に,まず,衝突を引き起こすすべての対角線の場合を求めた.

// 1
arr[0][1], arr[1][0]
// 2
arr[0][2], arr[1][1]
// 3
arr[0][3], arr[1][2]
// 4
arr[1][3], arr[2][2]
// 5
arr[2][3], arr[3][2]

パラメータが1を入力した場合は、arr[0][1], arr[1][0]とします.arr[i][매개변수]を例にとると、iが1増加するたびに、伝達されるパラメータは1減少する.
4番と5番なら次のように考えられます.

충돌 나는 상황 예시


0: (4) [0, 0, 0, 0, 0] // 매개변수 4를 입력받으면 arr[0][4] 부터 검사하면 된다.
1: (4) [0, 0, 0, 1] // arr[1][3]
2: (4) [0, 0, 1, 0] // arr[2][2]
3: (4) [0, 0, 0, 0] 

=>  TRUE (충돌이 있다!)

したがって、コードは次のように記述されます.

// 1. this.rows() 를 나타낼 변수 arr 선언

 let arr = this.rows();


// 2. 카운트 할 숫자를 담을 변수 num 선언

 let num = 0;


// 3. 반복문을 통해 arr[i][매개변수] 값이 1이라면 num++

if (arr[i][SlashColumnIndexAtFirstRow] === 1) {
   num ++;
}

// 4. 만약 num 이 1 이상이라면 true 를 리턴

if (num > 1)  {
  return true;
}

// 5. 한 번 반복할 때 마다 입력 받은 매개변수를 1씩 줄인다

SlashColumnIndexAtFirstRow--;

hasAnySlashConflicts

ボードのスラッシュ対角線(/)に衝突がないかどうかを確認します.

💡 私の解決方法

繰り返し文を返し、hasslashConflicts関数を満たす場合はtrueを返しますが、問題は、以前のように繰り返し文を返すと、繰り返し回数がチェックの回数に達しないことです.
したがって、次のコードが記述されます.

// 반복하는 횟수를 arr 길이의 2배로 늘려준다.

for (let i = 0; i < arr.length * 2; i++) {
  if (this.hasSlashConflictAt(i)) {
    return true;
  }
}

hasBackSlashConflictAt

指定した反スラッシュ対角線()に衝突する馬があることを確認します.

충돌 나는 상황 예시


0: (4) [1, 0, 0, 0] 
1: (4) [0, 1, 0, 0] // 역 대각선에 충돌이 있을 경우
2: (4) [0, 0, 0, 0]
3: (4) [0, 0, 0, 0] 

=>  TRUE (충돌이 있다!)

💡 私の解決方法

前述のhasslashConflictAt関数と何の違いもありません.
上記の例によれば、反スラッシュにはarr[0][0], arr[1][1]のパターンがある.
すなわち,i値が増加するにつれてパラメータも増加する.
したがって、コードは次のように記述されます.

// hasSlashConflictAt 과 동일하지만 다음만 다르게 한다.

BackSlashColumnIndexAtFirstRow++;

hasAnyBackSlashConflicts

チェス盤にスラッシュ対角線()の衝突がないかどうかを確認します.

충돌 나는 상황 예시


0: (4) [0, 0, 0, 0] 
1: (4) [0, 0, 0, 0] 
2: (4) [1, 0, 0, 0]
3: (4) [0, 1, 0, 0] // 역 대각선에 충돌이 있을 경우

=>  TRUE (충돌이 있다!)

💡 私の解決方法

競合を検出するには、アレイを次のように構成します.

충돌 나는 상황 예시


0: (4) [0, 0, 0, 0, 0, 0]  // arr[0][-2]
1: (4)    [0, 0, 0, 0, 0]  // arr[1][-1]
2: (4)       [1, 0, 0, 0]  // arr[2][0]
3: (4)       [0, 1, 0, 0]  // arr[3][1]

=>  TRUE (충돌이 있다!)

したがって,負の値を関数に渡されるiの値に拡大することによって衝突を検出する.

for (let i = arr.length - 1; i > -arr.length; i--) {
  if (this.hasBackSlashConflictAt(i)) {
    return true;
  }
}

2. solvers.js

findNRooksSolution

nが与えられた場合、n個のrooks問題の答えが返される.

戻り値

はチェス盤の2次元配列を表す.

해답 상황 예시


0: (4) [1, 0, 0, 0] // Rooks 가 충돌나지 않는 경우
1: (4) [0, 1, 0, 0]
2: (4) [0, 0, 1, 0]
3: (4) [0, 0, 0, 1]

💡 私の解決方法

各行、列に2つ以上の1がある場合、rooksは競合します.
したがって、上記の例のように、arr[0][0], arr[1][1]...の方法によって競合を回避する解決策が提供される.

//  1. 솔루션을 담을 배열 생성

let solution = [];

// 2. board 생성

let board = new Board({n});

// 3. board 불러올 변수 생성

let boardRows = board.rows();

// 4. 위에서 설명한 것 처럼 반복문 구성

  for(let i = 0; i < n; i++) {
    boardRows[i][i] = 1;
  }

// 5. 솔루션에 boardRows 담기

solution = boardRows;

countNRooksSolutions

nが与えられた場合,n個のrooks問題の全解数を返す.

の戻り値は整数です.

해답 상황 예시


0: (4) [1, 0, 0, 0] // Rooks 가 충돌나지 않는 경우
1: (4) [0, 1, 0, 0]
2: (4) [0, 0, 1, 0]
3: (4) [0, 0, 0, 1]

💡 私の解決方法

まず問題を解決するために、以下の思考段階を経験した.

Rooks競合を検出できる関数は実装されていますか?

YES, Board.jsではhasAnyRooksConflicts関数が実装されている.

ナビゲーションの順序を設定するにはどうすればいいですか?

ビット関数は、行または列が衝突したときにTrueを返す関数です.したがって,arr[0][0]から1番関数を条件として衝突がなければarr[0][1]の順に探索し,arr[0][1]に衝突があればその列と行は探索する必要がないため,論理をarr[1][1]とする.
(衝突がある場合は下へ、ない場合は横へ)

COUNTはどうしますか?

各行が列と衝突しない場合はcountを行います.つまり、arr[0][0]からarr[3][3]まで回転した後は衝突しなかった.したがって、以下のようにarr[i][매개변수]から매개변수 === boardRows.lengthに至ると、論理はcountとして記述される.

해답 상황 예시


0: (4) [1, 0, 0, 0] 0 // arr[0][4]
1: (4) [0, 1, 0, 0] 0 // arr[1][4]
2: (4) [0, 0, 1, 0] 0 // arr[2][4]
3: (4) [0, 0, 0, 1] 0 // arr[3][4]

function recursion(col){
    if(col === boardRows.length){ 
      solutionCount++
    }
    for(let i = 0; i < boardRows.length; i++){
      boardRows[i][col] = 1 // 먼저 해당 배열의 요소에 1 값을 준다.
      if(!board.hasAnyRooksConflicts()){ // 조건문을 통해 충돌이 없다면
            recursion(col + 1); // 재귀함수를 호출하고 파라미터에 1을 더한값을 넣어준다.
      }
      boardRows[i][col] = 0; // 충돌이 있다면 해당 1 값을 다시 0으로 바꾼다.
    }
  }
 recursion(0) // 파라미터로 0을 전달해서 0부터 [0][0] 부터 탐색할 수 있게 한다.

// 다음은 디버깅 결과의 일부분이다.

boardRows[0][0], count : 0 // 1번 콜스택 저장
boardRows[0][1], count : 0  
boardRows[1][1], count : 0 // 2번 콜스택 저장
boardRows[0][2], count : 0 
boardRows[1][2], count : 0
boardRows[2][2], count : 0 // 3번 콜스택 저장
boardRows[0][3], count : 0
boardRows[1][3], count : 0
boardRows[2][3], count : 0
boardRows[3][3], count : 0
boardRows[0][4], count : 1
boardRows[1][4], count : 1
boardRows[2][4], count : 1
boardRows[3][4], count : 1 // 반복문 모두 종료
boardRows[3][2], count : 1 // 3번 콜스택으로 돌아가서 i에 1이 더해진뒤 다시 탐색을 시작하는 모습 ([2][2] --> [3][2])
boardRows[0][3], count : 1 // ... 반복

これは典型的なDFS構造であり、競合がなければインデックス・サブアイテムのマイニングを継続します.
そして,ここで最も重要なのはcallスタック概念である.サブアイテムのサブアイテムを検索した後に他の検索可能なコンテンツがない場合(重複文の終了)、前のスタックに戻り、他の場所で検索します.この概念を頭の中に描いてこそ、理解しやすい.
(デュアルfor文に似ていますが、再帰的なため、デバッグの先頭が複雑になります)

findNQueensSolution

nが与えられると、n皇后問題の答えが返される.

戻り値

はチェス盤の2次元配列を表す.

💡 私の解決方法

上と似ていますが、チェス盤を返す値で表す2次元配列がほしいです.
以下にコードの一部を加え,各コードの注釈がなぜ存在するのかを簡単に説明したい.

  if (n === 2 || n === 3) { // Queens 는 체스판이 2*2, 3*3 인 경우 충돌할 수 없는 값이 존재하지 않는다. 따라서 위의 값을 입력 받으면 바로 배열을 리턴하도록 한다.
    return boardRows;
  }

    if(col === boardRows.length){
      solution = boardRows;
      return; // [0][4] 일 때 return 을 해줌 (함수 종료) 으로써 나머지 call stack (부모들) 이 실행
      // 안하게 되면 [0][4] 까지 간다음에 나머지 콜스택들이 실행됨
      // 재귀를 탈출하기 위한 조건
    }

    for(let i = 0; i < boardRows.length; i++){
      boardRows[i][col] = 1;
      if(!board.hasAnyQueenConflictsOn(i, col)){ // conflict 안나면 재귀
        recursion(col + 1);
      }
      if(solution !== undefined){ // 나머지 콜 스택은 여기서 걸림 모든 콜 스택을 브레이크 걸어줌으로써 나머지 작업을 아예 종료
        // 이거 안하면 [2][3] 에서 안 끝나고 [3][3] 으로 다시 갈거임 그리고 모든 콜스택이 계속 recursion 을 통해 실행되고 이후 모든것이 conflict 나기 때문에 79번 때문에 결국 모든 값이 0이 될거임
        return; // for 문을 탈출하기 위한 조건
      }
      boardRows[i][col] = 0;
    }

countNQueensSolutions

nが与えられると、n皇后問題のすべての解答個数が返される.

の戻り値は整数です.

💡 私の解決方法

Queensの競合状況とDFSを理解している場合は、countも実現しにくいことは明らかです.