1강 알고리즘 소개

[출처] 방송통신대학교 알고리즘 수강 정리

 

1. 컴퓨터 과학에서 알고리즘

- 컴퓨터과학 = 컴퓨터 + 데이터 + 프로그램 + 알고리즘

- 컴퓨터 한계 = 알고리즘의 존재 여부

- 컴퓨터 과학 = 알고리즘 과학

- 알고리즘

- 알고리즘의 한계

- 알고리즘의 분석

- 알고리즘의 개발

- 알고리즘의 실행

- 알고리즘간의 통신

- 알고리즘의 표현

 

2. 학습 목표

- 잘 알려진 특정 문제를 위한 알고리즘의 설계 및 분석 방법의 습득

- 컴퓨터를 이용한 문제 해결 방법에 대해 체계적으로 생각하는 훈련

- 주어진 문제에 대한 지적 추상화 능력 향상

 

 

1.1 알고리즘?

- 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것.

- (입출력) 입출력

- 0개 이상의 외부 입력

- 1개 이상의 출력

- (명확성) 각 명령은 모호하지 않고 단순 명확해야 함.

- (유한성) 한정된 수의 작업 후에는 반드시 종료.

- (유효성) 모든 명령은 수행 가능해야 함.

- (실용적 관점) 효율적이어야 함.

 

- 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것.

 

1.2 알고리즘 생성 단계

- 설계

- 상향식 설계

- 하향식 설계

 

- 표현/기술

- 일상 언어, 순서도

- 의사 코드, 프로그래밍 코드 등

 

- 정확성 검증

- 수학적 검증

- 실용적 검증

 

- 효율성 분석

- 공간 복잡도

- 시간 복잡도

 

 

1.3 알고리즘 기술 언어

- C 유사 언어

 

 

2.1 알고리즘 설계

- 최대값 찾기 :

-(알고리즘 1 ) 값들을 하나씩 모두 비교해 가면서 최대값을 찾는 방법

-(알고리즘 2 ) 토너먼트 방식

- 알고리즘 1과 2 중 어떤 것이 더 효율적인가.

- 비교 회수를 카운트하여 효율성의 우위성을 정한다.

 

 

2.2 순차 탐색 알고리즘

- 순처 탐색 : 앞에서 부터 하나씩 찾아가는 방법

- 이진 탐색 : 순서대로 나열된 카드에서 10 찾기

- 중앙의 카드를 오픈 하여 작은지 큰지를 따져 찾을 방향을 정한다.

 

 

2.3 알고리즘 설계 기법

- 주어진 문제와 제반 조건 등이 매우 다양

- 일반적인 틀 제시 곤란

 

- 대표적인 설계 기법

- 욕심쟁이 greedy 방법

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

- 희망적 -> "각 단계마다 선택한 최적해가 전체 최적해를 만들어 내지 못할 수 있음"

- 1장(거스름돈 문제, 배낭문제), 4장 프림 알고리즘, 크루스칼 알고리즘, 데이크스트라 알고리즘)등이 욕심쟁이 방법으로 구현된 것임.

 

- 분할정복 divide-and-conquer 방법 (순환적 recursive으로 문제를 푸는 하향식 방법)

- 분할 : 주어진 문제를 여러 개의 작은 문제로 분할

- 정복 : 작은 문제들을 순환적으로 분할 만약 작은 문제의 크기가 충분히 작다면 순환 호출 없이 작은 문제에 대한 해가 구해짐.

- 결합 : 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함.

- 2장(퀵 정렬, 합병 정렬), 3장(이진 탐색) 등이 분할정복 알고리즘으로 구현된것임.

 

- 동적 프로그래밍 dynamic programming 방법(최적화 문제의 해를 구하는 상향식 접근 방법)

- 주어진 문제를 여러 개의 부분 문제로 분할

- 가장 작은 부분 문제부터 해를 구하여 테이블에 저장

-  테이블에 저장된 해를 이용하여 입력 크기가 보다 큰 원래 문제를 점진적으로 해결

- 4장(모든 쌍 최단 경로를 구하는 플로이드 알고리즘), 6장 (동적 프로그래밍 : 연쇄 행렬 곱셈, 스트링 편집 거리등이 동적 프로그래밍으로 구현된것임.

 

 

2.4.1 욕심쟁이 방법의 한계

- 멋쟁이씨가 세상에서 가장 멋진 바지, 가장 멋진 넥타이, 가장 멋진 자켓을 입는다고 할 때, 그렇다면 그런 옷을 입은 멋쟁이씨는 세상에서 가장 멋쟁이라고 할 수 있는가?

 

2.4.2  거스름돈 문제

- 고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 문제

- 해결 방법 : 액면가가 큰 동전부터 최대한 뽑아서 거스름돈을 제공

 

2.4.3 배낭 문제

- 최대 용량 M인 하나의 배낭과 각각 무게 Wi와 이익Pi가 부여되어 있는 n개의 물체가 있다고 가정

- 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 집어넣는 방법을 찾아내는 것.

- 물체를 쪼갤 수 있다고 가정

- 각 물체의 가중치(단위 무게당 이익)이 최대가 되는 물체부터 집어 넣는다.

 

 

 

 

 

 

3.1 알고리즘 분석

- 정확성 분석

- 유효한 입력, 유한 시간 -> 정확한 결과 생성

- 다양한 수학적 기법을 사용한 이론적 증명

- 다양한 입력 상황을 가정한 테스트 데이터를 통한 실용적 방법

 

- 효율성 분석

- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

- 공간 복잡도 space complexity -> 메모리 양(=정적공간 +_ 동적공간)

- 시간 복잡도 time complexity -> 수행 시간

 

3.2 시간 복잡도

- 수행 시간에 영향을 미치는 요인

- 컴퓨터 속도

- 사용하는 프로그래밍 언어

- 프로그램 작성 방법

- 컴파일러의 효율성

 

 

 

 

 

 

 

- 입력의 크기

- 입력 데이터의 상태

 

- 단순한 단위 연산의 개수가 아닌 입력 크기의 함수로 표현

- 입력 크기 : 입력되는 데이터의 크기, 문제가 해결하려는 대상이 되는 개체의 개수.

- 행렬의 크기, 리스트 원소의 수, 그래프의 정점의 수 등

 

 

 

 

 

 

 

 

 

 

 

4. 점근 성능(점차적으로 가까이 가는 성능)

- 입력 데이터 크기n이 충분히 커짐에 따라 결정되는 성능

- 다항식의 수행 시간에 대해서 최고차항만을 이용해서 표현

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

데이터 n에 비례 하여 처리 시간 증가 추세가 어떠냐에 따라 표기 법

 

 

 

 

 

입력 크기에 따른 연산 시간의 증가 추세

 

 

 

 

 

 

 

 

알고리즘의 시간 복잡도를 구하려면

- 알고리즘의 수행시간 f(n)을 구한 후 f(n)=O(g(n))을 만족하는 최소의 g(n)을 찾음

- 실용적인 접근 방법

- 알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함.

- g(n)은 최고 치수에 의존

 

 

 

 

 

5. 순환(재귀) 알고리즘의 성능

- 몇번 순환 했는지 알기 어렵기 때문에 점화식으로 표현

 

 

 

 

 

 

5.3 기본 점화식과 폐쇄형

 

- (2) 퀵 정렬(최악), (3) 이진탐색, (6) 퀵(최선), 합병 정렬 정도는 필히 암기