[알고리즘] 이진 탐색과 완전 탐색

이진 탐색

이진 탐색 알고리즘이란?

매 탐색마다 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 

단, 리스트(배열)이 정렬되어 있어야 함

한번 탐색을 수행할 때 마다, 탐색의 범위가 반으로 줄어들기 때문에 시간 복잡도는 O(logN)

 

https://www.google.com/url?sa=i&url=https%3A%2F%2Fchamdom.blog%2Fbinary-search%2F&psig=AOvVaw07DVovQxS6E2ZnFpum__6-&ust=1718969229405000&source=images&cd=vfe&opi=89978449&ved=0CBEQjRxqFwoTCLjK-cSJ6oYDFQAAAAAdAAAAABAE

 

동작 방식

 

1. 배열의 중간 값을 가져온다

 

2. 중간값과 검색값을 비교

 

  2-1. 중간 값 == 검색 값

          종료

  2-2. 중간 값 < 검색 값

          중간 값 기준 배열의 오른쪽 구간을 대상으로 탐색

  2-3. 중간 값 > 검색 값

          중간 값 기준 배열의 왼쪽 구간을 대상으로 탐색

 

3. 값을 찾거나 간격이 비어있을 때까지 반복

 

 

이진 탐색의 장단점

• 단점: 정렬된 리스트에서만 사용할 수 있다
• 장점: 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 매우 빠르다
  • 시간 복잡도: O(logN)

 

 

 

완전 탐색 알고리즘이란?

 

Exhaustive search, Brute force

간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법

 

완전 탐색 알고리즘의 종류 

https://adjh54.tistory.com/197

• Brute-Force 
  • 반복문/조건문을 사용해서 가능한 모든 방법을 단순하게 찾는 기법 
• 비트 마스크 (Bitmask)
  • 이진수를 사용하는 컴퓨터의 연산 방식을 이용
  • 문제에서 확인해야하는 경우가 두가지 선택지 중 하나일 때 유용
• 백트래킹 (Backtracking)
  • 답을 찾는 과정에서 이 경로가 답이 아니라고 판단되면 버리고 다른 경로를 탐색하는 방법
  • 가지치기(Pruning)이라고도 함 
  • 반복문의 횟수를 줄일 수 있지만, 최악의 경우에는 여전히 완전 탐색을 해야 함
• 재귀함수
  • 답을 찾을 때까지 자기 자신을 반복적으로 참조하는 함수
  • 직관적이고 간단
  • 종료조건이 필요함
• 순열
  • 완전 탐색의 대표적인 유형
  • 서로 다른 n개의 원소에서 r개를 중복 없이 골라 순서대로 나열하는 것
• BFS(너비 우선 탐색)
  • 최대한 넓게 이동한 다음, 더 이상 이동할 곳이 없을 때 아래로 이동
  • 큐
• DFS(깊이 우선 탐색)
  • 최대한 깊게 내려간 뒤, 더 이상 내려갈 곳이 없을 때 옆으로 이동
  • 스택/재귀 함수

 

완전 탐색의 장단점 

 

장점

• 구현이 단순하고 이해하기 쉽다.

단점

• 시간 복잡도가 매우!! 높음 
  • O(n!) 또는 O(2^n)
  • 입력 크기가 조금만 커져도 실행 시간이 급증
  • 비효율적

 

그럼에도 완전 탐색이 쓰이는 경우

• 모든 가능한 경우를 다 시도해봐야 하는 경우
• 문제의 입력 크기가 작을 때

 

 

---

예상 면접 질문

 

• 이진 탐색을 장단점을 들어 설명해주세요.
  • 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만,
  • 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 매우 빠르다는 장점이 있다.
• BST와 Binary Tree에 대해 설명해주세요.
  • 이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리
  • 이진 탐색 트리는 이진 탐색과 연결리스트를 결합한 자료구조
    • 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있음
• 완전 탐색을 장단점을 들어 설명해주세요.
• BFS와 DFS에 대해 각각 설명해주세요.

 

---

출처

면접 질문 🌟🌟🌟

https://dev-coco.tistory.com/159

신입 개발자 기술면접 질문 정리 - 자료구조

 

개념

https://hongjw1938.tistory.com/78

알고리즘 - 완전탐색(Exhaustive Search)

https://velog.io/@hyehyes/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89

[알고리즘] 완전탐색

https://adjh54.tistory.com/197

[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -2 : 종류 별 이해