알고리즘
- 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
- 어떠한 문제를 해결하기 위한 절차
컴퓨터 분야에서 알고리즘을 표현 하는 방법
- 의사코드와 순서도
알고리즘의 성능 측정
- 좋은 알고리즘
- 정확성
- 작업량
- 메모리 사용량
- 단순성
- 최적성
-
주어진 문제를 해결하기 위해 여러 개의 다양한 알고리즘이 가능
-
알고리즘의 성능 분석 필요
-
알고리즘의 작업량을 표현할 때 시간복잡도로 표현한다
-
시간 복잡도 (Time Complexity)
- 실제 걸리는 시간을 측정
- 실행되는 명령문의 개수를 계산
-
시간 복잡도 : 빅오 표기법 (O)
- 빅-오 표기법
- 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만 표기
- 계수는 생략
O(3n + 2) = O(n)
O(2n^2 + 10n + 100) = O(n^2)
배열
-
일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
-
아래의 예는 6개의 변수를 사용해야 하는 경우, 이를 배열로 바꾸어 사용
배열의 필요성
- 일일이 다른 변수명을 이용해서 자료에 접근하는 것은 비효율적일 수 있음
- 배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언 가능
1차원 배열
arr = list()arr= []
1차원 배열의 접근
arr[idx] = 10 # arr idx번 원소에 10을 저장
정렬
- 2개이상의 자료를 특정 기준에 의해 작은 값부터 큰 값, 혹은 그 반대의 순서대로 재배열하는 것
- 키
- 자료를 정렬하는 기준이 되는 특정 값
대표적인 정렬 방식의 종류
- 버블 정렬
- 카운팅 정렬
- 선택 정렬
- 퀵 정렬
- 삽입 정렬
- 병합 정렬
버블 정렬
-
인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
-
정렬 과정
- 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다
- 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다
- 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하려 버블 정렬이라고 한다
-
시간 복잡도
- O(n^2)
def bubblesort(a,n):
for i in range(n-1, 0 , -1):
for j in range(0, i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
n = int(input())
a = list(map(int,input().split())) #[55,7,78,12,42]
bubblesort(a, n)
print(a) # [7, 12, 42, 55, 78]카운팅 정렬
-
항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
-
제한 사항
-
정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문
-
카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함
-
-
시간 복잡도
- O(n + k) : n == 리스트 길이 / k == 정수의 최대값
카운팅 정렬 과정
-
[0, 4, 1, 3, 1, 2, 4, 1]을 카운팅 정렬하는 과정
-
1단계
-
데이터에서 각 항목들의 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열 counts를 저장
data = 0 4 1 3 1 2 4 1
counts = 1 3 1 1 2 -
정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts의 원소를 조정함
data = 0 4 1 3 1 2 4 1
counts = 1 3 1 1 2
-> counts = 1 4 5 6 8 (n-1번째 + n번째)
-
counts[1]을 감소시키고 Temp에 1을 삽입함
(Temp : 정렬이 된 결과를 저장하는 data와 같은 크기의 )data = 0 4 1 3 1 2 4 1
counts = 1(0) 4(1) 5(2) 6(3) 8(4)
1까지 4개의 값이 있으므로 1은 4번째 인덱스에 위치
Temp = - - - 1 - - - -
counts = 1(0) 3(1) 5(2) 6(3) 8(4) -
counts[4]를 감소시키고 temp에 4를 삽입
data = 0 4 1 3 1 2 4 1
counts = 1(0) 4(1) 5(2) 6(3) 8(4)
4까지 8개의 값이 있으므로 4은 8번째 인덱스에 위치
Temp = - - - 1 - - - 4
counts = 1(0) 3(1) 5(2) 6(3) 7(4) -
counts[2]를 감소시키고 temp에 2를 삽입
data = 0 4 1 3 1 2 4 1
counts = 1(0) 4(1) 5(2) 6(3) 8(4)
2까지 5개의 값이 있으므로 2은 5번째 인덱스에 위치
Temp = - - - 1 2 - - 4
counts = 1(0) 3(1) 4(2) 6(3) 7(4)
- 같은 방법으로 끝까지 진행
-
def counting_sort(data):
counts = [0] * (max(data) + 1)
sort_counts = [0] * len(data)
for i in range(len(data)):
counts[data[i]] += 1
#print(counts) #[1, 3, 1, 1, 2]
for j in range(1, len(counts)):
counts[j] += counts[j-1]
#print(counts) #[1, 4, 5, 6, 8]
for index in data:
counts[index] -= 1
sort_counts[counts[index]] = index
return sort_counts
data = [0, 4, 1, 3, 1, 2, 4, 1]
print(counting_sort(data)) #[0, 1, 1, 1, 2, 3, 4, 4]
정렬 알고리즘 비교
| 알고리즘 | 평균 수행 시간 | 최악 수행 시간 | 알고리즘 기법 | 비고 |
|---|---|---|---|---|
| 버블 | O(n^2) | O(n^2) | 비교와 교환 | 코딩이 가장 쉬움 |
| 카운팅 | O(n+k) | O(n+k) | 비교환 방식 | n이 비교적 작을때만 가능 |
완전 검색 (Exaustive Search)
-
완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
-
Brute-force 혹은 generate-and-test 기법이라고도 부름
-
모든 경우의 수를 테스트한 후, 최종 해법을 도출
-
일반적으로 경우의 수가 상대적으로 작을 때 유용
-
모든 경우의 수를 생성하고 테스트하기 때문에 수행속도는 느리지만, 해답을 찾아내지 못할 확률이 작음
-
자격검정평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직
순열 생성
- 순열(Permutation)
- 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
- 서로 다른 n개 중 r개를 택하는 순열
nPr
- 그리고 nPr은 다음과 같은 식이 성립
nPr = n (n-1) (n-2) ... (n-r+1) = n! / (n-r)!
- nPr = n!라고 표기
Greedy 알고리즘
- 최적해를 구하는 데 사용되는 근시안적인 방법
- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
- 각 결정은 지역적으로는 최적이지만,
최종적인 해답에서는 그것이 최적이라는 보장은 없음 - 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 greedy 접근임
동작과정
1) 해 선택
2) 실행 가능성 검사
3) 해 검사
