[자료구조&알고리즘] 탐색(Search)

2025. 5. 23. 17:21·자료구조&알고리즘
반응형

탐색(검색) 알고리즘: 저장된 데이터 중 원하는 값을 찾는 방법


1. 선형 탐색 (Linear Search, 순차 탐색)

  • 방법: 데이터의 처음부터 끝까지 하나씩 차례대로 비교하며 원하는 값을 찾는 방식
  • 특징: 정렬 여부와 상관없이 사용 가능, 구현이 단순하지만 데이터가 많을수록 비효율적
  • 시간 복잡도: O(n)
  • 적용: 정렬되지 않은 배열, 리스트 등
  • 예시

      
[3][8][2][7][5]
↑ ↑ ↑ ↑ ↑
(순서대로 비교)

2. 이진 탐색 (Binary Search)

  • 방법: 정렬된 데이터에서 중간값과 비교하여 더 작으면 왼쪽, 더 크면 오른쪽으로 인덱스를 이용해 절반씩 범위를 줄여가며 찾는 방식
  • 특징: 정렬된 배열이나 리스트에서만 사용 가능, 매우 빠름
  • 시간 복잡도: O(log n)
  • 적용: 정렬된 배열, 리스트
  • 예시:

      
배열: [1, 3, 5, 7, 9]
찾는 값: 5
1. 중간값 5와 비교 → 찾음!

3. 해시 탐색 (Hash Search)

  • 방법: 해시 함수를 이용해 데이터의 저장 위치를 계산하여 바로 접근
  • 특징: 평균적으로 매우 빠름, 충돌 처리 필요
  • 시간 복잡도: 평균 O(1), 최악 O(n)
  • 적용: 해시 테이블, 해시 맵 등
  • 예시: 해시함수(key) → index

      
import java.util.HashMap;
public class HashSearchExample {
public static void main(String[] args) {
// HashMap 객체 생성 (키: String, 값: Integer)
HashMap<String, Integer> hashMap = new HashMap<>();
// 데이터 추가
hashMap.put("Alice", 25);
hashMap.put("Bob", 30);
hashMap.put("Cathy", 35);
hashMap.put("David", 40);
// 키로 값 탐색
String searchKey = "Cathy";
if (hashMap.containsKey(searchKey)) {
int value = hashMap.get(searchKey);
System.out.println("The value for the key '" + searchKey + "' is: " + value);
} else {
System.out.println("The key '" + searchKey + "' is not in the HashMap.");
}
}
}

      
# 해시 테이블 생성
hashTable = [None] * 10
# 데이터 삽입
L = [34, 16, 2, 93, 80, 77, 51]
for num in L:
hashTable[num % 10] = num
# 93을 찾고 싶을 때
key = 93
index = key % 10
if hashTable[index] == key:
print(f"Number {key} found at index {index}")
else:
print(f"Number {key} not found")

4. 이진 탐색 트리 탐색 (Binary Search Tree Search)

  • 방법: 트리 구조에서 각 노드의 값을 기준으로 왼쪽/오른쪽 자식으로 이동하며 탐색
  • 특징: 동적 데이터 삽입/삭제에 적합, 트리 균형에 따라 성능 차이
  • 시간 복잡도: 평균 O(log n), 최악 O(n)
  • 적용: 이진 탐색 트리(BST)
  • 예시:

      
5
/ \
2 8
/ \ \
1 3 9
찾는 값: 3
5(루트) → 2(왼쪽) → 3(오른쪽)

5. 깊이 우선 탐색 (DFS, Depth-First Search)

  • 방법: 트리나 그래프에서 한 분기를 끝까지 탐색한 뒤, 다음 분기로 이동
  • 특징: 스택(혹은 재귀) 사용, 모든 경로를 탐색할 때 유용
  • 적용: 트리, 그래프
  • 예시:

      
0
/ \
1 2
/ \
3-------4
탐색 순서 (0에서 시작, 가능한 한 왼쪽부터):
0 → 1 → 3 → 4 → 2
동작 과정:
0을 방문, 1로 이동
1을 방문, 3으로 이동
3을 방문, 4로 이동
4를 방문, 더 이상 갈 곳 없으니 백트래킹
2로 이동하여 방문.

6. 너비 우선 탐색 (BFS, Breadth-First Search)

  • 방법: 트리나 그래프에서 가까운 노드부터 차례대로 탐색
  • 특징: 큐 사용, 최단 경로 탐색에 유용
  • 적용: 트리, 그래프
  • 예시:

      
0
/ \
1 2
/ \
3-------4
탐색 순서 (0에서 시작):
0 → 1 → 2 → 3 → 4
동작 과정:
0을 방문하고 큐에 0을 넣음
0의 이웃 1, 2를 큐에 추가
1을 방문, 1의 이웃 3을 큐에 추가
2를 방문, 2의 이웃 4를 큐에 추가
3, 4를 차례로 방문.

요약 표

탐색 종류 특징/적용 구조 시간 복잡도 비고
선형 탐색 정렬 불필요, 단순 배열 O(n) 구현 쉬움
이진 탐색 정렬 필요, 배열 O(log n) 정렬 필수
해시 탐색 해시 테이블 O(1) ~ O(n) 충돌 관리 필요
BST 탐색 이진 탐색 트리 O(log n) ~ O(n) 트리 균형 중요
깊이 우선 탐색 트리, 그래프 O(V+E) 스택/재귀
너비 우선 탐색 트리, 그래프 O(V+E) 큐
 

 

반응형

'자료구조&알고리즘' 카테고리의 다른 글

[자료구조&알고리즘] 최소비용신장트리(Prim, Kruskal, Dijkstra 알고리즘)  (1) 2025.05.25
[자료구조&알고리즘] 트리(Tree)  (0) 2025.05.24
[자료구조&알고리즘] 정렬(Sort)  (0) 2025.05.04
'자료구조&알고리즘' 카테고리의 다른 글
  • [자료구조&알고리즘] 최소비용신장트리(Prim, Kruskal, Dijkstra 알고리즘)
  • [자료구조&알고리즘] 트리(Tree)
  • [자료구조&알고리즘] 정렬(Sort)
라텐느
라텐느
이제 막 개발을 시작한 초보가 개인공부를 하는 공간입니다.
  • 라텐느
    괴발개발
    라텐느
    • 개발자 (154)
      • HTML|CSS (14)
      • JAVA (29)
      • JAVACSCRIPT (15)
      • SQL (16)
      • 기타 (5)
      • JSP (2)
      • SPRING (13)
      • SPRING BOOT (6)
      • Git&GitHub (1)
      • 시행착오 (2)
      • 개발일지 (35)
        • GreenMiniProject1 (12)
        • GreenMiniProject2 (9)
        • GreenFinalProject (14)
      • Flutter (5)
      • 자격증 (0)
        • SQLD (1)
      • AWS (2)
      • Linux (1)
      • 자료구조&알고리즘 (4)
  • 블로그 메뉴

    • 홈
    • 방명록
    • 태그
  • 링크

    • GitHub
  • 공지사항

  • 인기 글

  • 태그

    input
    부트캠프
    일지
    CSS
    link
    티스토리챌린지
    javascript
    JQuery
    SQL
    오블완
    개발자
    JS
    태그
    db
    tag
    AJAX
    자기계발
    링크
    HTML
    java
  • 최근 댓글

  • 최근 글

  • 반응형
  • hELLO· Designed By정상우.v4.10.0
라텐느
[자료구조&알고리즘] 탐색(Search)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.