신비한 개발사전

위상 정렬은 그래프 형식의 데이터를 탐색할 때 사용할 수 있는 알고리즘이다. 모든 그래프 형식에 사용할 수 있는 알고리즘은 아니다. 방향성이 있고, 순환 구조를 이루는 edge가 없는 그래프만 위상 정렬이 가능하다. 이 두가지 특정 조건을 가진 그래프를 directed acyclic graph(dag)라고 한다. Edge로 이어진 노드들 중 다른 노드를 먼저 거쳐야 도달할 수 있는 노드는 의존성(dependency)을 가진다고 표현한다. 위상 정렬에서는 의존성이 없는 노드를 먼저 탐색하는데, 이때 탐색한 노드는 그래프에서 제거해나간다. 따라서 dag 그래프에서는 노드가 제거될 수록 남은 노드들이 가지는 의존성도 줄어든다. 위와 같은 이유로, 만약 순환되는 구조를 가진 그래프라면 각 노드의 의존성의 유무를..

퀵 정렬은 파티션(partition)이라는 알고리즘을 사용해 배열을 정렬한다. Big-O 표기법으로는 많은 정렬 알고리즘과 동일하게 n²이지만, 평균적으로는 n * log(n) 정도의 시간복잡도를 가진다고 한다. 파티션파티션 알고리즘에서는 말 그대로 배열을 부배열(subarray)이라는 파티션으로 나눈다. 이때 피벗(pivot)이라는 임의로 고른 원소의 좌우로 부배열이 나눠지게 된다. 좌측 부배열은 피벗보다 작거나 같은 값으로 이루어진 배열이고, 우측 부배열은 피벗보다 크거나 같은 값만 있는 배열이다. 파티션을 나누기 위해 먼저 전체 배열의 마지막 원소를 피벗으로 삼는다. 그런 다음 배열의 첫번째 인덱스부터 차례대로 피벗의 값과 비교하면서 정렬해나가는데, 이미 정렬된 부배열과 정렬해야 되는 부배열을 구분..

정렬 알고리즘은 배열의 데이터를 순서에 맞게 정렬할 때 사용되는 알고리즘이다. 선택 정렬 (Selection sort)배열의 순번을 차례대로 순회하면서 데이터의 순서를 재정렬하는 것이 선택 정렬이다. 선택 정렬에서는 데이터를 순서대로 재배치하기 위해 배열을 반복해 돌면서 가장 작은(또는 큰) 값을 임의로 기억해 두었다가 마지막 인덱스까지 도달한 다음 그 값을 알맞은 위치로 이동시킨다. 반복문에서 찾은 값이 인덱스 j에 있었다고 가정할 때, 배열의 앞쪽인 인덱스 i로 이동시킬 땐 단순히 배열[i]에 있던 값과 자리를 바꾼다. 한번 자리를 바꾼 후에는 인덱스 i에 있는 값은 이미 정렬된 값이라고 볼 수 있기 때문에 그 다음 반복문부터는 i + 1 인덱스부터 배열을 순회하면 된다. 이런 방식으로 데이터를 정렬..