정보처리기사 필기시험 준비 [12]

자료구조와 알고리즘

알고리즘분석은 컴퓨터과학에서 알고리즘을 실행하는데 필요한 시간과 기억 용량과 같은 자원의 수를 결정하는 일을 말한다.

실행시간 - 시간 복잡도 = 컴파일시간 + 실행시간

기억장소의크기 - 공간복잡도 = 고정공간 + 가변공간

 

 

알고리즘의 복잡도

1. 워스트케이스 (Worst Case)
2. 평균케이스 (Average Case)
3. 최선의케이스 (Best Case)

 

 

빅-오 표기법(Big-O Notation)

• 아무리 많은 시간이 소요되더라도 정해진 시간 안에는 종료됨
• 처리에 필요한 시간의 최대치를 표기하며 최악의 경우에도 정해진 수행시간 안에는 알고리즘이 수행 및 완료 되는 것을 보장
• 시간복잡도 함수 중에 가장 큰 영향력을주는 n에 대한 항만 표시할 것
• 계수는 생략할 것
• 가장 높은 n의 지수만 표기함

 

정렬 - 데이터들을 어떤 규칙에 따라 순서대로 나열하는것

• Bubble Sort
  • 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 알고리즘
• 삽입정렬(Insert Sort)
  • 자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
  • 회전이라는 표현으로 1회차를 나타냄

• 선택정렬(Selection Sort)
  • 정렬되지 않은 데이터들에 대해 가장 작은 데이터를찾아 가장 앞의 데이터와 교환해 나가는 방식
• 합병정렬, 병합정렬 - O(nLog2n)

 

 

해싱(Hashing)

• 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색방식
• 비교검색 - 순차검색, 이진검색, 트리검색
• 계산검색 - 해싱

• 검색방법
  • 키 값에 대해서 해시 함수를 계산하고 주소를 구하고 구한 주소에 해당하는 해시 테이블로 이동한 다음 해당 주소에 찾는 항목이 있으면 검색 성공 없으면 검색 실패

• 해시 함수
  • 키값을 원소의 위치로 변환하는 함수

• 해시테이블
  • 해시 함수에 의해 계산된 주소의 위치에 항목을 저장한 표

 

• 재산함수
  • 함수는 나머지 연산자 MOD(%d)를 사용하는 방법
  • 키 값 k를 테이블의 크기 M으로 나눈 나머지를 해시 주소로 사용
  • M으로 나눈 나머지의 값은 0~(M-1)이 되므로 해시 테이블의 인덱스로 사용
  • 해시주소는 충돌 발생 없이 고르게 분포하도록 생성되어야 함으로 키 값을 나누는 해시 테이블의크기 M은 적당한 크기의 소수사용
• 접지함수(폴딩법)
  • 키와 비트 수가 해시 테이블 인덱스의 비트 수 보다 큰 경우에 주로 사용
  • 이동 접지함수
  • 각 분할부분을 이동시켜 오른쪽 끝자리가 일치하도록 맞추고 더하는 방법
• 숫자분석함수
  • 키 값을 이루고 있는 각 자릿수의 분포를 분석하여 해시 주소로 사용
  • 각 키 값을 적절히 선택한 진수로 변환한 후에 각 자릿수의 분포를 분석하여 가장 편중된 부분을 가진 자릿수는 생략하고 가장 고르게 분포된 자릿수부터 해시 테이블 주소의 자릿수 만큼 차례대로 뽑아서 수의 역순으로 바꾸어서 주소로 사용
• 진법변환함수
  • 키 값이 10진수가 아닌 다른 진수일 때 10진수로 변환하고 해시테이블 주소로 필요한 자릿수 만큼 하위자리의 수를 사용하는 방법