알고리듬(Algorithm)

알고리즘이란 무엇일까?

사전적 정의 : 문제를 해결하기 위한 여러 동작들의 모임

• 문제를 해결하기 위해 사용하는 방식
• 같은 문제라도 접근과 풀이방법이 다를 수 있다.
• 여러 방법이 있는데 어떤 것이 보다 효율적일까?

알고리즘의 조건

1. 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
2. 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다. (모든 입력에 대한 동일한 결과가 나오면 안됨)
3. 명확성 : 수행 과정은 명확하고, 모호하지 않은 명령어로 구성되어야 한다.
4. 유햔성(종결성) : 유한 번의 명령어를 수행 후(유한시간 내로)에 종료한다.
5. 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

좋은 알고리즘의 분석 기준

• 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단
• 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정, 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
• 기억 장소 사용량(공간 복잡도와 연관) : 수행에 필요한 저장 공간
• 최적성(시간복잡도와 연관) : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 ‘잘 알려진’ 이 아니라 ‘가장 좋은’의 의미이다
• 복잡도(계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법) - Big-O Notation
  • O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
  • O(log N) : 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
  • O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
  • O(N2) : 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.
  • O(N3) : 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.
  • O(2n) : 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.
  • O(n!) : 입력 자료의 크기가 N일경우 n(n-1)(n-2)… * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법

유명한 알고리즘의 종류

탐색

• 선형 탐색법(리니어 서치) : 맨앞에서 순서대로 찾는다.
• 이진 탐색법(바이너리 서치) : 범위를 절반씩 추려가면서 찾는다.
• 해시 탐색법 : 계선해서 저장 위치를 찾는다.

정렬

• 단순 정렬법(선택 소트) : 최솟(댓)값 선택하여 맨 앞부터 순서대로 나열한다.
• 단순 교환법(버블 소트) : 옆에 있는 데이터를 교환하면서 자리를 바꿔 나열한다.
• 단순 삽입법(삽입 소트) : 데이터를 올바른 위치에 삽입하면서 자리를 바꿔 나열한다.
• 퀵 정렬 : 기준 데이터를 기반으로 대소 분할을 반복하여 자리를 바꿔 나열한다.
• 머지 정렬 : 이분할과 머지(병합)를 이용하여 자리를 바꿔 나열한다.
• 힙 정렬 : 힙이라는 데이터 구조를 이용하여 자리를 바꿔 나열한다.
• 셀 정렬 : 그룹을 나누면서 자리를 바꿔 나열한다.

수치 계산 (수치해석)

• 에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 알고리즘
• 유클리드 알고리즘 : 최대 공약수를 구하는 알고리즘
• 가우스 소거법 : 연립 1차 방정식을 푸는 알고리즘
• 사다리꼴 법칙 : 정적분의 근삿값을 구하기 위한 알고리즘
• 다익스트라 알고리즘 : 그래프에서 최적 경로를 구하는 알고리즘
• 이분법 : 방정식을 푸는 알고리즘
• 뉴턴법(뉴턴 랩슨법) : 방정식을 푸는 알고리즘

문자열 탐색

• 무차별 검색법(브루트 포스 검색법) : 맨 앞부터 한 문자씩 차례대로 탐색
• KMP(커누스-모리스-프랫) 알고리즘 : 불일치 부분에 착목하여 탐색
• BM(보이어-무어) 알고리즘 : 부분 문자열의 끝에서부터 탐색