일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 개발공부
- RDS
- UNICON2023
- 42서울
- CICD
- 게임개발동아리
- 인디게임
- 프리티어
- Developer
- 티스토리챌린지
- 라피신
- 체크인미팅
- 위키북스
- 스프링부트
- 자바개발자
- UNICON
- 백엔드개발자
- AWS
- 생활코딩
- 프로그래밍
- 도커
- 인프라
- 스프링
- 전국대학생게임개발동아리연합회
- 백엔드
- 온라인테스트
- 오블완
- 배포
- UNIDEV
- EC2
- Today
- Total
Hyun's Wonderwall
[컴퓨터알고리즘] 1, 2장 - 알고리즘 소개, 삽입 정렬 본문
1단원
알고리즘 과목에서 공부할 내용
- 알고리즘 표현: 문제를 정확하고 추상적으로 정의하는 것, 알고리즘을 수도코드로 나타내는 것
- 알고리즘 유효성: 알고리즘이 옳다는 것을 증명
- 알고리즘 분석: 시, 공간 복잡도.
- 알고리즘 설계: 고전적인 알고리즘. 메타 알고리즘. 어떤 상황에 사용?
알고리즘이란?
- 절차의 순서. 주어진 문제에 대해, 조건 만족 위해. 입력. 출력. 자료구조와 연관.
알고리즘 분석
- 성능과 리소스 사용량 중요. 그외에 정확성. 간결성. 신뢰성 등..
왜 알고리즘과 성능을 공부?
- 확장성 이해 도와줌. 실행 가능/불가능 알수있. 성능이 가치판단의 기준이 됨. 등
2단원
Pseudocode: 알고리즘 표현을 위해 설계되었음. 컴파일되지는 않음.
삽입정렬 Insertion Sort
Input: a1~an 숫자
Output: a1~an (크기순서대로인) 순열.
- 작은 개수의 요소를 정렬하기 좋음.
- 제자리 정렬, 별도의 메모리공간 사용x. 시작할 때 정렬된 건 A[1], 정렬 진행할 수록 A[1...j]가 정렬됨.
- 삽입정렬은 점진적으로 정렬됨.
# pseudo code
INSERTION-SORT(A,n)
for j ← 2 to n do
key ← A[j]
i ← j - 1
while i > 0 and A[i] > key do
A[i+1] ← A[i]
i ← i - 1
A[i+1] = key
pseudo code: block이 없고 들여쓰기를 사용. = 대신 ←를 사용. 배열 인덱스 1에서 시작함.
루프 불변성 Loop invariants: 모든 한 루프에서 정렬이 보장됨.
Correctness: 어떤 일반적인 input이든간에 원하는 정확한 출력이 나와야함. 보통 수학적 귀납법
- 어떻게 증명? (1) 실제 값 넣고 추적해 증명 (2) 추상적인 (a1, ... an) 값 넣고 추적해 증명
- 반례 찾기 위해 넣어볼 수 있는 입력: (1)이미 정렬된, (2)중복된 요소들이 있는, (3)매우 작거나 큰
삽입 정렬의 루프 불변성과 정확성
- Claim: 매 루프에서 A[1...j-1]이 정렬된다.
- Proof: induction을 이용
Proof by Induction (수학적 귀납법)
- Claim: S(n) 이 모든 n>=1에 대하여 참을 증명해야 한다.
- Basis 기본 가정: n=1일 때 참임을 밝힌다
- Inductive Hypothesis 귀납가정: 임의의 n=k에 대해 참이라고 가정한다.
- Step: n=k+1에 대해 참임을 밝힌다.
루프 불변성을 이용해 알고리즘이 참임을 증명
1. Initialization(초기조건)
- 루프 불변성이 루프의 첫번째 반복이 시작될 때 참이다.
2. Maintenance(유지조건):
- 루프가 시작되기 전에 참이라고 가정한다.
- 그리고 (이번 루프 이후) 다음 반복 시작 전에 참이라는 것을 보인다.
3. Termination(종료조건)
- 루프가 종료할 때, 루프 불변성이 알고리즘이 옳음을 보이는 데 유용한 특성이라는 것을 보인다.
삽입정렬 코드
# 수도 코드
InsertionSort(A, n) {
for j ← 2 to n do
key ← A[j]
i ← j - 1
while i > 0 and A[i] > key do
A[i+1] ← A[i]
i ← i - 1
A[i+1] ← key
}
// C언어, A[1]부터 시작하는 경우 (A[0] 사용 x)
void InsertionSort(int A[], int n) {
int j, i, key;
for (j = 2; j <= n; j++) {
key = A[j];
i = j - 1;
// A[j]를 A[1..j-1]에 삽입한다
while (i > 0 && A[i] > key) {
A[i+1] = A[i];
i = i - 1;
}
A[i+1] = key;
}
}
Initialization 초기조건
- A[1]은 정렬되어있다. 따라서 루프가 시작할 때 루프 불변성은 참이다.
Maintenance
- 루프 불변성이 j번째 반복에서 참이라고 하자.
- A[j]를 정렬된 A[1..j-1]에 삽입하는데, 루프를 하다 반복 멈추었을 때 A[j+1]=key으로 들어가므로 j+1번째 반복 전에 루프 불변성이 참이게 된다.
Termination: 종료 시점에 A[1..n]은 A의 요소들을 정렬된 순서로 갖게 된다. (증명 완)
Efficiency: 효율성.
실행시간 어떻게? 연산
Asymptotic Analysis 점근적 분석기법
- 입력 크기 커지면 알고리즘 실행 시간도 커짐.
- 실행 시간이 입력 크기에 의존한다.
- 큰 배열-> 정렬에 더 오랜 시간. T(n): 크기 n인 입력에 걸리는 시간.
- T(n)의 growth(기울기)을 n->무한대로 갈 때 바라본다.
- size: 입력 요소의 개수.
- 실행 시간의 상한선을 본다(big O..)
삽입 정렬의 수행시간
- 거의 대부분 정렬된 경우 정렬 쉽다. 입력 크기 작으면 정렬 쉽다.
King of analyses
- Worst-case: 대부분의 경우. T(n)=아무 입력, 최대 시간
- Average-case: T(n)=모든 입력, 평균적인 시간.
- Best-case: 운이 좋은 경우.
삽입 정렬의 cost, time 분석
각 단계의 cost * time의 합 -> T(n)
InsertionSort(A, n) {
for j ← 2 to n do # c1 * n
key ← A[j] # c2 * (n-1)
i ← j - 1 # c3 * (n-1)
while i > 0 and A[i] > key do # c4 * j=2부터 n까지 tj
A[i+1] ← A[i] # c5 * j=2부터 n까지 (tj-1)
i ← i - 1 # c6 * j=2부터 n까지 (tj-1)
A[i+1] ← key # c7 * (n-1)
}
T(n) = c1n + c2(n-1) + c3(n-1) + c4 * j=2부터 n까지 tj + c5 * j=2부터 n까지 (tj-1) + c6 * j=2부터 n까지 (tj-1) + c7(n-1)
1. 최적의 경우 (이미 정렬됨)
- tj=1. T(n)=an+b. 그냥 n번의 비교를 함. 선형적.
2. 최악의 경우
- tj=j. 이러면 급수 쓰인 부분들이 모두 2차가 됨. T(n)=an^2+bn+c. 이차식 형태로 시간복잡도->상한.
3. 평균의 경우
- tj=j/2. 마찬가지로 T(n)=an^2+bn+c.
Theta notation
Θ(g(n)) = { f(n) : 0<= c1g(n) <= f(n) <= c2g(n) for all n>= n0 }
'Subjects > 컴퓨터알고리즘' 카테고리의 다른 글
[컴퓨터알고리즘] 5장 - 힙 정렬 (0) | 2024.04.24 |
---|---|
[컴퓨터알고리즘] 4장 - (2) 분할정복기법 (0) | 2024.04.24 |
[컴퓨터알고리즘] 4장 - (1) 점화식 (0) | 2024.04.24 |
[컴퓨터알고리즘] 3장 - 함수의 증가 (0) | 2024.04.24 |
[컴퓨터알고리즘] 2장 - 합병 정렬 (0) | 2024.04.24 |