[알고리즘] 선형 자료 구조에서 탐색(Search)

자료구조 초반에 등장하는 내용

확실히 정리하고 가도록 하자.

 

3가지 형태의 Search

1) find arbitrary

- 원하는 임의의 원소를 찾는다.

 

2) find first/last

- 가장 처음으로/마지막으로 들어온 원소를 찾는다.

 

3) find max/min

- 가장 큰/작은 원소를 찾는다.

 

 

 

또 다른 탐색 Traversal

비선형자료구조(트리, 그래프)에서 사용하는 탐색이다.

주어진 집합 내에서 시작원소로부터 도달 할 수 있는 모든 원소를 찾는 과정이다.

 

 

선형/비선형 자료구조

선형 자료구조는

배열, 연결리스트, 스택, 큐

비 선형 자료구조는

그래프. 트리 가 있다.

 

자료 구조에 따라 분류

1) 선형

자료구조	search	알고리즘	시간 복잡도
			검색	추가	삭제
sorted array	arbitrary	linear search	O(N)	O(N)	O(N)
		binary search	O(logN)
		interpolation search	O(logN)
	top	find max/min	O(1)
stack	arrival	pop	O(1)	O(1)	O(1)
queue		push

 

2) 비선형

자료구조	search	알고리즘	시간 복잡도
			검색	추가	삭제
bst	arbitrary	search	O(logN)/O(N)	O(logN)/O(N)	O(logN)/O(N)
heap	top	find max/min	O(1)	O(logN)	O(logN)
hash	arbitrary	hashing	O(1)	O(1)	O(1)

 

 

 

Search 종류에 따라 분류

1) find arbitrary

 

자료구조	알고리즘	시간 복잡도
		검색	추가	삭제
sorted array	linear search	O(N)	O(N)	O(N)
	binary search	O(logN)
	interpolation search	O(logN)
bst	search	O(logN)/O(N)	O(logN)/O(N)	O(logN)/O(N)
hash	hashing	O(1)	O(1)	O(1)

선형 자료 구조에서 임의의 값을 찾는 경우 이진탐색을 사용하자

 

 

2) find first/last

 

자료구조	알고리즘	시간 복잡도
		검색	추가	삭제
stack		O(1)	O(1)	O(1)
queue

 

 

3) find max/min

자료구조	알고리즘	시간 복잡도
		검색	추가	삭제
sorted array		O(1)	O(N)	O(N)
heap		O(1)	O(logN)	O(logN)

최댓값/최솟값을 찾을 땐 우선순위큐를 사용하자