검색 알고리즘

728x90

SMALL

뇌빼고 코테 준비하다가 한계에 부딪혀서 쓰는 포스팅입니다. :-)

우선 검색 알고리즘은 집합에서 원하는 값의 원소를 찾는 알고리즘 입니다.

오늘은 유명한 검색 알고리즘 종류 3가지 중 (배열검색, 연결 리스트 검색, 이진 검색 트리) 배열검색에 대해

그리고 그 중에서도 선형 검색, 이진 검색, 해시법에 대해 공부하려합니다.

첫번째로 선형 검색의 경우 브루트 포스(BruteForce), 완전 탐색이라고도 하며 배열 전체를 처음부터 원소를 찾을 때까지. 혹은 찾지 못할 경우 끝까지 확인합니다. 보통 for 문 while 문을 사용하며 시간복잡도 O(n)을 갖습니다.

예제 문제

두번째로 이진 검색입니다. 이진 검색의 경우 오름차순 혹은 내림차순으로 배열이 정렬 되어 있어야 하며, 배열의 중앙값과 검색 값을 비교하여 반절씩 쳐내어 가는 식으로 값을 찾아 갑니다. 때문에 시간 복잡도 O(log n)을 갖습니다

예제 문제

마지막으로 해시법 입니다. 이 방법은 원소의 검색뿐 아니라 추가, 삭제도 효율적으로 수행합니다.

해시값을 인덱스로 해서 새로 저장한 배열을 해시테이블이라고 하며 키를 특정한 방법(나머지를 구하는 연산 또는 그 연산을 응용한 것)으로 대응한 해시값을 가집니다. 이렇게 해시값을 변환하는 과정을 해시 함수라고 하며 만들어진 원소를 버킷이라 합니다.

나머지를 구하는 연산은 저장할 버킷이 중복되는 해시 충돌을 일으키며 (키와 해시값의 대응은 꼭 1:1 이 아니며 일반적으로 n:1)

체인법, 오픈 주소법 두가지 방법으로 대응합니다.

체인법 : 해시값이 같은 원소를 연결 리스트로 관리

오픈 주소법 : 빈 버킷을 찾을 때 까지 해시를 반복

예제 문제

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

추가적으로 배운 점

1. 오늘 배운 내용을 통해 파이썬에서 List -> element in 은 O(n), Dictionary -> key in 은 O(1) 의 시간 복잡도를 가지는 이유를 알 수 있었다.

Dictionary가 해시테이블이기 때문!

2. 파이썬에선 Switch가 없기에 Dictionary를 대신하는데 그렇다면 Swift에서 Switch의 시간복잡도는?

놀랍게도 Switch 도 해시테이블이다. 더군다나 런타임에서 공간을 만들어 내는 Dictionary와 다르게 Switch의 경우컴파일에서 처리를 하기 때문에 검색에 필요한 시간 복잡도 O(log n)이 없어진다.

728x90

LIST

김밥