알고리즘 총 정리

알고리즘

알고리즘은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것으로,

문제풀이에 필요한 계산절차 또는 처리과정의 순서를 의미한다
알고리즘의 중요한 특징은 같은 지식수준을 가진 사람이라면 그 알고리즘을 보고 누구나 같은 결과를 낼 수 있어야한다

 

 

 

 

 

알고리즘의 조건

- 입력: 외부에서 제공되는 자료가 0개 이상 존재한다

- 출력: 적어도 2개 이상의 서로다른 결과를 내어야 한다 (모든 입력에 하나의 출력이 나오면 안된다)

- 명확성: 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다

- 유한성: 유한 번의 명령어를 수행 후 유한 시간 내에 종료한다

- 효율성: 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다

 

 

 

 

좋은 알고리즘의 기준

- 정확성: 적당한 입력에 대해 유한 시간내에 올바른 답을 산출하는가를 판단

- 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정

- 기억장소 사용량: 수행에 필요한 저장 공간을 적게 사용

- 최적성: 더 적은 연산을 수행하는 알고리즘

- 복잡도 (점근 표기법 (Big-O Notation)): 알고리즘이 소모하는 소요시간과 메모리 사용량

 

 

 

 

 

알고리즘의 분류

- 정렬 (sort)

- 탐색 (Search)

- 그래프 (Graph)

 

 

 

 

알고리즘 문제 해결 전략

- 재귀 호출

함수 안에서 해당 함수가 호출되는 형태

 

- 동적 계획법

하나의 큰 문제를 해결하기 위해서 큰 문제를 작은 문제로 나누어 해결한 후 작은 문제로부터 계산된 결과 값을 이용하여 전체 문제를 해결

> 상향식 접근법 (가장 최하위 문제의 답을 구한 후 이를 이용하여 상위 문제를 풀어나가는 방식)

> 메모이제이션 (프로그램 실행 시 중복되는 연산이 2번 실행되지 않도록 이전에 계산한 값을 저장하여 전체적인 연산 실행 속도를 빠르게 하는 기술)

 

- 분할 정복

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

> 하향식 접근법 (상위 문제의 답을 구하기 위해 아래로 내려가면서 하위 문제의 답을 먼저 구하는 방식. 재귀함수로 구현)

> 동적계획법과 달리 나누어진 부분 문제에 중복이 없음

 

- 탐욕 알고리즘

최적의 해에 가까운 값을 구하기 위해 사용하는 알고리즘

여러가지 경우 중 하나를 결정해야할 때 상황에 따라 매순간 최선의/최적의 선택을 하여 최종적인 값을 구하는 방식

 

- 백트래킹 (퇴각 검색)

제약조건 만족 문제에서 해를 찾기 위한 전략

해를 찾기 위해서 어떤 후보군을 대상으로 제약조건을 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단되면 그 즉시 backtrack(다시는 해당 후보군을 체크하지 않을 것을 표시)한 후, 다른 후보군으로 넘어가는 방식

백트래킹에 의해 연산의 대상이 되는 후보군이 적어지고 그만큼 시간복잡도가 크게 줄어들어 빠르게 최적의 해를 구할 수 있다

 

 

 

 

 

 

정렬 - 버블 정렬

서로 인접해있는 요소 간의 대소 비교를 통해 정렬

가장 단순한 알고리즘으로 단순한 만큼 비효율적이다

 

- 시간 복잡도

최고, 평균, 최악 모두 O(n^2)

 

- 공간 복잡도

하나의 배열만 사용하여 O(n)

 

 

 

 

 

 

정렬 -  삽입 정렬

정렬을 진행할 원소의 index 보다 낮은 곳에 있는 원소들을 탐색하여 알맞은 위치에 삽입

낮은 원소를 탐색해야하기 때문에 두번 째 index 부터 시작

알고리즘이 동작하는 동안 계속해서 정렬이 진행되기 떄문에 반드시 맨 왼쪽까지 탐색하지 않아도 된다는 장점이 존재

 

- 시간 복잡도

O(n)

 

- 공간 복잡도

O(n)

 

 

 

 

 

 

정렬 -  선택 정렬

배열에서 최소 값을 반복적으로 찾아 정렬

 

- 시간 복잡도

최선, 평균, 최악 모두 O(n^2)

 

- 공간 복잡도

O(n)

 

 

 

 

 

 

정렬 -  퀵 정렬

분할 정복법과 재귀를 사용해 정렬

정렬될 기준 원소를 뜻하는 피봇 (pivot)이라는 개념을 사용

피봇 선택 방법에 따라 퀵 정렬의 성능이 달라지는데, 최적의 피봇 선택이 어려우므로 임의 선택을 해야함

보통 배열의 첫 번째 값이나 중앙 값을 선택

 

 

 

 

 

 

정렬 -  병합 정렬

분할정복과 재귀 알고리즘을 사용

퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가짐

그러나 퀵 정렬과 달리 배열을 원소가 하나만 남을때까지 이분할 한 다음 대소 관계를 고려하여 재배열하여 원래 크기의 배열로 병합

 

 

 

 

 

 

 

정렬 -  힙 정렬

힙이란 트리 기반의 자료구조로, 두개의 노드를 가진 완전 이진 트리를 의미

따라서 힙 정렬은 완전 이진 트리를 기반으로 하는 정렬 알고리즘

힙은 최대 힙과 최소 힙으로 나누며, 최대 힙은 내림차순 정렬에, 최소 힙은 오름차순 정렬에 사용

 

 

 

 

정렬 -  셸 정렬

삽입 정렬의 단점을 보완하기 위해 도입된 알고리즘

주어진 정렬 상태가 역순으로 배열되어 있을 수록 비교횟수가 늘어남

간격(interval)이라는 개념을 사용하며 간격은 비교할 원소 간의 간격을 의미

비교 횟수를 줄이기 위해 interval은 큰 값에서 작은 값으로 낮춰짐

 

- 시간 복잡도 

평균 O(n^1.25~1.5)

 

 

 

 

 

정렬 -  기수 정렬

non-comparison 알고라즘으로 원소간의 대소 비교를 하지 않고 정렬

정렬하고자 하는 수의 낮은 자리 수를 차례대로 확인하여 정렬

정렬을 위해 총 10개의 queue를 사용

 

 

 

 

 

 

 

 

정렬 -  카운팅 정렬

이름 그대로 배열에 존재하는 원소 별 개수를 세어 정렬하는 방식

버블, 선택, 힙, 병합, 퀵, 삽입 알고리즘의 시간 복잡도를 O(n) 수준으로 낮추기 위해 도입

 

 

 

 

 

 

 

 

 

탐색 - 이진 탐색

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

 

 

 

 

 

탐색 - 순차 탐색

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

 

 

 

 

 

 

 

 

그래프 - 너비 우선 탐색 (BFS)

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

 

 

 

 

 

 

 

그래프 - 깊이 우선 탐색 (DFS)

노드의 자식 노드를 먼저 탐색하는 방식

 

 

 

 

 

 

 

그래프 - 최단 경로 알고리즘

그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘

간선의 가중치 합이 최소인 경로를 찾는 것을 목적으로함

 

- 단일 출발

특정 노드와 그 외 노드 간의 최단 경로

 

- 단일 출발 및 단일 도착

특정 노드 2개의 최단 경로

 

- 전체 쌍

모든 노드 간의 연결 조합에 대한 최단 경로

 

 

 

 

 

 

그래프 - 다익스트라 알고리즘

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

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

 

 

 

 

 

 

 

 

그래프 - 최소 신장 트리 알고리즘 (MST)

신장트리 (그래프 내부의 모든 노드가 연결되어 있으며 사이클이 없는 그래프) 중에서 간선의 가중치 합이 가장 작은 경로로 이루어진 트리

 

 

 

 

 

 

 

그래프 - 크루스칼 알고리즘

대표적인 최소 신장 트리 알고리즘으로, 탐욕 알고리즘을 기반하여 선택과 결정을 수행

모든 간선의 가중치를 오름차순으로 정렬 후 가장 낮은 가중치를 갖는 간선부터 모든 노드를 연결하며 MST를 탐색

사이클의 유무를 판단하기 위해 Union-Find 알고리즘을 사용

 

 

 

 

 

 

 

그래프 = 프림 알고리즘

크루스칼 알고리즘과 마찬가지로 대표적인 최소 신장 트리 알고리즘이며 탐욕 알고리즘을 기반으로 함

어떤 노드와 인접한 노드의 간선만을 대상으로 하여, 인접 노드 중에서 간선의 가중치가 가장 작은 간선을 선택하여 해당 인접 노드를 연결하는 방식으로 MST를 탐색

 

 

 

 

 

 

 

 

 

 

 

Reference

[알고리즘] 알고리즘 #0 - 알고리즘이란? 종류와 의미

[자료구조] 기본 정렬 알고리즘 총 정리