알고리즘 문제 유형

Lee Eunsang·2022년 5월 1일

알고리즘

목록 보기

3/7

Sorting이란?
sorting problem(정렬문제)은 한 sequence의 요소들을 다시 재배열하는 문제이다.
Sorting Key
Sorting Key는 정렬의 기준이 되는 성질로 예를 들면 숫자크기순, 알파벳순 등이 있다.
이 Sorting Key를 비교하는 연산이 많을수록 복잡한 정렬 알고리즘이 된다.
Sorting problem의 의의
sorting은 그 자체로도 하나의 문제 유형이기도 하지만 또, 굉장히 많은 문제들에서 sub_problem으로도 자주 다뤄지며 복잡한 알고리즘들의 base_algorithm으로 활용되어 문제를 더욱 단순하게 만들어주기도 한다.
Sort의 종류
1) Selection sort (선택 정렬)
2) Bubble sort (버블 정렬)
3) Insertion sort (삽입 정렬)
4) Merge sort (병합 정렬)
5) Heap sort (힙 정렬)
6) 등등...
Two Properties of sorting
1) Stable sort
만약 Sorting Key가 동일한 요소가 두개 있을 때, 정렬 이후에도 두 요소의 순서가 항상 바뀌지 않는다면 그 정렬 알고리즘을 'stable' 하다고 부른다.

2) Inplace sort
만약 알고리즘이 진행되면서 추가적인 메모리가 거의 필요하지 않은 경우(아예 안필요한건 아님)에 그 정렬 알고리즘을 'Inplace' 하다고 부른다.

Searhing이란?
Searching problem(탐색문제)는 한 sequence의 요소들 중에서 원하는 요소를 찾아내는 알고리즘이다.
Search Key
Searching Key는 탐색 과정에서 요소들을 구별해내기 위한 value이다. multi_set으로 Searching Key가 주어지는 경우 중복 value로 인해 구분할 수 없는 요소들이 존재할 수도 있다.
Search의 종류
1) Sequential search (순차 탐색)
2) Binary search (이진 탐색)
3) 등등...

String Processing이란?
String Processing은 문자열을 활용하는 모든 유형을 의미하며 그 중에서도 String matching problem이 가장 많이 쓰인다.
String matching problem
String matching problem은 하나의 text에서 주어진 단어나 패턴을 찾아내는 문제이다.

Graph Problems이란?
그래프는 vertices(정점)과 edges(모서리)로 이루어진 하나의 구조를 의미하며 Graph Problem은 이 그래프를 활용하는 모든 유형의 문제를 의미한다.
Basic graph algorithms
1) Graph traversal algorithm - 그래프 길찾기
2) Shortest-path algorithm - 최단 거리 찾기
3) Topological sorting - 위상 정렬

Combinatorial Problems이란?
조합론적인 모든 문제들을 의미하며 어떤 문제에 대한 자명한 algorithm이 정해진 것이 없고, 문제 size에 따라 조합론적 객체 수가 기하급수적으로 커지기 때문에 이론적으로나 실험적으로나 굉장히 해결하기 힘든 문제 중 하나이다.