꾸준2

ㄴㄴ

깊이 우선 탐색(DFS)

• 루트 정점 혹은 임의의 정점에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘
• 즉, 넓게 탐색하기 전에 깊게 탐색합니다.
• 스택 혹은 재귀함수를 통해 구현합니다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느립니다.

사용 예 )

• 모든 정점을 방문해야 할 때
• 가중치가 있는 간선을 이동할 때 혹은 여러 제약이 있을 경우 
• 미로를 탐색 할 때 한 방향으로만 갈 수 있을때 까지 가보고 틀리다면 다시 가장 가까운 지름길을 찾을 때

방향성 그래프

code

// ----------------------- 방향 그래프 코드 -----------------------

function directedGraph() {
  this.edges = {};
}

directedGraph.prototype.addVertex = function(vertex) {
  this.edges[vertex] = {}
}

directedGraph.prototype.addEdge = function(goVertex, stopVertex, weight) {
  if(weight == undefined) {
    weight = 0
  }
  this.edges[goVertex][stopVertex] = weight;
}

directedGraph.prototype.removeEdge = function(goVertex, stopVertex) {
  if(this.edges[goVertex] && this.edges[goVertex][stopVertex] != undefined) {
    delete this.edges[goVertex][stopVertex];
  }
}

directedGraph.prototype.removeVertex = function(vertex) {
  for(var allEdge in this.edges[vertex]) {
    this.removeEdge(allEdge, vertex);
  }
  delete this.edges[vertex]
}


// ----------------------- DFS 탐색 코드 -----------------------

directedGraph.prototype.traverDFS = function(vertex) {
  var visited = {}
  this._traverDFS(vertex, visited);
}

directedGraph.prototype._traverDFS = function(vertex, visited) {
  visited[vertex] = true;
  console.log(vertex, '방문 완료')
  for(var nextVertex in this.edges[vertex]) {
    if(!visited[nextVertex]) {
      this._traverDFS(nextVertex, visited);
    }
  }
}



// ----------------------- 방향 그래프 정점,간선 추가 -----------------------
var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('B')
graph2.addVertex('C')
graph2.addVertex('D')
graph2.addVertex('E')

graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('B', 'D', 2)
graph2.addEdge('D', 'E', 5)

console.log(graph2.edges)
  //         A
  //    B
  // C     D
  //     E

// ----------------------- DFS A 탐색 -----------------------
graph2.traverDFS('A')
// A 방문 완료
// B 방문 완료
// C 방문 완료
// D 방문 완료
// E 방문 완료

// ----------------------- DFS B 탐색 -----------------------
graph2.traverDFS('B')
// B 방문 완료
// C 방문 완료
// D 방문 완료
// E 방문 완료

// ----------------------- DFS C 탐색 -----------------------
graph2.traverDFS('C')
// C 방문 완료

// ----------------------- DFS D 탐색 -----------------------
graph2.traverDFS('D')
// D 방문 완료
// E 방문 완료

// ----------------------- DFS E 탐색 -----------------------
graph2.traverDFS('E')
// E 방문 완료

설명

// ----------------------- DFS 탐색 코드 -----------------------
// (1) - 방문중인 정점
// (2) - 모든 정점 방문 했는지 안했는지 여부
//       true => 방문 완료, undefined => 방문 미완료
// (3) - 방문중인 정점에 인접정점

// 설명
// 방문중인 정점에 방문했다고 visited객체에 true로 저장한다
// 방문중인 정점에 인접정점을 찾고 해당 인접정점이 방문이 미완료일 경우
// 재귀함수를 이용하여 인접정점을 방문한다.
// 재귀함수를 통해 호출되기때문에 다음 분기를 넘어가기 전에 해당 분기를 가장 깊게 탐색한다

// 데이터 상황
// {
//   A: { B: 1, Q: 5 },
//   Q: { P: 5, R: 5 },
//   P: {},
//   R: {},
//   B: { C: 1, D: 2 },
//   C: { CC: 1 },
//   CC: { ccc: 1, CCC: 1 },
//   CCC: {},
//   ccc: {},
//   D: { E: 5 },
//   E: {}
// }

// 현재 데이터 상황 그림으로 표현
  //              A
  //           B       Q
  //       C     D  P   R
  //    CC     E
  //  ccc CCC


directedGraph.prototype.traverDFS = function(vertex) {
  var visited = {}
  this._traverDFS(vertex, visited);
}

directedGraph.prototype._traverDFS = function(vertex, visited) {
  visited[vertex] = true; // 방문 중인 정점 체크(true)로 하기
  console.log(vertex, '방문 완료') // (1)
  for(var checkVisited in this.edges) {
    console.log(checkVisited, '의 방문 상태 =>', visited[checkVisited]) // (2)
  }

  for(var nextVertex in this.edges[vertex]) {
    console.log('인접 정점 : ', this.edges[vertex]) // (3)
    console.log("")
    if(!visited[nextVertex]) {
      this._traverDFS(nextVertex, visited);
    }
  }
}



// ----------------------- 방향 그래프 정점,간선 추가 -----------------------
var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('Q')
graph2.addVertex('P')
graph2.addVertex('R')
graph2.addVertex('B')
graph2.addVertex('C')
graph2.addVertex('CC')
graph2.addVertex('CCC')
graph2.addVertex('ccc')
graph2.addVertex('D')
graph2.addVertex('E')

graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('C', 'CC', 1)
graph2.addEdge('CC', 'ccc', 1)
graph2.addEdge('CC', 'CCC', 1)
graph2.addEdge('B', 'D', 2)
graph2.addEdge('D', 'E', 5)
graph2.addEdge('A', 'Q', 5)
graph2.addEdge('Q', 'P', 5)
graph2.addEdge('Q', 'R', 5)

console.log(graph2.edges)


// ----------------------- DFS A 탐색 -----------------------
graph2.traverDFS('A')
// A 방문 완료
// B 방문 완료
// C 방문 완료
// CC 방문 완료
// ccc 방문 완료
// CCC 방문 완료
// D 방문 완료
// E 방문 완료
// Q 방문 완료
// P 방문 완료
// R 방문 완료

// ----------------------- DFS B 탐색 -----------------------
// graph2.traverDFS('B')
// B 방문 완료
// C 방문 완료
// CC 방문 완료
// ccc 방문 완료
// CCC 방문 완료
// D 방문 완료
// E 방문 완료

// ----------------------- DFS Q 탐색 -----------------------
// graph2.traverDFS('Q')
// Q 방문 완료
// P 방문 완료
// R 방문 완료

// ----------------------- DFS C 탐색 -----------------------
// graph2.traverDFS('C')
// C 방문 완료
// CC 방문 완료
// ccc 방문 완료
// CCC 방문 완료

// ----------------------- DFS D 탐색 -----------------------
// graph2.traverDFS('D')
// D 방문 완료
// E 방문 완료

참고
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/BFS%20%26%20DFS.md
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

너비 우선 탐색(BFS)

• 루트 정점 혹은 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 알고리즘입니다.
• 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색합니다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있게 큐(Queue)를 사용했습니다.
• 사용예 : 두 노드 간의 최단 경로, 임의의 경로를 찾고 싶을 때

code

// ----------------------- 방향 그래프 코드 -----------------------

function directedGraph() {
  this.edges = {};
}

directedGraph.prototype.addVertex = function(vertex) {
  this.edges[vertex] = {}
}

directedGraph.prototype.addEdge = function(goVertex, stopVertex, weight) {
  if(weight == undefined) {
    weight = 0
  }
  this.edges[goVertex][stopVertex] = weight;
}

directedGraph.prototype.removeEdge = function(goVertex, stopVertex) {
  if(this.edges[goVertex] && this.edges[goVertex][stopVertex] != undefined) {
    delete this.edges[goVertex][stopVertex];
  }
}

directedGraph.prototype.removeVertex = function(vertex) {
  for(var allEdge in this.edges[vertex]) {
    this.removeEdge(allEdge, vertex);
  }
  delete this.edges[vertex]
}






// ----------------------- BFS 탐색 코드 -----------------------

directedGraph.prototype.travelBFS = function(vertex) {
  var queue = [];
  var visited = {};

  queue.push(vertex)

  while(queue.length) {
    vertex = queue.shift();
    if(!visited[vertex]) {
      visited[vertex] = true;
      console.log(vertex, '방문 완료')
      for(var nextVertex in this.edges[vertex]) {
        queue.push(nextVertex);
      }
    }
  }
}




// ----------------------- 방향 그래프 정점,간선 추가 -----------------------
var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('B')
graph2.addVertex('C')

graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('C', 'A', 1)

console.log(graph2.edges)
// { A: { B: 1 }, B: { C: 1 }, C: { A: 1 } }
// 위의 객체 설명
// A -> B
// B -> C
// C -> A



// ----------------------- BFS A 탐색 -----------------------
graph2.travelBFS('A')
// A 방문 완료
// B 방문 완료
// C 방문 완료

// ----------------------- BFS B 탐색 -----------------------
graph2.travelBFS('B')
// B 방문 완료
// C 방문 완료
// A 방문 완료

// ----------------------- BFS C 탐색 -----------------------
graph2.travelBFS('C')
// C 방문 완료
// A 방문 완료
// B 방문 완료

설명

// ----------------------- BFS 탐색 코드 -----------------------

// (while문)
//  1) 해당 정점 탐색 후 삭제
//  2) 해당 정점의 인접 정점 탐색 준비
//  3) queue.length > 0 일때까지 반복

// 1. queue배열에 해당 정점 추가
// 2. vertex에 해당 정점 저장 후 queue배열에서 해당 정점 삭제
// 3. visited객체에 해당 정점(vertex)이 탐색 됐는지 확인
//    1) 탐색 안했을 경우 => visited객체에 해당 정점값을 true로 바꾸고 인접 정점 탐색 시작 (queue배열에 인접 정점 추가하고 1번으로 돌아가 반복)
//    2) 탐색 했을 경우 => 모든 정점 방문 종료!!!

directedGraph.prototype.travelBFS = function(vertex) {
  var queue = [];
  var visited = {};

  queue.push(vertex)

  while(queue.length) {
    vertex = queue.shift();
    if(!visited[vertex]) {
      visited[vertex] = true;
      console.log(vertex, '방문 완료')
      for(var nextVertex in this.edges[vertex]) {
        queue.push(nextVertex);
      }
    }
  }
}

탐욕 알고리즘(Greedy Algorithm)

• 탐욕적이다 => 근시안적으로 의사 결정을 내리지만 최선이길 바라는 알고리즘입니다.
• 즉, 각 단계에서 최선의 선택을 하는 알고리즘
• 굳이 최적의 답을 구하려고 노력하지 않고 적당히 괜찮은 답을 찾으려고 합니다.

구성 요소

• 해 선택(Selection Procedure) : 현재 상황에서 가장 최선의 후보를 선택
• 적절성 검사(Feasibility Check) : 선택된 후보가 답이 될 수 있는지 제약 사항 검사
• 해 검사(Solution Check) : 현재까지 선택된 해가 문제의 정답이 되었는지 검사하고 정답이 아니라면 다시 시작

장점

최적의 답을 구하는 알고리즘보다 계산이 단순하고 시간이 적게 걸립니다.

단점

항상 최적의 답을 구해주는 것은 아니기때문에 상황에 맞게 적절히 사용해야합니다.

예시)

동전 거스름돈

// cost : 거스름돈
// coin : 동전 종류
// count : 거스름돈 동전 {종류 : 갯수}

function changeCoin(cost, coin) {
  count = {}
  while(cost>0) {
    for(var i=0; i<coin.length; i++) {
      if(cost/coin[i] >= 1) {
        count[coin[i]] = Math.floor(cost/coin[i])
        cost = cost%coin[i]
      }
    }
  }
  return count
}

console.log(changeCoin(570,[100, 50, 10]))
// { '10': 2, '50': 1, '100': 5 }

최적의 답을 구하지 않는 예시

조건 : 최소한의 동전 개수를 이용하여 거스름돈을 만들어라

function changeCoin(cost, coin) {
  count = {}
  while(cost>0) {
    for(var i=0; i<coin.length; i++) {
      if(cost/coin[i] >= 1) {
        count[coin[i]] = Math.floor(cost/coin[i])
        cost = cost%coin[i]
      }
    }
  }
  return count
}

console.log(changeCoin(800,[500, 160, 100, 10]))

// changeCoin함수 실행 결과
// { '10': 4, '100': 1, '160': 1, '500': 1 }

// 최적의 답
// { '100': 3, '500': 1 }

탐욕 알고리즘을 이용한 정답 :  7개 

최적의 정답 : 4개

결론

상황에 맞게 잘 쓰자