알고리즘

Alogorihm == 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한것.

알고리즘의 조건

• 입력: 제공되는 자료가 0개 이상 존재해야 한다.
• 출력: 입력되는 자료에 따라 다른 결과를 내어야 한다.
• 명확성: 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성: 유한 번의 명령어를 수행하고 유효 시간 내에 종료되어야 한다.
• 효율성: 모든 과정은 명백하게 실행 가능한 것이어야 한다.

알고리즘의 선택기준

• 정확성: 입력에 대해 유한 시간내에 올바른 답을 산출하는가를 판단.
• 작업량(최적성): 입력된 자료의 크기&종류에 따라 가장 적은 작업량을 가졌는지 판단.
• 용량: 작업에 필요한 저장공간.
• 시간복잡도: 알고리즘이 소모하는 시간과 메모리 크기에 따라 소모되는 비용.(시간 복잡도와 공간 복잡도의 비례치를 계산).

*Big-O 표기법

• O(1): 입력 자료의 수에 관계없이 일정한 실행 시간을 가짐.
• O(log N): 입력 자료의 크기가 N일 경우 log2N 번 만큼의 수행시간을 가짐.
• O(N): 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가짐.
• O(N log N): 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가짐.
• O(N2): 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가짐.
• O(N3): 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가짐.
• O(2n): 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가짐.
• O(n!): 입력자료의 크기가 N일경우 n(n-1)(n2)...*1(n!) 번만큼의 수행시간을 가짐.

알고리즘의 분류
정렬(Sort)

1. 버블 정렬(Bubble)
   • 인접한 두 데이터의 크기를 비교하여 정렬하는 알고리즘.
2. 선택 정렬(Selection)
   • 주어진 데이터중 최소값을 찾아 순서대로 정렬하는 알고리즘.
   • 자료 중 최소값을 찾아낸 후, 맨 앞의 데이터와 교체한다.
   • 교체된 데이터를 제외한 나머지ㅏ 후보군에서 다시 최소값을 찾아낸다.
3. 삽입 정렬(Insertion)
   • 1번 index에 위치한 데이터를 시작으로 0번 index에 있는 데이터와 비교한다.
   • 더 작은 값을 찾을 때까지 데이터를 뒤로 밀어내어 정렬하는 알고리즘.
   • 삽입된 데이터보다 작은 데이터를 만날 때까지 반복한다. 없는 경우 0번 index에 위치하게 된다.
4. 퀵 정렬(Quick)
   • 데이터에서 기준점(pivot)을 정하여 pibot보다 작으면 좌측, 크면 우측에 정렬한다.
   • 좌/우측으로 정렬된 데이터에서 좌/우측의 pibot을 다시 선정하고 정렬을 수행한다.
   • 이 과정을 재귀함수로 반복하여 데이터를 정렬한다.
5. 병합 정렬(Merge)
   • 분할 정복 알고리즘을 기반한 정렬이며, 재귀함수를 사용한다.
   • 자료를 절반으로 자르고 비슷한 크기의 두 부분 리스트로 나눈다.
   • 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
   • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

탐색(Search)

1. 이진 탐색(Binary Search)
   • 탐색할 자료를 반으로 나누어 찾는 데이터가 있을만한 곳을 탐색하는 방법.
   • 데이터가 정렬되어 있어야 가능하다.
2. 순차 탐색(Sequential Search)
   • 데이터가 담겨있는 자료를 앞에서부터 하나씩 순차적으로 비교하여 데이터를 찾는 방법.

그래프(Graph)

1. 너비우선탐색(BFS)

   • 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식.
     

2. 깊이우선탐색(DFS)

   • 정점(노드)의 자식노드를 먼저 탐색하는 방식.
     

3. 최단경로 알고리즘(Shortest Path Algorithm)

   • 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘.
   • 간선(edge)의 가중치 합이 최소인 경로를 찾는 것이 목적이다.
   • 최단경로 알고리즘의 3가지 유형.
     - 단일출발(single-source): 특정 노드와 그 외 노드간의 최단경로
     • 단일출발 및 단일도착(single-cource & single-destination): 특정 노드 2개의 최단경로.
     • 전체 쌍(all-pair): 모든 노드간의 연결조합에 대한 최단경로.

4. 다익스트라 알고리즘(Dijikstra Algorithm)

   • 최단경로 알고리즘에서 단일출발에 해당한다.
   • 첫 정점을 기준으로 연결되어 있는 인접노드를 추가해가며 최단거리를 갱신하는 방법이다.
   • 다익스트라 알고리즘 중 가장 개선된 알고리즘이 우선순위 Queue를 활용한 것이다.

5. 최소신장트리 알고리즘(Mnimum Spanning Tree)

   • 신장트리란, 그래프 내부의 모든 노드가 연결되어 있으며, 사이클이 없는(트리의 속성) 그래프를 말한다.
   • 최소신장트리란, 간선의 가중치 합이 가장 작은 경로로 이루어진 신장트리를 말한다.

6. 크루스칼 알고리즘(Kruskal's Algorithm)

   • 대표적인 최소신장트리 알고리즘으로, 탐욕 알고리즘을 기반하여 선택과 결정을 하는 방식.
   • 모든 간선의 가중치를 오름차순으로 정렬 후 가장 낮은 가중치를 갖는 간선부터 모든 노드를 연결하며 MST를 찾는다.
   • 사이클의 유무를 판단하기 위해 Union-find 알고리즘을 사용한다.

7. 프림 알고리즘(Prim's Algorithm)

   • 크루스칼 알고리즘과 마찬가지로 대표적인 최소신장트리 알고리즘이며 탐욕 알고리즘을 기반으로 한다.
   • 어떤 노드와 인접한 노드의 간선만을 대상으로 하여, 인접노드 중에서 간선의 가중치가 가장 작은 간선을 선택하여 해당 인접노드를 연결하는 방식으로 MST를 찾는다.

8. 개선된 프림 알고리즘(Improved Prim's Algorithm)

   • 개선된 프림 알고리즘은 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식이다.
   • 그래프는 노드보다 간선의 수가 더 많기 때문에 그차이 만큼 반복연산이 줄어들어 시간복잡도가 개선되었다.