“우리 대부분은 초라한 옷차림과 엉터리 가구들을 부끄럽게 여기지만, 초라한 생각과 엉터리 철학을 부끄럽게 여길 줄 알아야 한다.” – Albert Einstein

19800101
algorithm

문제를 해결하기 위한 절차나 방법.

이 단어는 아랍의 수학자인 알-콰리즈미의 이름에서 유래했다고 알려졌다. 영어로는 algorism보다는 algorithm(알고리듬)으로 훨씬 더 자주쓰지만 한국에서는 알고리듬보다는 알고리즘의 사용 빈도가 높다.

알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다. 조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다. 컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저를 의미한다.

알고리즘은 다음 조건을 만족해야 한다.

입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.

출력 : 적어도 2개 이상의 결과를 내어야 한다. (즉 모든 입력에 하나의 출력이 나오면 안됨)

명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.

유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.

효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

즉, 쉽게 말하면 알고리즘은 어떠한 입력이 있다면 이 입력에 따라 명령을 명확하게 실행하고 효과적으로 입력에 따른 결과물을 도출 할 수 있다면 알고리즘으로 볼 수 있다는 의미이다. 반대로 명령에 애매함이 있다거나 유한한 시간 안에 끝나는 것이 보장되지 않은 경우를 메서드(Method)라고 한다. 예를 들어 ‘산에서 길을 잃었을때 계곡을 찾아서 아래로 내려간 뒤 물길을 따라 하류로 가면 된다. ‘ 라는 문장은 메서드이다.

프로그래밍에서 사용하는 알고리즘들

자료구조  :  정렬, 탐색, 각종 트리(tree-최소 스패닝 트리 등)와 힙(heap)

알고리즘 패러다임  :  백트래킹, 동적 계획법, 분할 정복법, 분기 한정법

트리 알고리즘  :  DFS(Depth-First Search), BFS(Breadth-First Search)

그래프 알고리즘  :  탐색, 다익스트라 알고리즘 등 최단 경로 찾기, Union Find, 네트워크 흐름(network flow) 알고리즘

기타 KMP 등의 문자열 매칭, Pollard’s rho 등의 정수론 알고리즘, 선형합동법등의 난수발생 알고리즘, 해석기하/그래픽 알고리즘 등등.

빅오표기법

O표기법은 알고리즘의 최악의 성능을 표시해준다. (빅오)

Ω표기법은 알고리즘의 최고의 성능을 표시해준다. (빅오메가)

θ표기법은 정확한 알고리즘의 성능을 표시해준다. (빅세타, 위 두표기법의 교집합)

O표기법을 주로 사용하는 이유는 최악의 상황이라도 해당 성능을 보장해 준다는 것을 표시하기 위해.

알고리즘 시간복잡도 순서

big-o-complexity

O(1)  :  constant  /  상수  /  처리데이터의 양에 상관없이 일정.  /  임의 접근

O(logn)  :  logarithmic  /  대수  /  처리 데이터의 양이 증가할 수록 실행시간이 약간씩 증가한다  /  정렬된 자료를 이진 탐색

O(n)  :  linear  /  선형  /  처리데이터 양이 많아지면 많아질 수록 처리 시간도 그와 비례해서 늘어난다  /  비정렬 배열에서 탐색, 해시 테이블

O(nlogn)  :  linear log  /  선형 대수  /  처리 데이터의 양의 증가에 대해 처리 시간은 정비례보다 약간 더 많이 증가를 한다  /  힙, 병합, 퀵 정렬

O(n^2)  :  quadratic  /  제곱  /  데이터에 양에 대해 제곱 만큼 시간이 증가.  /  버블, 삽입 정렬, 2중 for

O(n^3)  :  cubic  /  세제곱  /  데이터에 양에 대해 세제곱 만큼 시간이 증가.  /  행렬곱, 3중 for

O(2^n)  :  exponential  /  지수 / 2의 n제곱이 되는 알고리즘은 거의 최악의 알고리즘  /  외판원 문제 정확한 해로 풀기

O(n!)  :  factorial  /  5!= 5 * 4 * 3 * 2 * 1 = 120  /  외판원 문제 그냥 막 풀기


Fisher-Yates shuffle(Knuth shuffle)

//c#
private static Random rng = new Random();

public static void Shuffle<T>(this IList<T> list)
{
    int n = list.Count;

    while (n > 1) {
        n--;
        int k = rng.Next(n+1);

        T value = list[ k ];
        list[ k ] = list[ n ];
        list[ n ] = value;
    }
}

정렬

stable sort, unstable sort?

정렬 알고리듬이 ‘unstable’하다는 말은 data내에 값이 동일한 요소들을 정렬할 경우 정렬 전 순서가 보장이 안되다는 것을 의미한다. 반대로 ‘stable’ 정렬은 정렬이 완료 되었을때 동일한 값들이 정렬 전과 같은 순서로 있는 것을 말한다.

이것이 중요한 이유는 온라인 게임의 리더보드 같은 경우 점수로만 정렬을 할 때 ‘unstable’하게 정렬을 하면 결과가 보는 사람에 따라 순서가 다를 수 있다는 이야기이다. 다른 예로 이름으로 정렬을 먼저 하고 다른 조건으로 정렬을 할 시 stable한 정렬은 동일 이름 순서를 유지 하면서 정렬을 하지만 unstable한 정렬은 순서대로 일 수도 있고 아닐 수도 있다.

O(n^2)

대개 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다. 즉, 1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다.

bubble(best: n / aver : n^2 / worst : n^2) 교환방식

sa_bubble-sort
bubble
shaker
shaker

1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ……, n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째 까지 정렬…… 해서 최대 n(n-1) / 2 번 정렬한다. 한 번 돌때마다 마지막 하나가 정렬이 되므로 원소들이 거품이 올라오는 것처럼 보여 거품정렬이다. 파생형으로 홀수번째 돌때는 앞부터, 짝수번째는 뒤부터 훝는 칵테일 정렬(cocktail sort)내지는 셰이커 정렬(shaker sort)이란 것도 있다. 당연하겠지만 이 쪽은 마지막과 처음이 번갈아가며 정렬된다.

거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 이미 정렬된 자료를 정렬하는 바보짓을 왜 하냐는 의문이 들 수 있지만, 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다.

가장 손쉽게 구현하여 사용할 수 있으며, 소소한 용도에서는 사용빈도도 높은 편이다. 하지만 만들기가 쉽고 직관적일 뿐이지, 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식이다. 다른 몇 가지 정렬 방식과 비교해도 효율이 대략 시망.

그런데도 많이 쓰는 것은 보통 PC의 경우 성능이 좋다보니 입력량이 작으면 어지간한 비효율적인 방법도 씹어먹고 수행이 가능하며, 무엇보다 효과적인 정렬방식을 구현하는 것은 프로그래머 입장에서 귀찮기 때문이다(. . . ) 하지만 웬만큼 자료량이 커지면 버블 소트는 피하는 것이 좋다. 요즘은 웬만한 프로그래밍 언어 내부에 온갖 꼼수를 다 갈아넣은 고효율의 정렬 알고리즘이 내장되어 있어, 그냥 인클루드해서 갖다 쓰기만 하면 되는 세상이라 버블 정렬의 장점이 거의 없다. 내장 정렬이 더 편하니(. . . )

거품정렬에서 파생된 형태로 콤브정렬(Comb sort)이 있다. 이쪽은 기본 형태는 버블정렬과 같지만 예를 들어 처음에 a[0]에서 10칸 띄워서 a[11]과 비교해서 치환하는 식으로 대상을 띄웠다가 한 바퀴 돌면 띄우는 간격을 좁혀서 정렬하는 방식이다. 이렇게 하면 버블정렬과 다를 게 없어졌을 시점엔 정렬이 거의 끝나 있는데, 이 단계까지 가는 동안 모양이 마치 닭의 볏을 닮았다 하여 콤브정렬이라는 이름이 붙었다. 이렇게 본다면 콤브정렬이 버블 정렬보다 좋아 보이지만 단점이 있는데 버블정렬이 stable sort이지만 콤브정렬은 그렇지 못하다.

comb(best: n / aver : nlogn / worst : n^2) 교환방식

Comb_sort_demo

bubble을 향상시킨 것으로 bubble에서는 두 요소를 비교할 때 둘의 거리는 항상 1이다. comb은 이 거리를 1 이상으로 한 것이다. 전체 크기보다 크지않게 간격을 준 뒤 첫 번째부터 시작해 간격만큼 떨어진 요소와 비교해서 교체한다. 비교할 요소가 배열을 넘어가면 간격을 줄인 뒤 다시 처음으로 돌아가서 비교를 반복한데 간격이 0이 되면 정렬을 완료한다.

selection(best: n^2 / aver : n^2 / worst : n^2) 선택방식

sa_selection-sort

버블정렬이 비교하고 바로 바꿔넣는걸 반복한다면 이쪽은 일단 1번째부터 끝까지 훝어서 가장 작은게 1번째, 2번째부터 끝까지 훝어서 가장 작은게 2번째……해서(n-1)번 반복한다. 어찌보면 인간이 사용하는 정렬 방식을 가장 많이 닮아 있다. 어떻게 정렬이 되어 있든 일관성있게 n(n-1) / 2에 비례하는 시간이 걸린다는게 특징. 또한 버블정렬보다 시스템 자원을 적게 잡아먹는다.

insertion(insert) (best: n / aver : n^2 / worst : n^2) 삽입방식

Insertion-sort-example-300px
sa_insertion-sort

k번째 원소를 1 ~ k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로, 평균적으론 O(n^2)중 빠른편이나 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 앞의 예시처럼 작은게 뒤쪽에 몰려있으면(내림차순의 경우 큰게 뒤쪽에 몰려있으면) 그야말로 헬 게이트다. 다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입 / 제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데 탐색을 제외한 오버헤드가 매우 적기 때문이다. 괜히 ‘삽입’이란 이름이 붙은 것이 아니다.

shell(best: n / aver : (nlogn)^2 / worst : (nlogn)^2) 삽입방식

sa_shell-sort

삽입정렬이 거의 정렬된 배열에서 최적의 성능을 내는 것에서 착안한 정렬 방법이다. 삽입 정렬을 띄엄띄엄한 간격으로 먼저 수행하고, 그 간격을 점차 좁혀나가면서 최종적으로는 거의 정렬된 배열을 삽입정렬로 마무리하게 된다. 지저분해 보이지만 삽입 정렬의 특성을 잘 이용한 정렬로, 실제 성능은 힙 정렬 등에 버금갈 정도로 빠르다! 이 정렬 알고리즘의 핵심은 어떤 간격으로 정렬을 수행해나갈 것이냐는 것인데, 그 간격에 따라 시간 복잡도도 제각각이다.

자르는 수를 잘 선택하는 경우 O(n^1. 25)까지도 가능하다고 하는데 일반적인 데이터 크기에 모두 적용할 수 있는 것은 아니다. 알고리즘 자체가 시간복잡도가 명확하지 않고 퀵정렬이나 병합정렬에 비해 크게 나을 것이 없기에 일반적으로 쓰는 알고리즘은 아니다. 쉘 정렬이란 이름은 개발자인 도널드 쉘의 이름을 딴 것으로 유닉스의 쉘과는 관련이 없다. 이것을 잘 몰랐는지 예전 번역서에는 ‘껍질 정렬’로 오역된 책이 있었다. 지금도 껍질 혹은 틀을 의미한다면서 큰 틀을 잡아나가면서 정렬해나가기에 셸 정렬이라는 말이 가끔 도는데 완전히 틀린 말이다.

O(nlogn)

이 세 알고리즘은 최선이나 평균적으로나 O(nlogn)의 성능을 나타낸다. 최악의 상황에서도 병합정렬이나 힙정렬은 O(nlogn)을 유지하는 반면 퀵정렬이 오히려 O(n^2)으로 뒤지나, 실제 응용에서는 최악의 경우는 잘 발생하지 않는다. 그럼에도 불구하고, 병합정렬이나 힙정렬 같은 다른 O(nlogn) 성능의 알고리즘은 요건에 따라서 어느 정도 퀵정렬과 대적할 만하다. 애초에 퀵정렬 하위호환이였으면 예시로 나올리가 없지.

merge(best: nlogn / aver : nlogn / worst : nlogn) 병합방식

Merge-sort-example-300px
sa_merge-sort

개발자는 존 폰 노이만으로 원소개수가 1 또는 0이 될때까지 두 부분으로 자른뒤 자른 순서의 역순으로 크기를 비교해 병합해 나간다. 병합된 부분 안은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다. 대표적인 분할 정복 알고리즘으로 존 폰 노이만의 천재성을 엿볼 수 있는 알고리즘이다. 성능은 아래의 퀵정렬보다 전반적으로 뒤떨어지지만 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다는 점과 stable sort라는 점이다. 힙이나 퀵의 경우에는 배열 A[25] = 100,  A[33] = 100인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있다. 그에 반해서 병합정렬은 그런 거 없다.

heap(best: nlogn / aver : nlogn / worst : nlogn) 선택방식

Heap_sort_example
sa_heap-sort

1. 원소들을 전부 힙에 삽입한다

2. 힙의 루트에 있는 값은 남은 수들 중에서 최소값(혹은 최대값)을 가지므로 루트를 출력하고 힙에서 제거한다.

3. 힙이 빌 때 까지 2의 과정을 반복한다.

사실 선택 정렬과 거의 같은 알고리즘으로. 단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다. 힙정렬은 최악의 경우에 O(n^2)의 성능을 내는 퀵정렬과 달리 항상 O(nlogn) 정렬의 성능을 발휘하는 장점이 있다. 하지만 실제 코드를 짜서 비교를 해보면 퀵정렬이 힙정렬보다 일반적인 경우에 빠르게 동작한다. 재귀방식으로 작성되는 퀵소트가 대량의 원소를 정렬할 때 콜스택이 과도하게 깊어져 오류를 일으키는 경우가 있는 반면에, 재귀를 사용하지 않는 힙소트는 이러한 문제가 없다는 장점도 있다. 하지만 요즘은 퀵소트도 재귀 안쓰고 만들잖아? 그러니까 아마 안될거야. .

quick(best : nlogn / aver : nlogn / worst : n^2) 분할방식

Sorting_quicksort_anim
sa_quick-sort
sa_quick-sort-3-way

퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다. C, C++, C, PHP, 자바 등 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다. 방식은 적절한 원소 하나를 기준(피벗, pivot 으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은것, 큰것으로 나눈뒤 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될때까지 정렬한다.

위에서도 말했듯이 최악의 경우에는 시간복잡도가 O(n^2)가 되는데, 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 경우에 그렇다. 대표적인 예로는 피벗을 항상 배열의 첫 원소로 잡도록 구현한 알고리즘으로 이미 정렬된 배열을 정렬할 경우. 힙정렬이나 병합정렬은 이런 경우가 없지만, 데이터가 극단적이면 대충 구현된 퀵정렬은 안쓰느니만 못한 최악의 결과를 초래한다. 이를 방지하기 위하여 여러 기법들이 개발 되었는데, 대표적인 것이 피벗을 랜덤으로 잡는 것. 또는, 배열 중에 3개나 9개의 원소를 골라서 이들의 중앙값을 피벗으로 고르는 것이다. 이 방법을 사용하더라도 최악의 경우가 나올 수는 있지만 그 경우가 극히 드물게 된다. 재귀 깊이가 어느 제한 이상으로 깊어질 경우 힙 정렬 알고리즘을 사용하여 항상 O(nlogn)을 보장 해주는 방법도 많이 쓰인다.

링크드 리스트 역시 퀵정렬이 가능하다. 첫번째 노드 A를 피봇으로 놓고 나머지 노드들 중 피봇보다 작은 것들은 L1, 큰 것들은 L2로 연결한다. L1과 L2를 퀵정렬한 뒤 L1->A->L2 순으로 연결하면 정렬 완료. 힙소트나 머지소트 역시 가능. 단, 파이썬은 퀵정렬을 하지 않는다. 그 이유는 파이썬은 stable한 정렬을 하는데, 퀵정렬은 stable하지 않기 때문이다. 예를 들어 한글의 키값이 2, 숫자의 키값이 1이라 두면 1, ㄱ, ㄷ, ㄹ, 2를 퀵정렬해서 2, 1, ㄹ, ㄱ, ㄷ같은 게 나올 수도 있다. O(n)의 추가 메모리를 이용하면 stable한 퀵정렬을 만들 수 있다.

현존하는 컴퓨터 아키텍처 상에서 비교 연산자를 이용하여 구현된 정렬 알고리즘 중 가장 고성능인 알고리즘이 바로 이 퀵정렬이다. 단 데이터에 접근하는 시간이 오래 걸리는 외부 기억장소(하드디스크등)에서 직접 정렬을 수행할 경우에는 병합 정렬이 더 빠른 것으로 알려져 있다. 요즘에는 디스크에서 데이터를 블럭 단위로 읽어서 각각을 퀵정렬한 뒤 정렬된 두 블럭을 병합정렬하는 식으로 알고리즘을 설계한다.

이외

radix(best: -/ aver : nk / worst : nk)

k는 데이터의 자릿수를 의미한다.

위에 나온 알고리즘은 모두 데이터끼리의 직접적인 비교를 이용하는데, 이렇게 데이터끼리 직접적인 비교를 하여 정렬할 경우 시간복잡도는 O(nlogn)보다 작아질 수 없다. 이 기수 정렬은 자릿수가 있는 데이터(정수, 문자열 등)에서만 수행이 가능하며, 데이터끼리의 직접적인 비교 없이 정렬을 수행한다. 비교를 이용한 정렬이 아니기 때문에 k가 상수일 경우 시간복잡도가 O(n)으로 퀵정렬보다 빠른 시간복잡도가 나오는 것이 가능하다. 어떻게 데이터끼리 비교하지도 않고 정렬을 할 수 있는지는 후술. 다만 이 알고리즘은 자릿수가 적은 4바이트 정수 등에서나 제대로 된 성능을 발휘할 수 있으며, 자릿수가 무제한에 가까운 문자열 정렬 등에 사용할 경우 오히려 퀵정렬보다 느릴 수 있고, 부동 소수점 등을 정렬할 때는 아예 사용할 수가 없다.

기수 정렬의 방식은 대충 이렇다. 데이터가 n진법이라고 가정하자. 0번부터 n-1번까지의 리스트를 만들어 놓고, 각 데이터를 순서대로 현재 자릿수의 숫자가 가리키는 리스트에 밀어넣고, 리스트를 0번부터 n-1번까지 순서대로 이어붙인다. 이 과정을 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복하면 정렬이 끝나게 된다.

(예시)10, 5, 15, 234, 1: 10진법, 최대 3자리수인 정수들을 정렬해보자. 편의상 010, 005, 015, 234, 001로 표기.

10^0의 자리 : 0) 010, 1) 001, 4) 234, 5) 005, 015. 순서대로 이어붙이면 010, 001, 234, 005, 015.

10^1의 자리 : 0) 001, 005, 1) 010, 015, 3) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.

10^2의 자리 : 0) 001, 005, 010, 015, 2) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.

보다시피 마지막 자리까지 과정을 거치면 정렬된 결과인 1, 5, 10, 15, 234가 나온다. 실제 프로그램에서 정수를 정렬하는 코드를 짜는 경우, 10진법 대신 컴퓨터가 바이트 단위로 처리하기 쉬운 256진법을 사용하고, 각 자릿수를 정렬하는 과정은 밑의 카운팅 정렬을 이용하는 경우가 많다. 그렇게 코드를 짜면 퀵 정렬보다도 훨씬 빠른 속도로 정수를 정렬할 수 있다!

counting(best: -/ aver : n+r / worst : n+r)

카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다.

카운팅 정렬은 쉽게 설명하자면 특정 데이터의 개수(1이 두개있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야할 위치를 찾아내는 정렬 알고리즘이다. 이 경우에 데이터의 최댓값을 k라 두면, 시간은 O(n+k). 하지만, 만약 k가 억단위를 넘어간다면? n이 아무리 작아도 동작시간이 크다. 그럴 땐, 위의 정렬들을 사용하는 게 바람직하다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다. 즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다.

(예시)
data / 0 4 1 3 1 2 4 1

1. data(d)의 각 요소(정수)들의 갯수를 세서 count(c)에 저장한다. (data에서 1의 경우 세 개이므로 count[ 1 ]에 3을 저장)

d / 0 4 1 3 1 2 4 1

c / 1 3 1 1 2

2. count[ 1 ]부터 시작해서 왼쪽(i-1)의 값과 더해서 저장한다. (count[ 2 ]의 경우 count[ 1 ]이 count[ 0 ]과 더해진 4를 더해서 5를 저장)

d / 0 4 1 3 1 2 4 1

c / 1 4 5 6 8

3. data와 동일 크기의 새 배열(t)을 만들고 data 끝 요소부터 숫자를 확인해서 해당하는 count를 하나 빼고 count를 index로 새 배열 위치에 저장

d / 0 4 1 3 1 2 4 1

c / 1 3 5 6 8

t / n n n 1 n n n n (n == null)

4. 3을 반복

d / 0 4 1 3 1 2 4 1

c / 1 3 5 6 7

t / n n n 1 n n n 4

d / 0 4 1 3 1 2 4 1

c / 1 3 4 6 7

t / n n n 1 2 n n 4

d / 0 4 1 3 1 2 4 1

c / 1 2 4 6 7

t / n n 1 1 2 n n 4

d / 0 4 1 3 1 2 4 1

c / 1 2 4 5 7

t / n n 1 1 2 3 n 4

d / 0 4 1 3 1 2 4 1

c / 1 1 4 5 7

t / n 1 1 1 2 3 n 4

d / 0 4 1 3 1 2 4 1

c / 1 1 4 5 6

t / n 1 1 1 2 3 4 4

d / 0 4 1 3 1 2 4 1

c / 0 1 4 5 6

t / 0 1 1 1 2 3 4 4

5. 완료

d / 0 4 1 3 1 2 4 1

t / 0 1 1 1 2 3 4 4

bogo, stupid(best: n / aver : nn!/ worst : ∞) 교환방식

이름 그대로 멍청한 정렬이다. 랜덤으로 데이터들을 재배열 한 후, 정렬되었는지 검사한다. 정렬이 되어있지 않으면 다시 랜덤으로 재배열한다. 정렬 될 때 까지 재배열한다. 덕분에 최악의 경우 정렬이 영원히 안 끝날 수도 있다!물론 정렬된 데이터는 재배열 없이 한 방에 끝난다.

하지만 이 보고정렬은 유전알고리즘과 결합하면 나름 쓸만해지게 된다. 데이터에 따라서는 하나의 값만으로 크기를 비교할 수 없는 경우도 있다. 예를 들어 n차 다항식을 풀어서 나오는 결괏값으로 정렬해야 하는 경우도 있는데 이런 데이터는 위에 나온 모든 정렬알고리즘들이 다 소용없어진다. 이때 n차 다항식은 배열에서 데이터의 현재 위치까지 변수에 들어있는 등 사전에 계산해두는 게 불가능한 데이터이다. 이때 적절한 평가 함수와 유전 알고리즘을 조합하고 나서 유전알고리즘의 후손 생성 알고리즘에 이 보고정렬을 결합하는 것이다. 정말로 멍청하게 정렬된 후손은 도태되고 조금이라도 우수하게 정렬된 후손이 선택되는 과정이 반복돼서 최종적으로는 완전히 정렬된 데이터가 나온다.

단점은 유전알고리즘의 단점을 그대로 물려받는데, 정답이 언제 나올지는 아무도 모른다. 다만 실제로 돌려보면 대자연의 신비인지 생각보다 빠른 시간 안에 정답으로 수렴해간다.


검색

검색(탐색)은 특정 제약 조건을 만족하는 요소를 찾는 것을 말한다. 문제를 해결하는 데 있어 해석적 해법을 사용 할 수 없는 경우 시행 착오를 통해 해결책 을 얻을 수 있다. 일부 알고리즘은 원래 머신 러닝과 함께 인공 지능 분야의 알고리즘이지만, 현재는 다른 분야에도 응용되고 있다.

검색 알고리즘은 광범위하게 말해서 문제를 입력으로 해서 사용 할 수 있는 여러 가지 해법을 평가 한 후 해법을 반환하는 알고리즘이다. 먼저 풀어야 할 문제를 상태(state)와 상태 변화(행동, action)로 나눈다. 먼저 주어진 상태를 초기 상태(initial state)라고 하며, 목표로 하는 상태를 최종 상태(목표, final state, goal)이라고 부른다. 초기 상태에서 최종 상태에 이르는 상태 및 상태 변화의 단계가 답이다.

문제를 푸는 종류로서 연구되고있는 알고리즘의 대부분은 검색 알고리즘이다. 문제의 가능한 모든 해의 집합을 검색 공간이라고 부른다. brutal force와 소박한(지식을 이용하지 않는) 검색 알고리즘은 탐색 공간을 탐색하는 방법으로는 가장 단순하고 직관적이다. 한편 지식을 이용한 탐색 알고리즘은 추론 기법을 사용하여 탐색 공간 구조에 대한 지식을 이용하여 탐색 시간을 줄이기 위해 노력한다.

list search

linear search O(n)

순차 검색 알고리즘(sequential search algorithm), 또는 선형 검색 알고리즘(linear search algorithm)은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다.

binary search O(logn)

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값 을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 이진 검색은 분할 정복 알고리즘의 한 예이다.

간단히 설명하면 사전에서 원하는 단어를 찾을때 중간을 펼쳐 원하는 단어와 같은지 확인하고 같지 않을 경우 현재 단어와 원하는 단어를 비교해서 찾을 방향을 정한 뒤 그 절반의 시작부터 끝 중간을 다시 펼쳐 단어가 나왔는지를 반복해서 찾는 것을 말한다. 속도는 O(logn)이지만 이는 데이터가 정렬이 되어 있을 경우의 이야기이다. 정렬이 되어 있지 않다면 순차 탐색이나 정렬을 먼저 해야한다.

tree, graph search

backtracking

문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있어야 한다. 퇴각검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 결국 풀이 시간이 단축된다.

주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.

퇴각검색은 보통 재귀 함수로 구현된다. 재귀로 파생된 해결 방법은 하나 이상의 변수가 필요한데, 이것은 현재 시점에서 적용할 수 있는 변수값들을 알고 있다. 퇴각검색은 깊이 우선 탐색과 대략 같으나 기억 공간은 덜 차지한다. 현재의 상태를 보관하고 바꾸는 동안만 차지한다.

탐색 속도를 높이기 위해, 재귀 호출을 하기 전에 시도할 값을 정하고 조건(전진 탐색의 경우)을 벗어난 값을 지우는 알고리즘을 적용할 수 있다. 아니면 그 값을 제외한 다른 값들을 탐색할 수도 있다.

dfs bfs
dfsbfs_animation_final

Breadth-first search(BFS) O(|E|) (E는 그래프의 변의 개수이다. )

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.

Depth-first search(DFS) O(|E|)

깊이 우선 탐색(depth-first search : DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다. 여기서 부모 노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

Shortest path problem

그래프 이론에서 최단 경로 문제란 두 꼭짓점 사이의 가장 짧은 경로를 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.

Dijkstra algorithm / 단순 구현시 O(n^2) / 희소 그래프의 경우 바이너리 힙을 이용하면 O((m+n)logn), 피보나치 힙은 O(m+nlogn)

dijkstra_1

(Edsger Wybe Dijkstra 다이ㅋ스트라라고 발음, 오타아님)

컴퓨터 과학에서, 데이크스트라 알고리즘(영어: Dijkstra algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라의 이름에서 유래했다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.

Bellman-Ford algorithm O(VE)

벨먼-포드 알고리즘(영어: Bellman-Ford algorithm)은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 데이크스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행속도도 더 빠르다. 하지만 데이크스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없으므로, 이런 경우에는 벨먼-포드 알고리즘을 사용한다.

V와 E가 각각 그래프에서 꼭짓점과 변의 개수라고 한다면, 벨먼-포드 알고리즘의 실행시간은 O(VE)이다.

informed search

발견법(發見法) 또는 휴리스틱(heuristic)은 경험에 기반하여 문제를 해결하거나 학습하거나 발견해 내는 방법을 말한다. 전산학 등 과학분야에서는 한정된 시간 내에 수행하기 위해 최적의 해 대신 현실적으로 만족할 만한 수준의 해를 구하는 방법이다. 형용사구로 발견적 방법(heuristic method, 휴리스틱 기법)라고도 한다.

A* algorithm O(|E|)

Astar_progress_animation

전산학 분야에 있어서, A* 알고리즘(A* algorithm 에이 스타 알고리듬[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 (다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 / 트리 탐색 알고리즘 중 하나이다. 이 알고리즘은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 “휴리스틱 추정값” h(x) 을 매기는 방법을 쓴다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 breadth first search의 한 예로 분류할 수 있다.

이 알고리즘은 1968년 피터 하트, 닐스 닐슨, 버트램 라팰이 처음 기술하였다. 그 3명의 논문에서, 이 알고리즘은 A 알고리즘(algorithm A)이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다.

넓이 우선탐색 + 깊이 우선탐색을 조합한 휴리스틱 기법으로 길찾기 알고리즘의 한종류. A* 알고리즘은 휴리스틱한 기법이기 때문에 최적의 경로가 아닐수 도 있지만. 현실적으로 만족할 수준의 정확성과 속도라 많이 사용하는 알고리즘. 구현방법은 출발점에서 부터 스탭바이 스탭으로 목적지와 가장 가까운 방향으로 한 칸 한 칸 이동가능한 경로를 찾아가는 방법.

algorithm에 댓글 닫힘 | cat > 사락사락