알고리즘
정의
유한한 단계를 통해 문제를 해겨랗기 위한 절차나 방법. 주로 컴퓨터용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말함.
컴퓨터에서 알고리즘을 표현하는 방법
1. 수도코드(Pseudocode)
2. 순서도
알고리즘의 성능 측정
APS 과정의 목표 중 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것
무엇이 좋은 알고리즘 ?
- 정확성 : 얼마나 정확하게 동작하는가
- 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
- 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
- 단순성 : 얼마나 단순한가
- 최적성 : 더 이상 개선할 여지없이 최적화되었는가
주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능
-> 어떤 알고리즘을 사용해야하는가?
알고리즘의 성능 분석 필요 : 많은 문제에서 성능 분석의 기준으로 알고리즘의 작업량 비교
#1.
s = 0
for i in range(1,101) :
s+=1
#2.
100*(100+1)/2 알고리즘의 작업량을 표현할 때 시간복잡도로 표현한다.
시간 복잡도
- 실제 걸리는 시간을 측정
- 실행되는 명령문의 개수를 계산
#1
def CalcSum(n) :
sum =0
for i in range(1,n+1) :
sum=sum+i
return sum
#2
def CalcSum(n) :
reutnr n*(n+1)/2
빅오표기법
- 빅-오 표기법
- 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
- 계수는 생략하여 표시
#ex)
O(3n+2) > O(3n) > O(n)
O(2n^2 + 10n + 100) = O(n^2)
O(4) = O(1)배열
- 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
- 아례의 예는 6개의 변수를 사용해야 하는 경우, 이를 배열로 바꾸는 것
Num0 = 0 ; Num1=1; Num2 = 2; Num3=3; Num4=4; Num5=5; == Num=[0,1,2,3,4,5]배열의 필요성
- 프로그램 내에서 여러 개의 변수가 필요할 때, 일일이 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적일 수 있다.
- 배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언할 수 있다.
- 단순히 다수의 변수 선언을 의미하는 것이 아니라 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다.
1차원 배열의 선언
- 별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성
Arr = list()
Arr = []
Arr = [1,2,3]
Arr = [0]*10 1차원 배열의 접근
- Arr[0] = 10; // '배열 Arr의 0번 원소에 10을 저장하라'
- Arr[idx] = 20; // '배열 Arr의 idx번 원소에 20을 저장하라'
배열 활용 예제: Gravity
정렬
2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값, 혹은 그 반대의 순서로 재배열 하는 것
키
- 자료를 정렬하는 기준이 되는 특정 값
- ex) 서류를 번호대로, 카드를 번호대로
정렬의 종류
- 버블정렬(중요)
- 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
- 정렬 과정
- 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막자리까지 이동한다.
- 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다
- 교환되면 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.
- 시간복잡도 : O(n^2)
- 카운팅정렬
- 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하며 선형 시간에 정렬하는 효율적인 알고리즘
- 제한사항
- 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
- 카운트들을 위한 충분한 공간을 할당하려면 집합 내 가장 큰 정수를 알아야한다.
- 시간 복잡도 : O(n+k) :n은 리스트의 길이, k는 정수 최대값
- 선택정렬
- 퀵 정렬
- 삽입 정렬
- 병합 정렬
순열(완전탐색)
-
서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
-
서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다.
-
그리고 nPr은 다음과 같은 식이 성립한다.
nPr = n*(n-1)*(n-2)*...*(n-r+1) #n에서 1만큼 빼가며 r번 곱한다.
그리디 알고리즘
- 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
- 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
- 일반적으로, 머리속에 떠오르는 생각을 검증 없이 바로 구현하는 Greedy 접근이 된다.\
그리디 알고리즘 동작 과정
-
해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합에 추가한다.
-
실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검사한다.
-
해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1)의 해 선택부터 다시 시작한다.
예) 거스름돈 줄이기
-
어떻게 하면 손님에게 거스름돈을 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?
1) 해 선택 : 여기에는 멀리 내다볼 것 없이 가장 좋은 해를 선택한다. 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수가 줄어드므로 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가한다.
2) 실행 가능성 검사 : 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인한다. 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1)로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다.
3) 해 검사 : 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 셈이다. 더 드려도, 덜 드려도 안되기 때문에 거스름돈을 확인해서 액수에 모자라면 다시 1)로 돌아가서 거스름돈에 추가할 동전을 고른다.
