문제의 유형들

정렬(Sorting)

• 데이터를 순서대로 재배열하는 문제
• 데이터의 순서는 오름차순(Ascending Order)와 내림차순(Descending Order)가 있음.
• 정렬할 대상을 레코드(Record)라고 부르고, 레코드는 여러개의 필드(Field)로 이루어짐.
• 정렬의 기준이 되는 필드를 키(Key) 또는 정렬 키(Sort Key)라고 함.
• 정렬은 레코드를 키 순서대로 재배열하는 것.
• 비교 기반과 분배 기반 정렬
• 대부분의 알고리즘은 Key Value를 서로 비교하여 정렬하지만, 기수 정렬과 같이 Key Value의 분배를 이용하는 방법들도 있다.
• n개의 레코드를 정렬할 때 비교기반 기법들이 최소한 nlogn에 비례하는 연산이 필요한데 비해, 분배기반 정렬은 이보다 빠른 정렬도 가능함.
• 적용할 수 있는 Key Value에 제한이 있음.
 
• 안정성
• 입력에 동일한 Key Value를 갖는 레코드가 있을 때, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 경우 안정성을 갖는 정렬임.
 
• 제자리(In-place) 정렬
• 입력 배열 외에 추가적인 메모리를 사용하지 않는다면 제자리 정렬이라고 함.

탐색(Searching)

• 주어진 레코드의 집합에서 "탐색키"라 불리는 원하는 값을 가진 레코드를 찾는 작업
  인터넷에서 원하는 상품을 찾고, 단어나 문장을 검색하는 등의 작업
• 가장 단순하게 항목을 하나씩 순서대로 찾는 순차탐색과 DB에서 사용 하는 이진탐색, 해싱과 같은 방법들이 있음
• 모든 상황에 가장 적합한 알고리즘은 없으며, 일반적으로 더 빠른 알고리즘은 더 많은 메모리나 시간을 요구한다.
  따라서 문제의 특성을 잘 파악해 적절한 방법을 사용해야 함.

문자열 처리

• 텍스트에서 특정 문자열을 찾는 문자열 매칭(String Matching)이 중요한 문제중 하나임.
 

그래프(Graph)

• 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조
  ex)지하철 노선표
• 다양한 객체(정점)들이 연결(간선)되어 있는 구조를 표현할 수 있는 논리적 도구
• 그래프의 대표적 관련 문제
• 모든 정점을 빠짐없이 방문하는 순회문제
• 방향 그래프의 위상 정렬
• 두 도시 사이의 가장 빠른 경로를 찾는 최단경로
• 가중치 그래프에서 최소비용의 신장트리를 찾는 문제
 

조합 문제(Combinatorial Problems)

• 어떤 조건을 만족하는 순열이나 조합 또는 부분집합과 같은 조합 객체(Combinatorial Object)를 찾는 문제.
• 가능한 모든 조합에서 최소 비용과 같은 추가적인 특성을 갖는 조합 객체를 찾도록 요구 할 수도 있음.
• 조합 객체의 수는 일반적으로 문제의 크기에 따라 매우 빠르게 증가함.
  입력의 크기가 조금만 늘어나도 상상 할수 없는 수준으로 커지는 상황이 생길 수 있기 때문에 조합문제는 컴퓨팅에서 가장 어려운 문제로 볼 수 있음.
• 많은 조합 문제가 허용 가능한 시간내에 정확한 해를 구한다고 알려진 알고리즘은 없고, 대부분의 컴퓨터 과학자들도 존재하지 않는다고 생각함.
  하지만 그런 생각이 입증되지도 않았고, 반증되지도 않았으며, 컴퓨터 과학의 미해결 문제로 남아있음.
 

기하학적 문제

• 주로 점이나 선 또는 다각형과 같은 기하하적인 객체를 다룸.
• 컴퓨터 그래픽, 로봇 공학, 단층 촬영과 같은 곳에서 사용 됨.