230221 소프트웨어 개발 : 알고리즘

 

출처: http://bigocheatsheet.com/

 

정렬 종류 (시간 / 공간)

• 선택 정렬 : n^2 / n
• 삽입 정렬 : n^2 / n
• 버블 정렬 : n^2 / n
• 합병 정렬 : NlogN / 2n
• 퀵 정렬 : NlogN(평균), n^2(최악) / n

참고 : hsp1116.tistory.com/33

기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1

 

해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.

​* 해싱 함수

- 제산법(Division)

: 키를 임의의 양의 정수로 나눈 나머지를 그 키의 레코드를 저장하는 주소로 결정하는 방법

- 폴딩(Folding)

: 키를 여러 부분으로 나누고, 나누어진 각 부분의 값을 모두 더하거나 보수(XOR)를 취한 결과 값을 레코드 주소로 결정하는 방법

- 계수 분석(Digit Analysis)

: 키 값을 구성하는 숫자의 분포를 파악하여 균등한 분포의 숫자를 선택하여 레코드 주소를 결정하는 방법

- 제곱법(Mid-Square)

: 키 값을 제곱한 값의 중간 부분 값을 선택하여 레코드 주소로 결정하는 방법

- 기수 변환(Radix Transformation)

: 주어진 키 값을 다른 진법으로 변환하여 얻은 결과 값을 레코드 주소로 결정하는 방법

 

 

● 합병 정렬 알고리즘 : 안정정력, 분할 정복 알고리즘의 하나

● 분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원해 문제를 해결하는 전략

● 합병정렬의 단계 : 분할-정복-결합

합병 정렬의 시간 복잡도

● 단순하지만 비효율 적인 방법 : 삽입정렬 n, 선택정렬n², 버블 정렬n²

● 복잡하지만 효율적인 방법 : 퀵 정렬 nlog₂n, 힙 정렬nlog₂n, 병합정렬 nlog₂n, 기수 정렬

 

 

---

 

 

1,2회 #35

알고리즘 시간복잡도 O(1)이 의미하는 것은?

1 컴퓨터 처리가 불가

2 알고리즘 입력 데이터 수가 한 개
3 알고리즘 수행시간이 입력 데이터 수와 관계없이 일정

4 알고리즘 길이가 입력 데이터보다 작음

 

1,2회 #36

정렬된 N개의 데이터를 처리하는데 O(Nlog2N)의 시간이 소요되는 정렬 알고리즘은?

1 선택정렬 

2 삽입정렬 

3 버블정렬

4 합병정렬

 

3회 #27

다음 자료에 대하여 선택(Selection) 정렬을 이용하여 오름차순으로 정렬하고자 한다. 3회전 후의 결과로 옳은 것은? 자리를 바꾸는거라 35가 맨 뒤로 가네

37, 14, 17, 40, 35

1 14, 17, 37, 40, 35

2 14, 37, 17, 40, 35

3 17, 14, 37, 35, 40

4 14, 17, 35, 40, 37

 

3회 #31

알고리즘 설계 기법으로 거리가 먼 것은?

1 Divide and Conquer
2 Greedy
3 Static Block

4 Backtracking

 

4회 #27

다음 초기 자료에 대하여 삽입 정렬(Insertion Sort)을 이용하여 오름차순 정렬할 경우 1회전 후의 결과는?

초기 자료 : 8, 3, 4, 9, 7

1 3, 4, 8, 7, 9 

2 3, 4, 9, 7, 8 

3 7, 8, 3, 4, 9

4 3, 8, 4, 9, 7

 

4회 #38

해싱 함수 중 레코드 키를 여러 부분으로 나누고, 나눈 부분 의각숫자를더하거나XOR한 값을 홈주소로 사용하는 방식은?
1 제산법

2 폴딩법
3 기수변환법

4 숫자분석법