[정보처리기사]2.소프트웨어 개발/데이터 입·출력 구현/알고리즘

알고리즘

1) 정렬 알고리즘   20년 3회 기출문제

아이템, 레코드에 포함된 필드의 키에 따라 정보의 요소들을 배열

주기억장치에서 이루어지는 내부 정렬 : 힙, 삽입,셀,버블,퀵2-way 병합, 선택,기수

 

(1)Heap 정렬

• 전이진 트리를 이용한 정렬 방식
• O(nlog2n)

(2)퀵 정렬

• 키 기준, 작은값 왼쪽, 큰 깞 오른쪽 서브 파일로 분해
•  위치에 관계없이 임의의 키 분할원소로 사용
• 최악 : O(nlog2n)

순환 알고리즘 사용, 스택공간 필요

(3 )2-way 합병 정렬

• 2 개의 자료를 하나로 합치면서 정렬
• 최악: O(nlog2n)

 

(4)삽입 정렬

•  하나씩 삽입 PASS 4 (4회전)
• 최악:O(n^2)

N+1번째 값이 작은 경우 바꿔서 삽입

(5) 선택 정렬, PASS 3 (3회전)

• N 번째 제외한 N+1, N+2 에서 최소값 찾아 바꿈
• - 최소값 찾아 나머지 모두 비교하면서 정렬
• 최악:O(n^2)

 (6) 버블 정렬, PASS 1 (1회전) 

• - 인접한 2개 자료 비교해서 정렬( 5> 1 = True -> 1,5
• 최악:O(n^2)

(7) Shell 정렬(삽입 확장)

• 매개 변수의 값으로 서브파일 구성
• 각 서브파일 삽입정렬로 순서 배열

(8) 기수 정렬

• Radix=bucket
• 큐 자릿수별 정렬
• O(dn)

 

(7) 해싱

• DAM(직접 접근 방법) 파일을 구성시 사용
• 접근 속도는 빠르지만 기억공간 많이 필요
• 키 값으로 부터 레코드 저장되어 있는 주소 직접 계산, 산출된 주소로 바로 접근
• 버킷: 해시 테이블 구성하는 요소, 하나의 주소를 갖는 파일의 한 구역, 이것의 크기는 같은 주소에 포함될 수 있는 레코드의 수
• 충돌: 서로 다른 키가 동일한 홈 주소를 갖는 경우
• Synonym : 동일한 홈 주소로 인해 충동이 일어난 레코드들의 집합
•  Bucket 구성하는 Slot이 여러 개, Collision 발생시 Overflow 발생 방지

(7.1) 종류  20년 4회

• 폴딩법 레코드 키를 여러 부분 분할, 나눈 부분의 각 숫자 더하기/XOR한 값을 홈 주소로 사용하는 방식
• 제산법 레코드키로 해시표의 크기보다 큰 수 중에서 가장 작은소수로 나눈 나머지를 홈 주소로 삼는 방식
• 기수변환법 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수를 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법
• 숫자분석법(계수분석법) 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식​

(7.2) 해시 충돌(Hash Collision) 문제 해결 방법

• Open Hashing(개방 해싱) : 주소 밖에 새로운 공간을 할당하여 문제 해결
• Closed Hashing(폐쇄 해싱) : 처음에 주어진 해시 테이블의 공간 안에서 문제 해결

(1) Chaining(체이닝)

 개방 해싱인 동시에 폐쇠 해싱

충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 방법. 개방 해싱 알고리즘이다.

특징 :  (1) 새 데이터를 링크드 리스트의 가장 앞(즉, 헤드의 앞)에 삽입한다.

(그러면 데이터 삽입시, 링크드 리스트 테일을 찾는 '순차 탐색' 을 수행하지 않아도 된다.)

    (2) 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점을 가짐.

    (3) 해시 테이블 + 이진 탐색 트리의 결합은 최고!

(2) Open Addressing(개방 주소법)

해시 테이블 내의 해싱에서 충돌이 일어난 자리에 그 다음 버킷들을 차례로 하나씩 탐사, 최초로 나온 빈 버킷에 해당 충돌된 데이터 저장

(2.1) Linear Probing(선형 탐사)

해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동합니다.

특징 : Cluster(클러스터) 현상이 매우 잘 발생한다.

(2.2) Quadratic Probing(제곱 탐사)

선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.

특징 :서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생

(2.3)Double Hashing(이중 해싱)

클러스터 방지를 위해, 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용

(2.4) Rehashing(재해싱)

해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱

 

선형 검색 : 평균 (N+1)/2

이분 검색: 중간 레코드  = (처음 + 마지막 )/2

• 검색할 데이터가 정렬되어야함
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터 수가 절반 (탐색 효율 좋고 , 시간 적음)

3) 시간 복잡도에 다른 알고리즘 2-93, 20년 1, 2회 기출문제

Big-Θ: 알고리즘 수행을 위해서 process가 수생하는 연산 횟수를 수치화할때 평균의 경우

Big-Ω: 알고리즘 수행을 위해서 process가 수생하는 연산 횟수를 수치화할때 최상인 경우

Big-O:알고리즘 수행을 위해서 process가 수생하는 연산 횟수를 수치화할때 최악인 경우

(1) O(1) 상수형 복잡도

자료 크기 무관하게 항상 일정한 속도로 작동

eg. 해시 함수(Hash Function), 스택 삽입,삭제

(2)O(log N) 로그형 복잡도

문제를 해결하기 위한 단계의 수가 log 2N번만큼의 수행 시간을 가짐

eg. 이진 탐색 (Binary Search)/이진 트리

(3)O(n) 선형 복잡도

입력 자료를 차례로 하나씩 모두 처리

수행 시간이 자료 크기와 직접적 관계로 변함 (정비례)

eg. 순차 탐색 (Sequential Search), for 문

(4)O(N log N) 선형 로그형 복잡도

문제를 해결하기 위한 단계의 수가 Nlog 2 N번 만큼 수행 시간을 가짐

eg. 퀵 정렬, 합병 정렬

(5)O(N^2) 

제곱형 주요 처리 루프 구조가 2중인 경우

N의 크기가 작을 땐 N2이 N log 2N보다 느릴 수 있음

eg. 선택 정렬, 버블 정렬, 삽입 정렬, 쉘, 퀵

(6) O(2^n)

eg.피보나치 수열 

 

 

4) 알고리즘 설계 기법 , 20년 3회

• 분할과 정복 (Divide and Conquer) 문제를 나눌 수 없을 때까지 나누고, 각각을 풀면서 다시 병합해 문제의 답을 얻는 알고리즘
• 동적계획법(Dynamic Programming) 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘
• 탐욕법(Greedy) 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 알고리즘
• 백트래킹(Backtracking) 어떤 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 검색하는 알고리즘

 

 

[정보처리기사] 정보처리기사 필기 목차

[정보처리기사] 개정된 정보처리기사 필기 목차