알고리즘

선택정렬

- 데이터 중 가장 작은 값부터 하나씩 선택하여 정렬
- 시간복잡도 -  평균 : O(N^2)     최악 : O(N^2)
- 공간복잡도 -  O(1)
- 안정정렬   -  O

 

삽입정렬

- 데이터를 하나씩 꺼내어 정렬된 자료 중 적합한 위치에 삽입하여 정렬
- 시간복잡도 -  평균 : O(N^2)     최악 : O(N^2)
- 공간복잡도 -  O(1)
- 안정정렬   -  O

 

버블정렬(<= 손코딩으로 할수있는 수준으로 익혀야함)

- 서로 인접한 데이터를 비교하여 정렬
- 시간복잡도 -  평균 : O(N^2)     최악 : O(N^2)
- 공간복잡도 -  O(1)
- 안정정렬   -  O

---

<힙정렬>
- 힙을 이용하여 우선순위가 가장 높은 요소가 가장 마지막 요소와 교체된 후 제거되는 방법을 이용
- 배열에서 연속적인 데이터를 사용하지 않기 때문에 캐시 메모리를 효율적으로 사용할 수 없어 상대적으로 느림
  (캐시 적중률이 낮음)
- 시간복잡도 -  평균 : O(NlogN)   최악 : O(NlogN)
- 공간복잡도 -  O(1)
- 안정정렬   -  X

*힙정렬은 컴퓨터의 하드웨어적이 구조탓에 다른 정렬보다 비교적으로 느릴수 밖에 없다(캐시메모리관련)

 

<병합정렬>
- 데이터를 2분할하여 정렬 후 합병
- 데이터 갯수만큼의 추가적인 메모리가 필요
- 시간복잡도 -  평균 : O(NlogN)   최악 : O(NlogN)
- 공간복잡도 -  O(N)
- 안정정렬   -  O<병합정렬>
- 데이터를 2분할하여 정렬 후 합병
- 데이터 갯수만큼의 추가적인 메모리가 필요
- 시간복잡도 -  평균 : O(NlogN)   최악 : O(NlogN)
- 공간복잡도 -  O(N)
- 안정정렬   -  O

- 수가 적을땐 비효율적이다.

 

<퀵정렬>
- 하나의 피벗을 기준으로 작은값과 큰값을 2분할하여 정렬(왼쪽, 오른쪽이 만날때 까지 큰값 작은값 정렬하면서 만난다)
- 최악의 경우(피벗이 최소값 또는 최대값)인 경우 시간복잡도가 O(N^2)
- 시간복잡도 -  평균 : O(NlogN)   최악 : O(N^2)
- 공간복잡도 -  O(1)
- 안정정렬   -  X

- 다른 정렬보다 빠름

 

<하이브리드 정렬>

- 여러 정렬을 섞어서 사용하는 알고리즘

- c#은 인트로정렬, 파이썬은 팀정렬

---

안정정렬과 불안정정렬

- 안정정렬 : 중복값에 대해 기존의 정렬된 상태를 유지한채로 정렬이 이뤄짐.

- 불안정정렬 : 안정정렬과는 반대로 중복값이 정렬된 상태를 유지하지 않고 정렬 순서가 바뀜.

 

---

선형자료구조 탐색 알고리즘

1. 순차탐색

- 모든 선형자료구조는 순차탐색이 가능

 

2. 이진탐색

- 정렬한후 또는 정렬이 보장된 자료구조는 이진탐색이 가능함.

 

---

비선형자료구조 탐색 알고리즘

 

1.  그래프 (Graph)
 - 정점의 모음과 이 정점을 잇는 간선의 모음의 결합
 - 한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 순환구조를 가짐
 - 간선의 방향성에 따라 단방향 그래프, 양방향 그래프가 있음
 - 간선의 가중치에 따라   연결 그래프, 가중치 그래프가 있음

 

<인접행렬 그래프>
-  그래프 내의 각 정점의 인접 관계를 나타내는 행렬
-  2차원 배열을 [출발정점, 도착정점] 으로 표현
-  장점 : 인접여부 접근이 빠름
-  단점 : 메모리 사용량이 많음

 

<깊이 우선 탐색 (Depth-First Search)>
   - 그래프의 분기를 만났을 때 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 다음 분기를 탐색

   - 스택구조의 함수재귀호출구조로 탐색을 쓴다

   

 

 

<너비 우선 탐색 (Breadth-First Search)>
- 그래프의 분기를 만났을 때 모든 분기를 저장한 뒤, 저장한 분기를 하나씩 탐색

- 큐를 이용해 탐색을하는게 대부분이다.

---

다익스트라 알고리즘 (Dijkstra Algorithm)
 (최단경로 알고리즘)
 - 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구함
 - 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 후, 해당 노드를 거쳐 다른 노드로 가는 비용 계산

1. 방문(탐색)하지 않은 정점 중 가장 가까운 정점부터 탐색

2. 직접연결된 거리보다 거친거리가 더 짧아진다면 갱신.

---

AStart알고리즘
 - 다익스트라 알고리즘을 확장하여 만든 최단경로 탐색알고리즘
 - 경로 탐색의 우선순위를 두고 유망한 해부터 우선적으로 탐색

1. 목적지의 방향이 정해진 다면 반대방향의 노드들은 나중에 선택하고 목적지 방향 노드(유망한 노드)를 우선선택하는 식으로 탐색을 진행한다.

 

f : 총 소요시간( g+h )

g : 지금까지 온 거리 

h : 예상거리

 

휴리스틱 (Heuristic) : 최상의 경로를 추정하는 순위값, 휴리스틱에 의해 경로탐색 효율이 결정됨

- 맨해튼 거리 : 직선을 통해 이동하는 거리

- 유클리드 거리 : 대각선을 통해 이동하는 거리

-  타일맵용 유클리드 거리 : 직선과 대각선을 통해 이동하는 거리