[알고리즘] 알고리즘의 기초 정리자료-1

🌷 알고리즘의 기본 자료구조

- 배열과 연결 리스트 

배열은 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수로 모아놓은 집합체
연결 리스트는 노드(데이터 필드 + 링크 필드로 구성)라는 저장구조를 이용하여 리스트를 표현하는 것

• 배열은 논리적인 순서와 실제 순서가 같기 때문에, 인덱스로 접근이 쉬우나 삽입, 삭제시 순서를 유지하기 위하여 데이터의 이동이 빈번
• 연결 리스트는 순차 접근 방식으로 비교하고 데이터의 접근이 포인터의 조작으로 삽입, 삭제가 원활

- 스택과 큐

 

- 트리와 그래프

 

- 이진 트리

 

🌴 대표적인 알고리즘 설계 

 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법

 

🍓 주요 O-표기 간의 연산 시간의 크기 관계

 

🌵 순환 알고리즘의 성능

 

(1) 분할정복 알고리즘

분할정복은 하향식으로 접근하는 순환적 방법이다. 

원래 문제와 동일하지만 입력 크기만 작아지기 때문에 서로 독립적이며, 분할, 정복, 결합으로 처리한다.

적용 알고리즘 

이진 탐색, 합병 정렬, 퀵 정렬, 선택 문제(분할 함수, 중간값들의 중간값)

이진 탐색

→ 정렬된 상태의 입력 데이터를 절반씩 줄여가면서 원하는 값을 찾는 방법 O(logn)

특징 

• 정렬된 데이터에 대해서만 적용 가능
• 삽입/삭제 시 정렬 상태 유지를 위해 데이터 이동이 발생

퀵 정렬

→ 피벗이 제자리를 잡도록 하여 정렬하는 방식, 분할 함수 Partition()

• 최악 수행 시간 → O(n^2)
• 최선 수행 시간 → O(nlogn)
• 평균 수행 시간 → O(nlogn)

합병 정렬

→ 전형적인 분할정복 방법(분할, 정복, 결합) 이 적용된 알고리즘 O(logn)

특징

• 입력 크기 n 만큼의 추가적인 저장 장소가 필요 

선택 문제

→ 임의의 순서로 저장된 배열 A[0..n-1]에서 i번째로 작은 원소를 찾는 문제

• 최소값(or 최대값) 찾기 → (n-1)번 비교
• 최소값과 최대값 모두 찾기 → (3/2)n-2번 비교
• i번째로 작은 원소 찾기 →
• Partition() 이용 → 최악 O(n^2), 평균 O(n) 
• 중간값들의 중간값 이용 → 최악 O(n), 평균 O(n)

 

(2) 동적 프로그래밍 방법

동적 프로그래밍 방법은 최적성의 원리로 점화식을 도출해내에서 소문제의 해를 테이블에 저장.

저장된 해를 이용해서 점차적으로 상위 문제의 해를 구함

• 상향식 접근 방법
• 최적화 문제 해결에 주로 사용
• 소문제는 독립일 필요는 없음

적용 알고리즘

피보나치 수열, 연쇄 행렬 곱셈, 스트링 편집 거리, 모든 정점 간의 최단 경로("플로이드 알고리즘"), 저울 문제

연쇄 행렬 곱셈 문제

→ n개의 행렬을 연쇄적으로 곱할 때 기본 곱셈 횟수가 최소가 되는 행렬의 곱셈 순서를 구하는 문제 (On^3)

스트링 편집 거리 문제

→ 문자열 X(x1x2 ...xn)를 Y(y1y2 ...ym)로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용("편집 거리")을 구하는 문제

모든 정점 간의 최단 경로

가중 방향 그래프에서 모든 조합의 두 정점 간의 최단 경로

플로이드 알고리즘

• 경유할 수 있는 정점의 범위를 1에서 |V|까지 하나씩 늘려가면서 최단 경로를 구하는 방법 (O(|V|^3)
• 가정 → 가중치의 합이 음수인 사이클이 존재하지 않음

저울 문제

무게 M인 물체를 n개의 추를 이용하여 양팔 저울로 달수 있는지 확인하는 문제 O(nM)

• 가정 → 추의 무게 wi와 물체의 무게 M은 모두 정수

 

(3) 욕심쟁이 알고리즘

각 단계에서 가장 최선이라고 여겨지는 해를 선택해 나감으로써 전체적인 최적해를 구하는 방법

• 최적화 문제, 최적성의 원리
• 한계 → 각 단계에서 하나의 최적해만 고려

적용 알고리즘

동전 거스름돈 문제, 배낭 문제, 최소 신장 트리(크루스칼 알고리즘, 프림 알고리즘), 단일 출발점 최단 경로("데이크스트라 알고리즘"), 작업 스케줄링 문제, 작업 선택 문제, 허프만 트리

동전 거스름돈 문제

동전의 개수를 최소로 하는 거스름돈을 찾는 방법 O(n)

배낭 문제

배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제 O(n)

• 가정 → 물체를 쪼개서 넣을 수 있다.

최소 신장 트리

가중 무방향 그래프에 대한 크리 중에서 간선의 가중치의 합이 가장 작은 트리

• 가정 → 그래프가 트리가 되는 조건 → 무방향, 모든 정점 연결 무사이클(n-1)

1) 크루스칼 알고리즘

서로 다른 연결 성분에 속하는 정점을 잇는 최소 가중치의 간선을 선택 O(|E|log|E|)

- 사이클이 이루어지는 지 항상 확인 해야한다. 

 

2) 프림  알고리즘 

S(선택된 정점)와 V-S(선택되지 않은 정점)을 잇는 간선 중에서 가중치가 최소인 간선을 선택 O(|V|^2)

 

- 크루스칼은 간선 위주의 알고리즘, 프림은 정점 위주의 알고리즘

 

 단일 출발점 최단 경로

특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로

데이크스트라 알고리즘 

 

• 가정 → 음의 가중치를 갖는 간선이 없어야 한다.
• 초기화 → d[s] = 0, 나머지 정점 d[v] = ∞, S = {}
• V-S에서 거리 d[]가 최소인 정점 u를 선택

→ u의 인접 정점 v에 대해 d[v] = min{u를 경유하는 거리, 기존 거리}

• 성능 → 인접 행렬 O(|V|^2), 인접 리스트+힙 O((|V|+|E|)log|V|)

작업 스케줄링 문제, 작업 선택 문제

1) 작업 스케줄링 문제

최소의 기계를 사용해서 충돌 없이 모든 작업을 기계에 할당하는 문제 O(nlogn)

✓ 각 단계에서 시작 시간이 빠른 작업을 우선 선택해서 충돌이 없으면 해당 기계에 할당하고, 출동이 발생하면 새로운 기계에 할당

 

2) 작업 선택 문제 

하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 할당하는 문제 O(nlogn)

✓ 각 단계에서 완료 시간이 빠른 작업을 우선 선택해서, 충돌이 없으면 기계에 배정하고, 충돌이 발생하면 해당 작업을 버림

 

허프만 코딩

문자의 출현 빈도수에 따라 다른 길이의 부호를 부여

• 접두부 코드, 최적 코드
• 인코딩 과정 → 각 문자의 출현 빈도수 계산, 허프만 트리를 통해 각 문자의 이진 코드 부여, 주어진 텍스트에 대해 압충된 텍스트 생성 
• 성능 → O(nlogn + m) (n: 문자 집합의 크기, m: 텍스트의 길이)
• 특징 → 각 문자의 빈도수를 모르면 텍스트를 두 번 읽어야 하므로 속도 저하, 다코딩을 위한 정보 저장으로 인해 실제 압축률 저하 

허프만 트리

욕심쟁이 방법, 전 이진 트리

각 문자가 개별적인 트리인 상태에서 빈도수가 가장 작은 두 트리를 합치는 과정을 반복

허프만 트리는 유일하지 않음

• 같은 빈도수를 갖는 트리를 합치는 순서에 따라 다른 형태의 트리 생성

→ 각 문자에 부여되는 이진 코드가 달라짐

→ 인코딩된 메시지는 다르지만 메시지 길이는 동일