2-1 데이터 입출력 구현 - 검색

검색

 

검색 종류

선형 검색	처음부터 차례로 검색	자료 n개 있을 때 평균 비교 횟수 = (n+1)/2
제어 검색	이분 검색, 보간 검색 등 탐색 효율 좋고 탐색 시간 적게 소요 검색할 데이터 정렬 비교횟수 거듭할 때마다 검색 대상 데이터 수 절반	최악의 복잡도 = O(log n)+1
보간 검색	정렬된 리스트에서 범위를 줄여가며 검색하는 알고리즘	(검색할 자료 - 검색 자료의 최솟값)/ (검색 자료의 최댓값 - 검색 자료의 최솟값) * 검색 자료 수
블록 검색	검색 대상의 자료 그룹별로 블록화	가장 이상적인 블록의 개수 = √n
이진 트리 검색	이진 트리 구조를 이용해 검색	시간 복잡도 = O(log n)
해싱 검색	검색 대상의 자료를 키 변환 작업 통해 검색

 

 

 

해싱 함수 종류

제산법 (Division)	레코드 키값을 소수나 전체 자료수로 나누어 나머지값(%)으로 저장할 위치 선정
폴딩법 (Folding)	레코드 키 값을 여러 부분으로 나누고 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 사용
제곱법 (Square)	레코드 키 값을 제곱한 결과 값의 일부를 선택하여 저장할 위치 선정
중간 제곱법 (Mid-squre)	레코드 키 값을 제곱하고, 이 값의 중간 부분을 취하여 홈 주소로 선정
숫자 분석법 (Digit Analysis)	레코드 키 값을 이루는 숫자들의 분포를 파악하여 고른 부분을 선택해 저장할 위치 선정
기수 변환법 (Radix Transformation)	레코드 키 값을 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 버켓의 개수 범위에 맞게 조정
의사 무작위법 (Pseudo-random)	난수(무작위의 수)를 발생시킨 후 그 난수를 이용하여 저장할 홈 주소의 위치 선정

 

 

 

시간 복잡도

https://images.velog.io/images/jehjong/post/61fb9d3f-5f8f-471f-85bd-a4a15fe9c19c/image.png

 

 

 

 

 

정렬

 

1. 정렬의 시간 복잡도

빠른 순: O(logN) > O(N) > O(NlogN) > O(N^2)

 

 

 

2. 정렬의 종류

 

선택 정렬 (selection Sort)	큰(작은) 키 값 찾아 교환 가장 작은 값 먼저 결정(여러 번 교체) 가장 큰 값 먼저 결정(한번 만 교체)
버블 정렬 (Bubble Sort)	인접한 키 값을 교환, 이미 정렬 시 중단
삽입 정렬 (Insert Sort)	자신의 위치를 찾아 삽입(처음에 앞의 2자리만, 순차적으로 자릿수 늘려감) 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬
쉘 정렬 (Shell sort)	삽입 정렬 개선 입력 파일을 매개 변수값으로 서브 파일 구성하고 각 서브파일을 삽입정렬 방식으로 순서 배열하는 과정 반복
힙 정렬 (Heap sort)	이진 트리 구조를 만들어 정렬 정렬할 입력 레코드들로 힙 구성하고 가장 큰 키 값을 갖는 루트 노드 제거하는 과정 반복하여 정렬
이진 병합 정렬 (2-way merge sort)	두 개의 키를 한 쌍으로 정한 후 정렬
버킷 정렬 (Bucket sort)	기수 값에 따라 분배하여 정렬
퀵 정렬 (Quick sort)	레코드 많은 자료 이동 없애고 하나의 파일을 부분적으로 나누어 가며 정렬

 

 

 

 

 

모듈 구현

 

1. 단일 모듈 구현

 

• 상세 설계된 단위 모듈이나 환경 설정 모듈을 실제 프로그래밍 언어로 구현
• 통합 구현 위해 분산되어 있는 모듈 그룹화
• 종류별로 분류하여 컴포넌트화
• 응집도는 높게, 결합도 낮게 구현
• 공통 모듈 먼저 구현 후 개별 단위 모듈 구현 시 공통 모듈 재사용
• 항상 예외 처리 로직 고려하여 구현

 

단위 모듈 4가지 핵심 원리

정보 은닉 (information hiding)	어렵거나 변경 가능성 있는 모듈을 타 모듈로부터 은폐
분할과 정복 (Divide&Conquer)	복잡한 문제 분해, 모듈 단위로 문제 해결
데이터 추상화 (Data Abstraction)	각 모듈 자료 구조 액세스하고 수정하는 함수 내에 자료 구조의 표현 내역 은폐
모듈 독립성 (Module Independency)	낮은 결합도와 높은 응집도

 

 

 

2. 화면 모듈 구현

HTML 5 화면 구조

 

 

 

2. 반응형 웹(responsive web)

 

• 각 장치의 특성에 맞게 자동적으로 설정해주는 웹 기술
• 리액트(react), 뷰(vue), 앵귤러(angular) 등 웹 컴포넌트를 사용하여 구현

 

 

 

 

 

 

 

 

Reference

https://book.naver.com/bookdb/book_detail.naver?bid=17134434 

이기적 정보처리기사 필기 기본서