01-알고리즘 개요

01-알고리즘 개요

2024. 12. 17. 22:38ㆍlearning more/알고리즘

728x90

알고리즘(algorithm)
주어진 문제에 대해 하나 이상의 결과를 생성하기 위해 모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는 유한개의 일련의 명령을 순서에 따라 구성한 것
욕심쟁이 방법(greedy method)
해를 구하는 일련의 선택 과정마다 해당 단계에서 ‘가장 최선‘이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법
거스름돈 문제(coin change problem)
가게에게 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
배낭 문제(knapsack problem)
배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾아내는 문제
* 0/1 배낭 문제 : 배낭에 넣는 물체를 쪼갤 수 없다는 가정이 있는 배낭 문제로서, 이 경우에는 욕심쟁이 방법으로 해결할 수 없는 NP-완전문제가 된다.
분할정복 방법(divide-and-conquer method)
순환적으로 문제를 푸는 하향식 접근 방식으로, 주어진 문제의 입력을 더 이상 쪼갤 수 없을 때까지 2개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법
동적 프로그래밍 방법(dynamic programming method)
주어진 문제의 입력의 크기가 가장 작은 부분 문제부터 해를 구하여 저장해 놓고 이를 이용하여 입력 크기가 보다 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법

아무리 간단한 문제일지라도 주어진 문제를 해결하기 위해서는 일련의 단계적인 처리 과정이 요구

컴퓨터와 알고리즘

컴퓨터의 한계 ≒ 알고리즘의 한계
컴퓨터 과학 = 알고리즘 과학
- 알고리즘의 한계
- 알고리즘의 실행
- 알고리즘의 통시
- 알고리즘의 분석
- 알고리즘의 개발
- 알고리즘의 표현

알고리즘의 조건

조건 1> 입출력（input & output): 외부에서 0개 이상의 입력을 부쑈 서 하나 이상의 출력 을 생성해야 한다

조건 2> 명확성（definiteness): 각 단계（명령）는 모호하지 않고 단순하고 명확해야 한다．

조건 3> 유한성（finiteness): 한정된 수의 단계를 거친 후에는 반드시 끝나야 한다．

조건 4> 유효성（effectiveness): 모든 명령은 컴퓨터에서 수행할 수 있어야 한다．

** 효율성 또한 가지고 있어야 한다. **

알고리즘 생성 단계

설계(상향식/하향식 설계)
표현/기술(일상 언어, 순서도, 의사코드, 프로그래밍언어 등)
정확성 검증(수학적 증명)
효율성 분석(공간/시간 복잡도)

알고리즘 대표적 예시

다익스트라 알고리즘

다익스트라 알고리즘은 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용. 이 알고리즘은 가중치가 음수가 아닌 그래프에서만 동작

플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 그래프 내 모든 정점 쌍 간의 최단 경로를 찾는 데 사용. 이 알고리즘은 음수 가중치를 허용하지만, 음수 사이클이 존재하면 올바르게 작동하지 않음

Hierholzer's Algorithm

오일러 회로나 경로를 찾기 위한 효율적인 알고리즘입니다.
작동 방식:
1. 임의의 정점에서 시작하여 닫힌 경로(사이클)를 찾습니다.
2. 이미 방문한 경로에 포함된 정점 중 아직 방문하지 않은 간선이 있는 경우, 해당 정점을 시작으로 새로운 사이클을 찾고 기존 경로에 삽입합니다.
3. 모든 간선을 방문할 때까지 반복합니다.

오일러 경로 (Eulerian Path)
오일러 경로는 그래프의 모든 간선을 정확히 한 번씩만 방문하는 연속된 경로입니다. 이때 시작점과 끝점이 다를 수 있습니다.

조건
그래프가 연결 그래프여야 합니다.홀수 차수를 가진 정점이 0개 또는 2개여야 합니다.홀수 차수가 2개인 경우: 오일러 경로가 존재하며, 시작점과 끝점은 각각 홀수 차수를 가진 정점입니다.홀수 차수가 0개인 경우: 오일러 회로가 존재합니다.

Fleury's Algorithm

간단하게 오일러 경로나 회로를 찾는 방법입니다.
작동 방식:
1. 홀수 차수를 가진 정점을 확인하여 시작점을 선택합니다.
2. 각 단계에서 "다리(bridge)"가 아닌 간선을 우선적으로 선택하여 진행합니다.
3. 모든 간선을 사용할 때까지 반복합니다.

오일러 회로 (Eulerian Circuit)
오일러 회로는 오일러 경로의 특수한 형태로, 시작점과 끝점이 같은 경로입니다. 즉, 모든 간선을 한 번씩 방문한 후 출발점으로 돌아옵니다.

조건
그래프가 연결 그래프여야 합니다.
모든 정점의 차수가 짝수여야 합니다.

순차탐색

Sequentialsearch (A[ 1, n, key)
입력 : A[O. .n-1] : 입력 배열
n : 배열 크기（데이터 개수）
key : 탐색 키（찾으려는 값）
출력 : key가 배열 내에 존재하면 해당 인덱스』 아니면 n을 반환
{
1 = 0,
while (1 < n && A[i] != key)
i = i + 1;
return (1);
}

이진탐색 (입력 데이터가 정렬된 경우)

BinarySearch (A[], key, Left, Right)
입력： A{Left. . Ri醜t] : 입력 배열
key = 탐색 키
출력 : key가 A[ ] 내에 존재하면 해당 인덱스， 아니면 -1을 반환
{
 if (Left > Right) return (-1);
 Mid = [(Left + Right) I 2];
 if (A[Mid] == key) return (Mid);
 else if (key < A[Mid]) BinarySearch(A, key, Left, Mid-i)
 else BinarySearch(A, key, Mid+1, Right); 
}

알고리즘 설계방법

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

욕심쟁이 방법

해를 구하는 일련의 선택 과정에서 전후 단계의 선택과는 상관없이 각 단계마다 "가장 최선"이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을것이라는 "희망적인" 전략을 취하는 방법
단, 항상 전체적인 최적해를 구한단 보장은 아님

거스름돈 문제

거스름돈이 780원일 때 고객에게 돌려줄 동전의 최소 개수를 구하시오． 단 , 사용할 수 있는 동전의 종류

50O원 , 100원 , 50원 , 10원의 네 종류가 있다고 가정

일반적인 경우란?
일반적으로, 그리디 알고리즘이 최적해를 보장하기 위해서는 동전의 액면가가 특정한 수학적 관계를 만족해야 합니다. 예를 들어, 각 동전의 액면가가 서로의 배수 관계에 있어야 합니다. 즉, 큰 액면가의 동전이 작은 액면가의 동전으로 정확히 나누어 떨어져야 합니다

왜 일반적이지 않은 경우 문제가 되는가?
배수 관계 부족: 동전의 액면가가 서로 배수 관계에 있지 않으면, 그리디 알고리즘은 최적해를 보장하지 못할 수 있습니다. 예를 들어, 500원, 100원, 50원, 10원 동전은 서로 배수 관계에 있어 그리디 알고리즘이 잘 작동하지만, 여기에 120원 같은 중간 액면가가 추가되면 이 관계가 깨질 수 있습니다.최적해 실패 사례: 문제에서 제시된 것처럼, 650원을 거슬러 줄 때 그리디 알고리즘을 사용하면 500원 1개, 120원 1개, 10원 3개로 총 5개의 동전을 사용하게 됩니다. 그러나 최적해는 500원 1개, 100원 1개, 50원 1개로 총 3개의 동전만 사용하면 됩니다

배낭 문제 (물체를 쪼갤 수 없는 형태의 배낭 문제)

단위 무게당 이익이 가장 큰 물체부터 최대한 넣는 과정을 반복

0/1 배낭문제 (물체를 쪼갤 수 없는 형태의 배낭 문제)

욕심쟁이 방법으로 해결 불가

분할정복 방법

분할정복 방법은 순환적으로 문제를 푸는 하향식 접근 방법

분할（divide): 주어진 문제의 입력을 여러 개의 작은 문제로 분할한다.
정복（conquer): 작은 문제들을 순환적으로 분할한다 . 만약 작은 문제가 더 이상 분 할되지 않을 정도로 충분히 작으면 순환 호출 없이 작은 문제의 해를 구한다（정복 한다)
결합（combine , 합병）: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다．

쪼개진 문 제들은 원래의 문제에 비해 입력의 크기만 작아졌을 뿐 문제 자쳬는 원래 문제와 동일 하며 , 서로 독립적이기 때문에 각각의 작은 문제를 다시 순환적으로 분할하고 그 결과 를 통합하는 것이 가능

퀵 정렬, 합병 정렬, 이진 탐색 등

분할 : 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 절반씩 분할, 탐색 키와 가운데 원소가 같으면, 해당 원소의 배열 인덱스를 반환/종료
정복 : 탐색 키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출
결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

동적 프로그래밍 방법

입력의 크키가 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적을 만들어 가는 상향식 접근 방법

각각의 작은 문제는 원래 문제와 동일, 입력의 크기만 작음
작은 문제들은 서로 독립일 필요가 없음
플로이드 알고리즘, 행렬의 연속 곱셈 문제 등

정리하기

1. 기본개념

⦁ 알고리즘 → 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것

- 만족해야 할 조건 → (입출력, 명확성, 유한성, 유효성) + (실용적 관점에서는 ‘효율성’도 중요)

2. 알고리즘 설계

⦁ 알고리즘 생성 과정: 설계 → 표현(기술) → 정확성 분석 → 효율성 분석
⦁ 많은 부류의 문제에 적용될 수 있는 대표적인 설계 방법 → 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법
⦁ 욕심쟁이 방법
- 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 볼 수 있는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법
- 한계 → 국부적인 최적해가 항상 전체적인 최적해를 구성하지 못하는 경우도 있음
- 적용 알고리즘/문제 → 거스름돈 문제, 배낭 문제, 최소 신장 트리(크루스칼 알고리즘, 프림 알고리즘), 단일 출발점 최단 경로(데이크스트라 알고리즘)
- 거스름돈 문제 → 가게에서 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제 → 동전의 액면가가 일반적인 경우에는 욕심쟁이 방법 적용 불가
- 배낭 문제 → 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제 → 물체를 쪼개서 넣을 수 없는 ‘0/1 배낭 문제’는 욕심쟁이 방법 적용 불가
⦁ 분할정복 방법
- 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방식
- 분할된 문제는 입력 크기만 작아졌을 뿐 원래 문제와 동일하며 서로 독립적
- ‘분할’-‘정복’-‘결합’의 단계로 구성
- 적용 알고리즘/문제 → 이진 탐색, 퀵 정렬, 합병 정렬
⦁ 동적 프로그래밍 방법
- 입력의 크기가 가장 작은 부분 문제부터 해를 구하여 저장해 놓고 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법
- 분할된 문제는 입력 크기만 작아졌을 뿐 원래 문제와 동일하며 서로 독립적일 필요는 없음
- 적용 알고리즘/문제 → 모든 정점 쌍 간의 최단 경로를 구하는 플로이드 알고리즘, 교재 5장(행렬의 연쇄적 곱셈 문제, 최장 공통 부분 수열 문제)

흔적 남기기