[Algorithm] 재귀 · 탐색

 

Recursion 재귀

 

 

 

 

 

Searching 탐색

탐색 알고리즘 : 데이터 구조에서 특정 값을 찾는 방법

 

1) 선형탐색

linear Search

가장 간단한 형태의 알고리즘

리스트의 처음부터 끝까지 원하는 요소를 찾을 때 까지 하나하나 확인함

100개의 금고 안 중 한개에만 1,000만원이 들어있는 예시

시간복잡도가 최선의 경우 O(1), 최악의 경우 O(n) 

>> n :리스트의 길이

정렬에 대한 의미가 없음

 

 

2) 이진 탐색

이진 탐색은 정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 알고리즘

중간값과 찾으려는 값을 비교해서 검색 범위를 절반으로 줄여나감

매 단계 검사 해야할 요소가 절반으로 줄어들기 때문에 시간복잡도는 O(log N)

>> 엇 훨씬 효율적이네 (데이터가 커지면 커질수록)

 

문제01

 

문제02