순차탐색, 이진탐색, 그래프

순차 탐색

• 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것
• 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법
• 데이터 크기에 따라 효율이 다르기 때문에 데이터가 많다면 비효율적인 방법
• 최악 : O(n)

이진 탐색

• 데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 비교할 때마다 탐색 범위를 반으로 줄이면서 특정한 값의 위치를 찾는다
• 분할 정복 알고리즘 - 리스트 개수 0,1개일 때 처리하고 2개 이상일 때 재귀 호출로 구현
• 동작 방식
  
  1. 배열의 중간 값을 가져온다.
  2. 중간 값과 검색 값을 비교한다.
     1. 중간 값이 검색 값과 같다면 종료 (mid=key)
     2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key)
     3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다. (mid > key)
  3. 값을 찾거나 간격이 비어있을 때까지 반복한다.
• 데이터 전체를 탐색하는 순차 탐색보다 빠르다.
• 평균 : O(logN)

그래프

- 정점(vertex) = 노드(node), 간선(Edge)으로 구성된 자료구조

- 노드(node) or 정점(vertex) : 데이터가 저장되는 곳

- 간선 : 노드를 이은 선, link or branch라고도 부른다.

- 인접 정점 :간선으로 연결된 정점

- 정점의 차수 : 하나의 정점에 인접한 정점의 수

- 진입 차수 : 외부에서 오는 간선의 수

- 진출 파수 : 외부로 향하는 간선의 수

- 경로 길이 : 경로를 구성하기 위해 구성한 간선의 수

- 단순 경로 : 처음 정점, 끝 정점을 제외하고 중복된 정점이 없는 경로(A -> B -> C)(ex: 한붓그리기)

- 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 종류

- 무방향 : 정점을 연결하는 간선에 방향이 없는 것

- 방향 : 정점을 연결하는 간선에 방향이 있는 것

- 가중치 : 간선에 가중치(비용)가 있는 것으로 이동할 때 비용이 드는 그래프

- 연결과 비연결 : 모든 노드에 경로가 존재하는지(연결) 없는지(비연결) 차이

- 사이클과 비순환 : 시작, 종료 노드가 동일하거나(사이클) 다르거나(비순환)

- 완전 : 모든 노드가 서로 연결

그래프와 트리의 차이

- 트리는 그래프 중에 속한 특별한 종류

그래프와 트리의 차이

그래프의 구현 방식

인접 리스트

• 각각 정점에 인접한 정점들을 리스트로 표현

인접 행렬

• NxN Boolean 행렬로 표현, matrix [i][j]가 true면 i -> j 간선이 있다는 뜻이다.