Algorithm - 알고리즘 정리

알고리즘이란?

: 어떠한 문제를 해결하기 위해 사용되는 풀이과정 == 문제해결방법

: 수학과 같이 여러가지 풀이법이 존재함. 프로그래밍 또한 여러가지 풀이법이 존재하나 그 중 가장 효율이 좋은방법 == 알고리즘

: 수학의 공식처럼, 특정형태 및 구조를 갖는 프로그래밍 문제에는 공식화된 알고리즘이 존재함

 

알고리즘의 종류

A) 정렬(Sort)

1) 버블 정렬(Bubble Sort)

: 인접한 두 데이터의 크기를 비교하여 정렬하는 알고리즘

 

2) 선택 정렬(Selection Sort)

: 주어진 데이터 중 최소값을 찾아 순서대로 정렬 하는 알고리즘

: 후보군들 중 최소값을 찾아낸 후, 맨 앞의 데이터와 교체

: 교체된 맨 앞의 데이터를 제외한 나머지 후보군에서 다시 최소값을 찾아냄 → 반복

 

3) 삽입 정렬(Insertion Sort)

: 1번index에 위치한 데이터를 기준으로 해당 데이터의 앞 쪽에 위치한 데이터와 비교.

: 더 작은값을 찾을때까지 데이터를 뒤로 계속 밀어내여 정렬하며 삽입된 데이터보다 작은 데이터를 만날 때까지 반복
: 위와 같이 반복하다 더 없을 경우 0번 index에 위치

 

4) 퀵 정렬(Quick Sort)

: 데이터에서 기준점(Pivot)을 정해서 Pivot보다 작다면 좌측, 크다면 우측에 정렬

: 좌/우로 1차 정렬된 데이터에서 좌/우측 각각의 Pivot을 다시 선정하고 정렬을 수행

: 이 과정을 재귀함수를 사용하여 반복해 최종적으로 정렬된 데이터를 반환

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

5) 병합정렬(Merge Sort)

: 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눔

: 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬함(재귀함수 사용)

: 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

 

B) 탐색(Search)

1) 이진 탐색(Binary Search)

: 탐색할 자료를 반으로 나누어 찾는 데이터가 있을만한 곳을 탐색하는 방법

 

2) 순차 탐색(Sequential Search)

: 데이터가 담겨있는 리스트를 앞에서부터 하나씩 순차적으로 비교하여 원하는 데이터를 찾는 방법

 

 

C) 그래프(Graph)

1) 너비우선탐색(BFS)

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

 

2) 깊이우선탐색(DFS)

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

 

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

: 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘
: 간선(edge)의 가중치 합이 최소인 경로를 찾는 것이 목적
: 최단경로 알고리즘에는 3가지 문제유형이 존재

• 단일출발(single-source) : 특정 노드와 그 외 노드간의 최단경로
• 단일출발 및 단일도착(single-source & single-destination) : 특정 노드 2개의 최단경로
• 전체 쌍(all-pair) : 모든 노드간의 연결조합에 대한 최단경로

 

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

: 최단경로 알고리즘에서 단일출발에 해당

: 첫 정점을 기준으로 연결되어 있는 인접노드를 추가해가며 최단거리를 갱신하는 방법

: 다익스트라 알고리즘 중 가장 개선된 알고리즘이 우선순위 Queue를 활용한 것

 

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

: 신장트리란? 그래프 내부의 모든 노드가 연결되어 있으며, 사이클이 없는(트리의 속성) 그래프

: 최소신장트리란, 간선의 가중치 합이 가장 작은 경로로 이루어진 신장트리를 말함

 

6) 쿼드트리(Quad Tree)

: 자료구조의 트리를 기반으로 자식노드가 4개인 트리

: 3D데이터도 이에 포함이 되며(장면그래프 = Scene Graph), 장면그래프에는 쿼드트리 외에도 이진트리와 옥트리가 존재
: 쿼드트리는 상하개념이 없어서 3차원에서는 4개의 평면으로 분할
: 공간을 재귀적인 호출로 4개의 자식노드로 분할하는 방법

 

D) 문제해결전략(Problem Solving Strategy)

1) 재귀호출(Recursive Call)

: 함수 내부에서 함수가 자기 자신을 또 다시 호출하는 형태
: 재귀함수는 Stack처럼 동작한다고 생각하면 이해가 편하고 오류를 피할 수 있다.

 

2) 동적계획법(Dynamic Programming)

: 하나의 큰 문제를 해결하기 위해서 큰 문제를 작은 문제로 나누어 해결한 후,  작은 문제로부터 계산된 결과값를 이용하여 전체문제를 해결하는 알고리즘

• 상향식 접근법 : 가장 최하위 문제의 답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식 
• 메모이제이션(Memoization) : 프로그램 실행시, 중복되는 연산이 2번 수행되지 않도록 이전에 계산한 값을 저장하여 전체적인 연산실행속도를 빠르게 하는 기술 
• 동적계획법을 사용하는 이유 : 큰 문제를 풀다보면 중복되는 연산이 발생하게 된다. 이 중복연산을 제거하고 재활용하여 전체적인 코드의 수행 및 연산 효율을 증대시키기 위함

 

3) 분할정복(Divide & Conquer)

: 하나의 큰 문제를 해결하기 위해, 작은 문제로 나누어 하위문제를 해결하고 다시 병합하여 상위문제의 답을 얻는 방식

• 하향식 접근법 : 상위 문제의 답을 구하기 위해, 아래로 내려가면서 하위문제의 해답을 먼저 구하는방식
  상위문제의 답을 구하기 위해 이전에 수행해야하는 절차를 수행하는 방식(재귀함수로 구현)
• 동적계획법과 분할정복의 차이점은 나누어진 부분문제에 중복이 없다는 것과 하향식 접근법을 사용하고 메모이제이션기법을 사용하지 않는다는 것