알고리즘

1. 정렬 알고리즘

 

버블정렬

인접한 두 원소를 비교하며 정렬하는 알고리즘

시간복잡도 n^2

 

힙정렬

힙 자료구조에 담아 최대값이나 최소값부터 하나씩 꺼내서 정렬하는 알고리즘

시간복잡도 nlogn

 

병합 정렬

1) 정렬되지 않은 배열을 하나의 원소만 포함하는 n개의 부분리스트로 분할

2) 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분 리스트 생성

3) 마지막 남은 부분 리스트가 정렬된 리스트이다.

시간복잡도 nlogn // 최악의 경우에도 nlogn 보장

 

퀵 정렬

피벗을 선정하여 피벗을 기준으로 좌우측 배열을 피벗보다 크고 작은 값으로 나누며 정렬한다.

시간복잡도 nlogn // 최악의 경우 n^2

 

삽입 정렬

2번째 원소부터 시작하여 앞의 원소들과 비교하여 삽입할 위치를 찾아서 정렬한다.

시간복잡도 n^2 // 최상의 경우 n

 

2. 동적 프로그래밍

문제를 풀기 위해 여러개의 하위 문제로 나누어 푼 다음 결과를 결합하여 해결하는 방식

나누어 진 문제 중 동일한 문제는 한번만 계산하고 그 답을 재활용하는 메모이제이션 기법 사용

 

동적 프로그래밍의 조건

중복되는 부분문제 : 주어진 문제는 같은 부분 문제가 여러번 사용 된다.

최적 부분구조 : 새로운 부분 문제의 정답을 다른 부분 문제의 정답으로부터 구할 수 있다.

 

3. 탐색 알고리즘

 

DFS (Depth First Search) : 특정 노드에서 시작하여 해당 분기를 끝까지 탐색 후 다음 분기로 이동하여 탐색

스택이나 재귀호출을 이용하여 구현한다.

 

BFS (Breath First Search) : 특정 노드에서 시작하여 인접 노드를 먼저 탐색

큐를 이용하여 구현.