그래프와 탐색

1. 그래프
   • 자료구조에서 그래프란 연결 관계를 말함
   • 연결 관계란 노드(연결 관계를 가진 각 데이터)와 간선(노드간의 관계를 표시하는 선), 인접노드(간선으로 직접 연결된 노드)으로 구성된 형태
   • 그래프는 유방향 그래프(방향이 있는 간선 같고 간선은 단방향 관계를 나타내며 한방향으로 진행 할 수 있다)와 무방향 그래프(방향이 없는 간선) 두가지로 나누어 진다

     • 

   • 그래프 표현 방법(인접행렬, 인접리스트)
     • 인접행렬 : 2차원 배열로 그래프의 연결 관계를 표현
       • graph = [ [False, True, False, False], [True, False, True, False], [False, True, False, True], [False, False, True, False] ]
     • 인접 리스트 : 링크드 리스트로 그래프의 연결 관계를 표현
       • graph = { 0: [1], 1: [0, 2] 2: [1, 3] 3: [2] }
     • 인접행렬과 인접 리스트의 차이는 시공간차이로 입접행렬의 경우 데이터가 차지하는 공간은 크나 검색 시간이 작고 인접 리스트의 경우 데이터가 차지하는 공간은 작으나 검색 시간이 오래 걸리 수도 있다.
2. DFS
   • Depth First Search 약자로 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색
   • 노드를 방문하고 깊이 우선으로 인접한 노드를 방문
   • 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문
   • 만약 끝에 도달했다면 리턴

   • 

3. BFS
   • Breadth-First Search 약자로 인접한 노드를 먼저 탐색하는 방법
   • 현재 인접한 노드 먼저 방문

   • 

4. 백트래킹
   • 필요 없는 경우의 수를 없애므로써 시간 복잡도를 줄이는 방법
   • 대표적인 예로 N-Queen 문제가 있다
     • N-Queen 문제란 N*N 체스판에 N개의 퀸을 배치할 수 있는 경우의 수를 나열하는 문제
     • 퀸은 상하좌우, 대각선 방향으로 거리 제한 없이 이동
     • N=8인 경우, 경우의 수는 다음과 같다.
       • 64 * 63 * ... * 57 = 178,462,987,637,760
       • C 기준 1초에 1억 번을 연산하므로 모든 경우의 수를 탐색하는데 약 20.6시간 이 소요될 것
     • 이렇듯 모든 경우의 수를 넣을 경우 탐색에 시간이 오래 걸리는게 되는데 이를 줄이기 위해서는 필요 없는 경우의 수는 제외시키는 좋다
5. 이진탐색
   • 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법

   • 

   • 1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27 번 안에 찾을 수 있다.