코테

알고리즘의 종류

sungtt 2022. 11. 27. 09:34

스택과 큐

스택

한쪽이 막혀있는 구조라 생각하면 된다.

먼저 들어온 값이 나중에 나가는 선입후출. FILO(First-In-Last-Out)

 

큐

양쪽이 뚫려있는 구조라 생각하면 된다.

먼저 들어온 값이 먼저 나가는 선입선출. FIFO(First-In-First-Out)

 

우선순위 큐

가장 우선순위가 높은 데이터

 

팩토리얼

1부터 n까지의 자연수를 차례대로 곱하는것을 팩토리얼이라 한다.

n! = 1 x 2 x 3 ... ( n - 1 ) x n

수학적으로 0!과 1!의 값은 1이다.

 

유클리드 호제법

두 개의 자연수에 대한 최대공약수(GCD)를 구하는 알고리즘 (*최대공약수 : 두 자연수의 공통된 약수중에서 가장 큰 수)

두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 했을 때

A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 

 

알고리즘의 종류

1. 그리디 알고리즘

현재 놓여진 상황에서 최선의 상황만을 택하는 알고리즘

 

2. DFS (Depth-First Search)

깊이 우선 탐색이라고도 부른다.

깊은 부분을 우선적으로 탐색하는 알고리즘

스택 자료구조(혹은 재귀함수)를 이용한다.

노드 탐색을 시작했을 때 그래프의 깊은 부분까지 들어가는것을 우선하며 탐색하는 것

 

3. BFS (Breadth-First Search)

너비 우선 탐색이라고도 부른다.

가장 가까운 노드부터 우선적으로 탐색한다.

큐 자료구조를 이용한다.

 

4. 정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.

 

- 선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는것을 반복한다.

N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

시간복잡도는 빅오 표기법에 따라서 O(n₂)이라고 작성한다.

 

- 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

선택 정렬에 비해 구현 난이도가 높지만 동작이 더 효율적이다.

시간복잡도는 빅오 표기법에 따라서 O(n₂)이라고 작성한다.

삽입 정렬은 현재 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

최선의 경우 O(n)의 시간복잡도를 가진다.

 

- 퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

병합 정렬과 더불어 대부분의 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터로 설정한다.

시간 복잡도는 평균의 경우 O(nlogn)의 시간복잡도를 가진다.

최악의 경우 O(n₂)의 시간복잡도를 가진다.

 

- 계수 정렬

특정 조건이 부합할 때만 사용할  수 있지만 매우 빠르다.

데이터의 크기 범위가 제한되어 정수 형태로 표현할  수 있을 때 사용 가능하다.

시간복잡도는 O(N + K)를 보장한다.

 

 

 

5.이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

시간 복잡도는 O(logN)을 보장한다.

 

-파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법

 

 

6. 최단 경로

가장 짧은 경로를 찾는 알고리즘을 말한다.

문제상황

- 한 지점에서 다른 한 지점까지의 최단 경로

- 한 지점에서 다른 모든 지점까지의 최단 경로

- 모든 지점에서 다른 모든 지점까지의 최단 경로

 

- 다익스트라 최단 경로 알고리즘

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.

음의 간선이 없을 때 정상적으로 작동한다.

매 상황에서 가장 비용이 적은 노드를 선택해 그리디 알고리즘으로 분류된다.

 

총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다.

따라서 전체 시간 복잡도는 O(V₂)를 가진다.

노드가 너무 많아서 연산이 비효율적이라면 우선순위 큐 개념을 알아가자.

 

- 플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

다만 매 단계에서 방문하지않은 노드중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.

플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.

플로이드 워셜은 다이나믹 프로그래밍 유형에 속한다.

 

 

 

...