1장 알고리즘 소개

방통대2/알고리즘

1장 알고리즘 소개

book_lover 2025. 1. 1. 20:33

기본 개념

서울에서 부산에 가려고 한다. 그러면 우선 어떤 교통수단을 이용해서 어떤 일련의 과정을 거쳐 갈지를 결정해야 한다.

고속버스
- 집 → 고속버스 터미널
  - 지하철 or 버스 or 택시 or 걷기 등 일련의 방법 선택

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

이러한 문제를 푸는 독특한 단계별 절차가 있는데 이를 알고리즘(algorithm)이라고 한다

비유적으로 음식을 만들기 위한 조리법을 많이 든다. 식재료 준비하고 조리법에 따른 음식 만드는것 처럼, 데이터를 준비하고 알고리즘에 따르면 주어진 문제를 해결한 결과를 얻는 것이다.

문제를 푸는 기법은 다양하지만 , 기법에 따라서 알고리즘의 성능은 차이 날 수 있다

알고리즘 생성 단계

설계 - 상/하향식 설계, 욕심쟁이, 분할 정복, 동적 프로그래밍
표현/기술
정확성 검증 - 수학정 증명
효율성 분석 - 공간/시간 분석

예시 문제

주어진 배열에 가장 작은 값을 찾는 문제의 알고리즘을 작성

A[] = {80, 70, 40, 20, 30, 10. 60, 50}

최댓값 또는 최솟값을 찾는 기본적인 방법은 각 숫자를 차례대로 하나씩 모두 비교하는 것으로, 이를 일상적인 언어를 사용해서 알고리즘으로 표현하면 다음과 같다.

단계 1. 입력 배열 중에서 첫 번째 데이터를 최솟값으로 지정한다.
단계 2. 배열에서 다음 숫자를 읽고, 이것과 저장된 최솟밗을 비교한다.
단계 3. 비교 후 더 작은 숫자를 최솟값으로 다시 지정한다.
단계 4. 배열에 처리할 데이터가 남아 있으면 [단계 2]로 간다.
단계 5. 저장된 최솟값을 결과로 출력한다.

알고리즘은 일상적인 언어, 순서도, 의사 코드, 프로그래밍 코드 등의 다양한 방법으로 표현되고 기술될 수 있다.

퀘닉스버그 다리 문제(오일러 경로)

주어진 그래프에 대해 임의의 한 점에서 출발해서 모든 선분을 한 번씩 만 지나는 경로의 존재 여부를 확인하시오. 단, 각 점은 여러 번 방문해도 무관하다.

• 각 정점의 차수가 홀수인 정점이 0개 혹은 2개이어야 한다.
• 홀수점이 2개일 경우에는 홀수점에서 시작해야 한다.

순차검색(탐색)

문제 : 원소가 n개인 배열 S에 원소 x가 있는가？
입력（파라미터） : 정수 n(> 0) , 배열 S (인덱스 범위는 1부터 n까지） , 원소 x
출력 : 원소 x가 위치한 인덱스를 location에 저장（S 안에 x가 없으면 0을 저장）
void seqserch(int n, const keytype S[], keytype x, index& location)
{
    location = 1;
    while (location <= n && S[location] != x)
        location++;
    if (location > n)
        location = 0;
}
**
위 코드에서 index& location은 함수가 location 값을 직접 수정하여 호출한 쪽에서도 그 값을 사용할 수 있도록 설계되었습니다. 만약 index location으로 선언했다면, 함수 내부에서 변경된 값이 호출한 쪽에 반영되지 않았을 것

이진 탐색

BinarySearch (A[ ], key, Left, Right)
{
	if (Left > Right) return (-1);
		mid = ;
	if (A[Mid] == key) return (Mid);
	else if (key < A[Mid]) BinarySearch(A, key, Left, Mid-1)
	else BinarySearch(A, key, Mid+1, Right);
}

분할 정복 설계의 대표적 사례

각 도시 간의 가장 짧은 이동 거리 표현
하나의 출발점을 기준으로 다른 모든 정점(도시)으로의 최단 경로를 구하는 문제는 "데이크스트라(다익스크라) 알고리즘으로 해결 가능

서울에서 부산까지 최단 경로는 '서울-천안-논산-대전-진주-부산'이며, 최소 거리는 39이다.
참고로 모든 정점 쌍 간의 최단 경로, 즉 이 경우에는 임의의 두 도시 간의 최단 경로를 찾는 문제는 플로이드(Floyd) 알고리즘을 적용한다. ex(논산-대전, 서울-여주, 대전-대구 등..)

알고리즘 1,2는 똑같이 n-1번의 비교횟수로 똑같다.

설계 방법

욕심쟁이 방법

각 단계에서 '가장 최선' 이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 "희망적인" 전략을 취하는 방법

”희망적” → 각 단계마다 선택한 국부적인 최적해가 항상 전체적인 최적해를 만들지 못할 수도 있음
간단하면서 효율적인 알고리즘을 만들 수 있는 강력한 기법
최솟값/최댓값을 구하는 문제에 주로 사용
대표적인 문제 및 알고리즘
- 거스름돈 문제, 배낭 문제
- 최소 신장 트리 - 크루스칼 알고리즘, 프림 알고리즘
- 단일 출발점 최단 경로 - 데이크스트라 알고리즘

배낭 문제

단, 쪼갤수 없는 문제(0/1배낭문제)는 해결 불가

분할정복방법

순환적으로 문제를 푸틑 하향식 접근 방법(Top-Down)

주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결 후, 이들의 해를 결합하여 원래 문제를 해를 구하는 방식

분할된 작은 문제는 원래 문제와 동일, 단지 입려의 크기만 작아짐
분할된 문제는 서로 독립적 - 순환적인 분할 및 결과의 결합이 가능
각 순환 호출마다 세 단계의 작업을 수행
- 분할 - 주어진 문제의 입력을 여러 개의 작은 문제로 분할
- 정복 - 작은 문제들을 순환적으로 분할, 더 이상 분할되지 않을 정도로 크기가 충분히 작으면 작은 문제에 대한 해를 구함
- 결합 - 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함
퀵 정렬, 합병 정렬, 이진 탐색

동적 프로그래밍 방법

입력의 크기가 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고,

이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식(bottom-up) 접근 방법

각각의 작은 문제는 원래 문제와 동일, 입력의 크기만 작음
작은 문제들은 서로 독립일 필요가 없음, 중복되는 부분에 대해서는 여러번 계산할 경우가 있는데 중복된 부분을 테이블에 저장해 놓고 테이블에 저장한 결과를 불러다 문제를 해결하면 됨.
대표적인 문제 및 알고리즘
- 모든 정점 쌍 간의 최단 경로를 구하는 플로이드 알고리즘
- 행렬의 연쇄적 곱셈 문제
- 최장 공통 부분 수열 문제

알고리즘 분석

시간 복잡도

- 컴퓨터에서 실행시켜 실제 수행시간을 측정하는 방법

- 일반성이 떨어짐(컴퓨터 속도, 프로그래밍 언어, 작성 방법 컴파일러의 효율 성등 환경에 영향을 많이 받음)

- 알고리즘 수행시간 = 각 문장(연산)이 수행되는 횟수 모두 더하는 방법

- 영향을 주는 요수 : 입력 크기, 입력 데이터의 상태

- 시간 복잡도는 최악의 경우를 기준으로 계산하는 것이 일반적

점근성능

입력 크기 N이 무한히 커짐에 따라 결정되는 성능

알고리즘의 시간 복잡도 구하기

기본 연산의 수행 횟수의 합 f(n)을 구함
f(n)=O(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾음

실용적인 접근 방법

알고리즘의 모든 문장이 아닌 "루프의 반복 횟수"만을 조사하여 최고 차수를 시간 복잡도로 취함
O(최고차수)

정리하기

1. 기본 개념

⦁ 알고리즘 → 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것
- 만족해야 할 조건 → (입출력, 명확성, 유한성, 유효성) + (실용적 관점에서는 ‘효율성’도 중요)

2. 알고리즘 설계

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

3. 알고리즘 분석

⦁ 알고리즘 분석 → 정확성 분석, 효율성 분석
⦁ 정확성 분석 → 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는 지를 수학적으로 증명하는 것
⦁ 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
- 공간 복잡도 → 알고리즘 수행에 필요한 총 메모리의 양
- 시간 복잡도 → 알고리즘의 수행시간
⦁ 알고리즘 수행시간 → 알고리즘의 각 단위 연산(문장)이 수행되는 횟수의 합
- 입력 크기의 함수로 표현
- 데이터의 입력 상태에 따라 달라짐 → 최악의 수행시간으로 표현

4. 점근성능

⦁ 입력 크기가 무한히 커짐에 따라 결정되는 성능
- 수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 단순하게 표현하는 방법 → 알고리즘 수행시간의 증가 추세를 나타내므로 알고리즘 간의 우열 표현/비교에 용이
- 요소 → 시작
⦁ 표기법
- O-표기(“Big-oh”) → 점근적 상한 → 알고리즘의 최악의 수행시간에 해당
- Ω-표기(“Big-omega”) → 점근적 하한 → 최선의 수행시간에 해당
- Θ-표기(“Big-theta”) → 점근적 상한과 하한을 동시에 표시
⦁ O–표기의 함수 간의 크기 관계 → O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)
⦁ 실용적인 계산 방법 → 알고리즘에 나타난 루프(반복문)의 반복횟수를 조사하여 최고 차수를 시간 복잡도로 취함

5. 순환 알고리즘

⦁ 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 호출하여 수행하는 형태의 알고리즘
- 수행시간은 점화식으로 표현되고, 이를 풀어서 폐쇄형으로 표시
- 분할정복 방법의 적용된 알고리즘(이진 탐색, 퀵 정렬, 합병 정렬)은 기본적으로 순환 알고리즘 형태로 표현됨
⦁ 기본적인 점화식과 폐쇄형
① T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → T(n) = Θ(n)
② T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → T(n) = Θ(n2) → 퀵 정렬의 최악 수행 시간
③ T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → T(n) = Θ(logn) → 이진 탐색의 수행 시간
④ T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → T(n) = Θ(n)
⑤ T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → T(n) = Θ(n)
⑥ T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → T(n) = Θ(nlogn) → 퀵 정렬의 최선 수행 시간, 합병 정렬의 수행 시간