일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- codeengn basic rce 01
- BoB 12기
- 코드엔진 basic 5
- 코드엔진
- 철학
- 코드엔진 베이직
- 디지털 포렌식 트랙
- CodeEngn Basic 5
- CodeEngn Basic 01
- Best of the Best
- 사회분업론
- 리버싱
- CodeEngn
- 논문리뷰
- malware
- 자살론
- bob
- h4ckinggame
- 사회적 사실
- 에밀 뒤르켐
- BoB 12기 최종합격 후기
- Today
- Total
woonadz :)
[개념정리] 검색 본문
※ 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘 선택
1-1. 검색 알고리즘
배열 검색에 사용되는 알고리즘
- 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
- 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
방법 1) 체인법 : 같은 해시 갑스이 데이터를 선형리스트로 연결하는 방법
방법 2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
1-2. 선형 검색
선형 검색(순차 검색)이란?
배열에서의 검색 : 원하는 키 값을 갖는 요소와 만날 때까지 맨 앞부터 순서대로 요소를 검색
▷ 일반적으로 배열의 요소 개수가 n개일 때, 조건을 판단하는 횟수는 평균 n/2 회이다.
∵ 종료 조건을 검사하는 비용이 크다.
▷ 보초법 : 이 비용을 반으로 줄이는 방법
- 보초 : 검색하기 전에 검색하고자 하는 키 값 (반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할)
1-3. 이진 검색
이진 검색이란?
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘으로 배열의 요소 중앙값과 원하는 키 값을 비교 후 남은 두 부분 중 한 부분을 다시 비교(그림 참고)
▷ 이진 검색을 검색을 반복할 때마다 검색 범위가 절반이 되므로 비교 횟수 평균 값은 log n 이다.
복잡도란?
알고리즘의 성능을 객관적으로 평가하는 기준
1. 시간 복잡도 : 실행에 필요한 시간을 평가한 것
2. 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
선형 검색의 시간 복잡도 : O(n) (n에 비례하는 횟수만큼 실행하는 경우)
n/2로 표현하지 않는 이유는 n의 값이 무한히 커진다고 가정했을 때 그 값의 차이가 무의미해지기 때문.
이진 검색의 시간 복잡도 : O(log n)
'IT > 자료구조 및 알고리즘' 카테고리의 다른 글
[개념정리] 재귀 알고리즘 (0) | 2022.02.12 |
---|---|
[개념정리] 스택과 큐 (0) | 2022.02.04 |
[개념정리] 기본 자료구조 (0) | 2022.01.23 |
[개념정리]동적 계획법_nabi (0) | 2021.11.23 |
[개념정리]백 트래킹_nabi (0) | 2021.11.16 |