[알고리즘] 알고리즘의 개요
알고리즘의 개요
- 컴퓨터를 이용하는 가장 큰 목적은 데이터 처리로서 정보를 만들어 내는 것
- 이때 정보를 만들기 위해 프로그램이 필요함
- 프로그램은 문제를 해결하기 위한 절차를 바탕으로 구현 함
- 따라 컴퓨터 과학은 ‘컴퓨터+데이터+프로그램+알고리즘’으로 이루어져 있음
- 알고리즘(해결 방법)이 있어야만 컴퓨터가 주어진 문제를 풀수 있기에, ‘컴퓨터 과학 = 알고리즘 과학’이나 마찬가지
알고리즘
-
주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어 들을 단계적으로 나열한 것
- 조건 :
- 입출력 : 0개 이상의 외부입력과 1개 이상의 출력을 생성
- 명확성 : 각 명령은 모호하지 않고 단순 명확해야 함
- 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료함
- 유효성 : 모든 명령은 컴퓨터에서 수행할 수 있어야 함
- (실용적인 관점에서 효율성도 있음)
- 생성 단계
- 설계
- 상향식, 하향식, 욕심쟁이, 분할정복, 동적 프로그래밍 등…
- 표현/기술
- 일상 언어, 순서도, 의사코드, 프로그래밍 언어 등…
- 정확성 검증
- 수학적 증명
- 효율성 분석
- 공간 복잡도, 시간 복잡도
- 설계
알고리즘 설계
- 기본적으로 문제 방안을 찾는 것을 설계라고 할 수 있다
- 이 때 하나의 문제를 해결할 수 있는 알고리즘이 여러개 일 수 있음
- 어떤 알고리즘이 더 효율적인가 역시 찾아야 함
-
주어진 문제나 조건 등이 매우 다양하기에 일반적/범용적인 설계 기법은 미존재
- 대표적인 알고리즘 설계 기법
- 욕심쟁이 방법 (greedy)
- 해를 구하는 여러 선택 과정에서 전후 단계의 선택은 상관없이 각 단계마다 가장 최선인 최적해를 선택하면 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략
- 각 단계마다 선택한 국부적 선택해가 무조건 전체적인 최적해를 만들지 못할 수 있음
- 간단하면서 효율적인 알고리즘을 만들 수 있음
- 주로 최솟값이나 최댓값을 구하는 최적화 문제에서 사용
- 대표적인 적용 문제 : 크루스칼 알고리즘, 프림 알고리즘, 데이크스트라 알고리즘, 거스름돈 문제(동전이 평상적인 경우), 배낭 문제(0/1 배낭 문제 제외) 등
- 분할 정복 방법 (divide-and-conquer)
- 주어진 문제의 입력을 더 이상 나눌 수 없을 때 까지 작은 문제들로 순환적 분할해 각각 해결한 뒤, 각 해를 결합하여 전체의 해를 구하는 전략
- 분할된 작은 문제는 원래의 문제와 동일하나 입력의 크기만 작아진 것
- 분할된 문제는 서로 독립적이기에 순환적 분할 및 결과의 결합이 가능
- 각 순환 호출마다 ‘분할-정복-결합’ 세단계의 작업을 수행
- 대표적인 적용 문제 : 퀵 정렬, 합병 정렬, 이진 탐색
- 동적 프로그래밍 방법 (dynamic programming)
- 입력의 크기가 가장 작은 문제부터 해를 구해 저장해 놓고, 입력 크기가 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법
- 분할된 작은 문제는 원래의 문제와 동일하나 입력의 크기만 작아진 것
- 작은 문제들은 서로 독립일 필요가 없음 (분할 정복과의 차이점)
- 대표적인 적용 문제 : 플로이드 알고리즘, 행렬의 연쇄적 곱셈 문제, 최장 공통 부분 수열 문제
- 욕심쟁이 방법 (greedy)