[Algorithm] 알고리즘 정리

정렬

선택 정렬(selection sort)

• 배열에서 가장 큰 값을 선택하여 정렬되지 않은 배열의 맨 뒤로 이동시켜 정렬하는 방법입니다. 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 

버블 정렬(bubble sort)

• 배열에서 인접한 두 값을 비교하여 조건에 맞게(오름차순, 내림차순에 따라 다름) 값의 위치를 이동시켜 정렬하는 방법입니다. 선택 정렬과 마찬가지로 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다.

향상된 버블 정렬(enhanced bubble sort)

• 버블 정렬과 같은 방법으로 동작하지만 이중 반복문을 순환하는 동안 값이 한 번도 바뀌지 않으면 정렬되었다고 가정하는 정렬 방법입니다. 버블 정렬과 마찬가지로 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다.

삽입 정렬(insertion sort)

• 정렬된 배열을 하나씩 늘려나가는 정렬 방법으로 정렬되지 않은 값을 선택하여 알맞는 위치에 삽입시켜주는 것으로 정렬하는 방법입니다. 평균, 최악의 경우에는 O(n^2)의 시간 복잡도를 가집니다. 하지만 최선의 경우(거의 정렬된 배열의 경우)에는 O(n)의 시간 복잡도를 가집니다.

병합 정렬(merge sort)

• 입력을 나누어서 합치는 과정에서 정렬하는 방법으로 분할 정복 알고리즘의 하나입니다. 모든 경우에 대해서 O(nlogn)의 시간 복잡도를 갖지만 입력 크기만큼의 추가 메모리가 필요합니다.

퀵 정렬(quick sort)

• 임의의 값을 선택하여 해당 값을 기준으로 기준 값보다 작은 원소들은 왼쪽에 기준 값보다 큰 값은 오른쪽에 재배치하는 과정을 통해 정렬하는 방법입니다. 병합 정렬과 마찬가지로 분할 정복 알고리즘의 하나입니다. 평균, 최선의 경우 O(nlogn)의 시간 복잡도를 갖지만 최악의 경우 (한쪽에는 재배치할 값이 없고, 다른 쪽에 몰려있는 경우)에는 O(n^2)의 시간 복잡도를 가집니다.

힙 정렬(heap sort)

• 자료구조 힙(heap)을 이용하여 정렬시키는 방법입니다. 힙은 이진 트리로 맨 아래층을 제외하고 모든 값이 채워져 있고, 맨 아래층은 왼쪽부터 채워집니다. 힙은 다음의 성질을 만족합니다.
  • 각 노드의 값은 자기 자식의 값보다 작거나 같다.
• 위의 성질을 이용하여 힙의 루트 노드를 제거하고, 다시 힙을 만드는 과정을 반복하여 정렬하는 방식입니다. 모든 경우에 대하여 O(nlogn)의 시간 복잡도를 갖습니다.

이진 검색 트리

이진 검색 트리의 특징

• 이진 검색 트리의 각 노드는 하나의 값을 가진다. 모든 노드의 값은 달라야한다.
• 최상위 레벨에 루트 노드가 존재하고, 모든 노드는 최대 2개의 자식 노드를 가질 수 있다.
• 임의의 노드에 대해서 왼쪽에 있는 모든 노드의 값보다 크고, 오른쪽에 있는 모든 노드의 값보다 작아야 한다.

좌우의 균형이 잘 잡힌 이진 검색 트리를 균형이 잡힌 이진 검색 트리라고 합니다. 이때, 이진 검색 트리의 시간 복잡도는 최악의 경우라고 하여도 O(logn)입니다. 하지만 최악의 경우 (이진 검색 트리의 노드가 한쪽에 몰린 경우)에는 O(n)의 시간 복잡도를 가집니다.  

 

이진 검색 트리의 평균 검색 횟수

• 이진트리에서 각 노드의 깊이를 더한 것을 내부 경로 길이(Internal Path Length)라고 합니다. 따라서 평균 검색 횟수는 IPL/노드의 총개수입니다.

이진 검색 트리의 삭제

• r이 리프 노드인 경우: r을 삭제한 후 부모 노드에서 r을 가리키는 포인터를 NIL로 수정한다.
• r의 자식 노드가 하나인 경우: r을 삭제한 후에 부모 노드에서 r을 가리키는 포인터를 r의 자식으로 수정한다.
• r의 자식 노드가 두 개인 경우: r을 삭제한 후에 부모 노드에서 r을 가리키는 포인터를 다음의 2가지 경우 중에 하나를 선택하여 수정한다.
  1. r의 왼쪽 서브 트리에서 가장 큰 값
  2. r의 오른쪽 서브 트리에서 가장 작은 값

해쉬 테이블

해쉬 테이블의 정의

• 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조입니다. 해쉬 테이블은 자료의 저장과 검색에 있어 O(1)의 시간 복잡도를 가집니다.

해쉬 테이블의 충돌

• 해쉬 테이블 내의 한 주소를 두고 2개 이상의 원소가 자리를 다투는 것을 말합니다.

충돌 처리 방법

• 체이닝: 같은 주소로 해싱되는 원소를 연결 리스트에 저장하는 방법을 말합니다.
  • 연결 리스트에 삽입할 경우에는 연결 리스트의 맨 앞에 삽입합니다. 
  • 연결 리스트 대신에 배열을 사용할 경우 이진 검색 트리를 사용하여 값을 검색할 수 있습니다.
• 개방 주소 방법: 추가 공간을 허용하지 않고, 충돌이 발생할 경우 다른 주소를 계산하여 값을 저장하는 방법을 말합니다.
  • 선형 조사: 충돌이 발생한 바로 다음 값을 확인하는 방법으로 특정 영역에 몰릴 때 성능이 떨어지는 1차 군집 문제가 발생합니다.
  • 이차원 조사: 충돌이 발생한 후 다음 주소를 확인하는데 2차 함수를 사용하는 방법으로 처음 해쉬 함수 값이 같을 경우 같은 방법으로 조사를 진행하여 성능이 떨어지는 2차 군집 문제가 발생합니다.
  • 더블 해싱: 2개의 함수를 사용하여 충돌을 처리하는 방법으로 1차, 2차 군집 문제 모두 발생하지 않습니다. 더블 해싱에서 주의할 점은 두 번째 해쉬 함수 값이 해시 테이블의 크기와 서로소인 값이어야 한다는 것입니다. 해결 방법은 다음과 같습니다.
    • 해쉬 테이블의 크기를 소수로 잡고, 두 번째 해쉬 함수 값을 해쉬 테이블의 값보다 작은 자연수가 되도록 하는 것으로 해결할 수 있습니다.

해쉬 테이블의 삭제

• 해쉬 테이블의 중간에 있는 값을 삭제할 경우 검색할 때 삭제한 값을 거쳐갈 수 없기 때문에 deleted라는 상수값을 저장합니다.
• 값을 삽입할 경우에 deleted를 만났을 때 해당 주소에 값을 삽입하는 것을 값을 채웁니다.

동적 프로그래밍

동적 프로그래밍의 정의

• 큰 문제의 해답이 작은 문제의 해답에 포함되어 있는 것을 말합니다.

동적 프로그래밍의 조건

• 최적 부분 구조를 이룬다.
• 재귀 호출로 구현할 경우 심각한 비효율을 발생시킨다.

동적 프로그래밍 탑다운, 바텀업

탑다운(Top-down)

• 재귀 함수를 사용하여 문제를 해결하는 방식으로 작은 문제들이 해결되면 큰 문제가 해결되는 방식입니다.

바텀업(Bottom-up)

• 작은 문제들의 해답을 통해 큰 문제를 해결하는 방식입니다.

그래프 탐색

그래프와 트리: 트리는 그래프에 완전 포함됩니다. 따라서 트리의 조건에 대해서 알아보겠습니다.

• 연결되어 있다.
• 접점 n개와 간선 n-1개로 이뤄져 있다.
• 순환이 없다.

그래프의 표현

• 인접 행렬: 정점의 총수를 n이라고 할 때 n x n 행렬에 접점과 간석의 정보를 표현하는 것을 말합니다. 인접 행렬의 경우 간선의 밀도가 높은 그래프에서 사용하기 유용합니다.
• 인접 리스트: 각 정접의 인접한 정점들을 연결 리스트에 저장하여 표현하는 것을 말합니다. 인접 리스트의 경우 간선의 밀도가 높을 경우 연결 리스트를 만드는 메모리가 많이 필요하므로 간선의 밀도가 높을 경우에는 적합하지 않습니다.

너비 우선 탐색(BFS): 주변 노드를 우선으로 탐색하는 알고리즘입니다.

깊이 우선 탐색(DFS): 깊이를 우선으로 탐색하는 알고리즘입니다.

최소 신장 트리

최소 신장 트리의 정의

• 간선들이 가중치를 갖는 그래프에서 간선의 가중치의 합이 가장 적은 트리를 말합니다.

프림 알고리즘

• 공집합으로 시작하여 모든 정점이 포함될 때까지 정점을 포함시키는 알고리즘입니다. 연결 비용이 최소인 노드를 선택하는 방식으로 동작합니다.

크루스칼 알고리즘

• 사이클을 만들지 않은 범위에서 최소 비용의 간선을 하나씩 더하는 방법으로 동작하는 알고리즘입니다.

위상 정렬

다익스트라 알고리즘

그리디 알고리즘

그리디 알고리즘의 정의

• 문제 해결 단계에서 계속해서 가장 좋아 보이는 선택을 하여 답을 도출하는 방법입니다.

 

 

🎯 2021년 2학기 알고리즘 수업 내용 정리입니다.

참고 문헌: 쉽게 배우는 알고리즘, 문병로, 한빛아카데미, 2018-01-20