Algorithm_Repository (Using cpp & JavaScript)

Greedy

현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 대표 문제 거스름돈
  • https://www.acmicpc.net/problem/5585

DFS(Depth First Search, 깊이 우선 탐색)와 BFS

DFS = 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 장점

  • 현재 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적으로 적다.
  • 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
  • 구현이 너비 우선 탐색(BFS)보다 간단함

• 단점

  • 검색 속도가 너비 우선 탐색(BFS)보다 느림
  • 해가 없는 경우에 빠질 가능성이 있음
  • 최단 경로가 된다는 보장이 없음

BFS = 특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 장점

  • 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작
  • DFS보다 빠름
  • 최단 경로임을 보장
  • 해가 없는 경우에 빠질 일이 없다.

• 단점

  • 재귀 호출의 DFS와는 달리 큐에 다음 탐색할 정점들을 저장해야하므로 저장공간이 많이 필요하다.
  • 노드의 수가 늘어나면 탐색해야되는 노드 또한 많아지기에 비현실적이다.

• 대표 문제 DFS와 BFS

  • https://www.acmicpc.net/problem/1260

Backtracking

가능한 모든 방법을 탐색한다. 대표적으로 DFS(Depth First Search, 깊이 우선 탐색)가 있다.

  DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동하는 것으로
  무한히 깊은 곳을 찾아야할 때 효과적이다. 굳이 목표지점이 있지 않는 경로를 탐색한다는 비효율성이 존재한다.
  따라서 이러한 비효율성을 차단하고 목표지점에 갈 수 있는 가능성을 검사하는 방법이 Backtracking 알고리즘이다.
  DFS에 가지치기(Pruning)를 통해 가지 않아도 되는 루트를 고려하는 완전탐색 기법이다.

• 대표 문제 N-Queen
  • https://www.acmicpc.net/problem/9663