자료탐색 알고리즘

자료탐색 알고리즘

• 자료탐색
  • 수많은 자료 중에서 원하는 자료를 찾는 작업
  • 컴퓨터에서 처리되는 핵심 알고리즘 중 하나임
  • 탐색키(탐색 시 기준값. 항목과 항목을 구분하는 값)에 해당하는 인덱스 번호(찾는 자료 없으면 -1) 반환
• 자료 탐색 과정
  • 기준 정하기 (탐색 키 정하기)
  • 자료 비교
  • 자료 찾기 (탐색 성공, 실패 판가름)

 

• 선형 구조 자료 탐색
  
  • 기준은 동일하게 배열 안에 있는 값

정렬되지 않은 자료		정렬되어있는 자료
순차탐색 순서대로 앞에서부터 하나씩 값을 비교함	3   6   1 -----------------> 비교	이진탐색 중간 값과 비교하여 작으면 앞, 크면 뒤 비교를 반복함	|--------> 2  4  6  8  10               |---->

 

• 리스트 형식 자료의 탐색 알고리즘
  • 불규칙 선형, 정렬선형, 색인순차, 보간, 이진탐색, 해시 등등

 

• 트리형식 자료의 탐색 알고리즘
  • 이진탐색, 균형이진탐색, AVL, 2-3, red-black tree 등등

 

• 비선형 구조의 자료탐색

깊이 우선 탐색 (DFS- depth first search)	너비 우선 탐색 (BFS- breadth first search)
시작 노드에서 연결된 간선이 존재하는 경우 계속 깊게 들어가며 탐색하는 알고리즘 (백트래킹) 최하위 레벨 노드에 도달 → 되돌아감 → 다른 길이 연결된 가장 가까운 노드로 이동 → 계속 탐색	루트 노드부터 시작하여 깊이가 1인 모든 노드들을 우선비교 탐색 → 싶이 2인 모든 노드 비교탐색 → 깊이 3인 노드들을 대상으로 비교탐색 반복적으로 깊이 증가마며 탐색범위를 확장하는 알고리즘
시작: 1 1 → 2 → 3 → 4 → (backtrack) → 6 → (backtrack) → 8 → 12	시작: 1 1 → 2, 8 → 3, 6, 9, 12 → 4, 10
▶ Stack 기반 탐색 기록	▶ Queue 기반 탐색 기록
경로탐색, 백트래킹 유용	최단거리 찾기에 유리 + 자료 깊이 클수록 유리

 

 

• 코드예시 (C++, BFS)

// BFS (큐)
void bfs(int start) {
    unordered_set<int> visited;
    queue<int> q;

    visited.insert(start);
    q.push(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";

        for (int neighbor : graph[current]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

• 코드예시 (C++, DFS)

// DFS (재귀)
void dfs(int node, unordered_set<int>& visited) {
    visited.insert(node);
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            dfs(neighbor, visited);
        }
    }
}