학습개요
이번 강의에서는 알고리즘의 필요성과 정의에서부터 시작해서 알고리즘의 대표적인 설계 기법, 그리고 성능 분석 방법 등 알고리즘 전반에 걸친 주요 개념들에 대해서 우선 살펴본다. 그리고 정렬 문제를 해결하는 가장 기본적인 형태의 알고리즘으로서 선택 정렬, 버블 정렬, 삽입 정렬에 대해서 학습한다.
학습목표
- 알고리즘의 개념과 중요성을 이해할 수 있다.
- 대표적인 알고리즘 설계 기법의 종류와 개념을 이해할 수 있다.
- 알고리즘 분석을 위한 시간 복잡도와 점근성능의 개념을 이해할 수 있다.
- 선택 정렬, 버블 정렬, 삽입 정렬의 개념, 동작, 특징을 이해할 수 있다.
연습문제
- 문제 해결의 가능성이라는 이론적인 관점에서 알고리즘이 만족해야 할 조건에 해당하지 않는 것은?
- 확장성
- 유효성
- 명확성
- 유한성
정답 : 1❒ 문제 해결 가능성이라는 이론적인 측면에서 알고리즘은 4가지의 조건(입출력, 명확성, 유한성, 유효성)을 모두 만족해야 한다.
• 유효성 → 모든 명령은 컴퓨터에서 실행 가능해야 한다.
• 명확성 → 각 명령은 모호하지 않고 단순 명확해야 한다.
• 유한성 → 한정된 수의 단계를 거친 후에는 반드시 종료한다.
• 입출력 → 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 한다.❒ 한편, 알고리즘의 실용적인 관점에서는 알고리즘의 효율성도 중요한 조건이 된다.
- 알고리즘의 대표적인 설계 기법으로서 거리가 먼 것은?
- 동적 프로그래밍 방법
- 분할정복 방법
- 욕심쟁이 방법
- 회귀분석 방법
정답 : 4❒ 주어진 문제와 조건 등이 매우 다양하므로 범용적인 알고리즘의 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.
- 다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결할 때 가장 먼저 배낭에 넣는 물체는?(단, 물체는 쪼개서 배낭에 넣을 수 있다.)
● 배낭의 무게: 10kg
● 물체1 → 무게 5kg, 이익 20
● 물체2 → 무게 3kg, 이익 15
● 물체3 → 무게 4kg, 이익 14
● 물체4 → 무게 3kg, 이익 9- 물체1
- 물체2
- 물체3
- 물체4
정답 : 2❒ 배낭의 용량을 초과하지 않는 범위 내에서 최대 이익을 얻기 위해서는 무게는 적으면서 이익이 큰 물체부터 최대한 배낭에 넣으면 된다. 따라서 각 물체의 단위 무게당 이익, 즉 각 물체의 이익을 무게로 나눈 값을 계산하여, 이 값이 큰 순서대로 배낭에 해당 물체를 최대한 넣는다.
- 알고리즘의 시간 복잡도에 대한 설명으로 올바른 것은?
- 컴퓨터의 CPU를 통해서 실제로 측정한 수행 시간으로 정의한다.
- 시간 복잡도는 프로그램 코드의 길이에 대한 함수로 표현한다.
- 입력 데이터의 상태에 따라 달라진다.
- 일반적으로 최선의 수행 시간을 시간 복잡도로 사용한다.
정답 : 3❒ 알고리즘의 시간 복잡도는
• 알고리즘에서 수행되는 기본적인 연산들의 수행횟수의 합으로 정의한다.
• 단순히 단위 연산의 개수가 아닌 입력 크기 n의 함수로 표현한다.
• 입력되는 데이터의 상태에 따라 달라지므로, 일반적으로 최악의 수행 시간을 평가 척도로 사용한다.
- f(n)=3n3+3n-1이라고 하고 g(n)=n3이라고 하자. n>1에 대하여 f(n)≤7g(n)일 때 f(n)에 대한 올바른 점근성능의 표기는?
- f(n)=O(n3)
- f(n)=Ω(n3)
- f(n)=Θ(n3)
- f(n)=Φ(n3)
정답 : 1❒ 1보다 큰 모든 입력 크기 n에 대해서 알고리즘 수행 시간 f(n)이 7·g(n)보다 작거나 같다는 것은 결국 알고리즘의 수행 시간 f(n)이 아무리 오래 걸려도 7·g(n)보다 더 커질 수 없다는 점근적 상한을 의미하고, 점근적 상한에 해당하는 표기법은 Big-Oh이다. 참고로 Big-Omega 표기법(Ω)은 점근적 하한(f(n)≥c·g(n)), Big-theta 표기법(Θ)은 점근적 상하한(c1·g(n)≤f(n)≤c2·g(n))을 의미한다.
- 미정렬 데이터 중에서 가장 작은 키값을 갖는 데이터를 선택하고, 선택된 값과 미정렬 데이터 부분의 첫 번째 데이터와 교환하는 방식의 정렬 알고리즘은?(단, 오름차순으로 정렬한다.)
- 합병 정렬
- 버블 정렬
- 삽입 정렬
- 선택 정렬
정답 : 4❒ 선택 정렬은 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식이다.
- 버블 정렬에 대한 설명으로 올바른 것은?
- 역순으로 정렬된 입력 데이터에 대한 성능은 O(n)이다.
- 데이터의 입력 상태에 민감하지 않은 수행 시간을 갖는다.
- 선택 정렬에 비해 데이터 교환이 많이 발생한다.
- 정렬되지 않는 부분의 첫 번째 데이터를 선택해서 정렬된 부분에 위치시킨다.
정답 : 3① 입력 데이터가 역순으로 정렬된 경우에는 최악의 성능 O(n2)을 갖는다.
② → 선택 정렬에 대한 설명이다.
③ 선택 정렬에 비해 데이터 교환이 많이 발생하기 때문에 버블 정렬은 선택 정렬보다 비효율적이다.
④ → 삽입 정렬에 대한 설명이다.
정리하기
- 기본 개념
- 컴퓨터 알고리즘이란? → 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것
- 이론적 관점에서 반드시 만족해야 할 조건: 입출력, 명확성, 유한성, 유효성
- 실용적 관점에서의 추가 조건: 효율성
.
- 컴퓨터 알고리즘이란? → 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것
- 알고리즘 설계
- 대표적인 설계 기법 → 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법
- 분할정복 방법 → 순환적으로 문제를 푸는 방식 → 문제를 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 세 단계를 거친다.
- 적용 가능한 문제 → 퀵 정렬, 합병 정렬, 이진 탐색
.
- 적용 가능한 문제 → 퀵 정렬, 합병 정렬, 이진 탐색
- 동적 프로그래밍 방법 → 문제의 크기가 가장 작은 소문제부터 해를 구해서 테이블에 저장해 놓고 이를 이용하여 입력 크기가 보다 큰 원래의 문제를 점진적으로 만들어가는 상향식 접근 방법
- 적용 가능한 문제 → 모든 정점 간의 최단 경로를 구하는 플로이드 알고리즘
.
- 적용 가능한 문제 → 모든 정점 간의 최단 경로를 구하는 플로이드 알고리즘
- 욕심쟁이 방법 → 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 각 단계에서 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라고 희망하는 방법
- 거스름돈 문제 → 고객에서 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제 → 단순히 동전의 액면가가 가장 큰 동전부터 차례대로 최대한 거스름돈을 만든다.
- 배낭 문제(물체를 쪼갤 수 있는 경우) → 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾는 문제 → 단위 무게당 이익이 가장 큰 물체부터 통째로 배낭에 넣고, 만약에 배낭의 남은 용량보다 물체의 무게가 큰 경우에는 물체를 쪼개서 배낭에 넣는다.
.
- 알고리즘 분석
- 정확성 분석 → 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지를 수학적으로 증명
. - 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원, 즉 소요되는 메모리 공간의 크기 (“공간 복잡도”)와 수행에 걸리는 시간(“시간 복잡도”)을 측정
. - 시간 복잡도
- 알고리즘의 수행 시간 → 알고리즘에서 수행되는 기본적인 연산의 수행횟수의 합
- 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현
- 입력 데이터의 상태에 따라 달라지며, 일반적으로 최악의 수행 시간을 사용
.
- 점근성능 → 입력 크기 n이 충분히 커질 때 알고리즘의 수행 시간이 무엇에 의해 좌우되는가를 나타내는 성능 → 수행 시간이 다항식으로 표현되는 경우 입력 크기가 커짐에 따라 차수가 낮은 항들의 역할은 감소하고, 결국 계수 없이 n의 최고차항만을 이용해서 표현 → 수행 시간의 어림값이지만 수행 시간의 증가 추세 파악이 용이하여 알고리즘의 우열을 따질 때 사용
- 표기법 →
① “Big-Oh” 점근적 상한 f(n)=O(g(n)),
② “Big-Omega” 점근적 하한 f(n)=Ω(g(n)),
③ “Big-Theta” 점근적 상하한 f(n)=Θ(g(n)) - 빅오 표기 간의 연산 시간의 크기 관계
→ O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < … < O(2n)
.
- 표기법 →
- 정확성 분석 → 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지를 수학적으로 증명
- 정렬 알고리즘
- 내부 정렬 vs 외부 정렬
- 내부 정렬 → 모든 데이터를 주기억장치에 적재한 후 정렬하는 방식
- 외부 정렬 → 모든 데이터를 주기억장치에 저장할 수 없는 경우, 일부 데이터만 주기억장치에 있고 나머지는 외부기억장치에 저장한 채 정렬하는 방식
.
- 비교 기반 정렬 vs 분포 기반 정렬
- 비교 기반 정렬 → 데이터의 키값을 직접 비교하여 정렬하는 방식 → 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬
- 분포 기반 정렬 → 데이터의 분포 정보를 사전에 얻어서 정렬에 이용하는 방법 → 계수 정렬, 기수 정렬
.
- 선택 정렬
- 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식 → ① 미정렬 부분의 데이터 중에서 가장 작은 값을 선택하고, ② 선택된 값과 미정렬 부분의 첫 번째 데이터와 교환
- 데이터의 입력 상태에 민감하지 않고 언제나 동일한 수행 시간 → O(n2)
.
- 버블 정렬
- 왼쪽에서부터 모든 인접한 두 데이터를 차례대로 비교하여 왼쪽의 값이 더 큰 경우에는 오른쪽 값과 자리바꿈을 통해 정렬하는 방법
- 데이터가 원하는 순서로 이미 정렬된 경우에는 O(n)을 갖고, 역순으로 정렬된 경우에는 최악의 수행 시간 O(n2)을 가짐
- 데이터의 교환이 많이 발생하여 선택 정렬보다 비효율적
.
- 삽입 정렬
- 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식 → 미정렬 부분의 첫 번째 데이터를 꺼낸 후, 정렬된 부분에서 제자리를 찾아 삽입하는 과정을 반복
- 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로정렬된 경우에는 최악의 수행 시간 O(n2)을 가짐
- 내부 정렬 vs 외부 정렬