알고리즘 학습 · 탐색
하나를 골라 단계별로 살펴봐요
배열과 그래프에서 원하는 값이나 경로 찾기
배열 탐색
선형 탐색
O(n)배열의 처음부터 값을 하나씩 확인해 찾는 값과 비교합니다.
이진 탐색
O(log n)정렬된 배열의 중간값을 확인하면서 탐색 범위를 절반씩 줄입니다.
점프 탐색
O(√n)정렬된 배열을 일정 간격으로 확인해 후보 구간을 찾은 뒤, 그 구간을 순서대로 탐색합니다.
지수 탐색
O(log n)확인할 인덱스를 두 배씩 늘려 후보 구간을 찾고, 그 안에서 이진 탐색을 수행합니다.
보간 탐색
O(log log n) avg정렬된 수치 데이터에서 값의 크기를 이용해 목표값의 위치를 추정합니다.
삼진 탐색
O(log₃ n)두 지점을 비교해 탐색 구간을 세 부분으로 나누고 후보 범위를 줄이는 방법입니다.
피보나치 탐색
O(log n)피보나치 수를 이용해 정렬된 배열의 확인 위치와 다음 탐색 범위를 정합니다.
