Algorithm/개념

[알고리즘][파이썬] Exhaustive Search / 완전 탐색

y-seo 2023. 7. 8. 01:27

2023.07.07... 5학기 여름방학에 다시 시작하는 혼자 하는 알고리즘 레쮸고 !!!!!!!!!

 

완전 탐색이란

  • 모든 경우의 수를 다 세는 방법
  • Brute force
  • 직관적이어서 이해하기 쉬운 방법
  • 상대적으로 구현이 간단한 방법
  • 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법
  • 시간 복잡도가 O(N^2)인 방법
  • 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용

완전 탐색 알고리즘 종류

  1. Brute Force
  2. Bitmask (비트마스크)
  3. Recursive (재귀)
  4. Permutation (순열)
  5. BFS (너비우선탐색) & DFS (깊이우선탐색)

Brute Force

  • 반복문 or 조건문으로 모든 경우를 체크하여 정답 구하기
  • (ex) 000~999 사이의 자물쇠 암호를 하나하나 돌려가며 찾기

Bitmask (비트마스크)

  • 비트 연산을 통해 부분 집합을 표현하는 방법
  • 나올 수 있는 모든 경우의수가 각각의 원소가 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우에 사용
  • (ex) 0~8까지의 숫자로 이루어지는 정수 집합 중 하나의 부분 집합 A를 A = {1, 2, 3, 8} 라고 가정하자
    • 이때 부분 집합 A를 하나의 숫자로 나타낼 수 있다
    • 아래 표를 참고하여 100001110라는 이진수로 나타낼 수 있으므로 10진수로는 270이다 
숫자 8 7 6 5 4 3 2 1 0
비트 1 0 0 0 0 1 1 1 0
  • 위와 같이 정수로 사용하면 전체 저장 공간 절약과 인덱스 활용이 가능하다
  • 처리할 전체 데이터가 정해져 있고 그 안에서 특정 개수를 가지고 연산을 수행할 때 사용
  • 시간 복잡도 = O(1)
  • 비트 연산 사용 방법
    1. 집합 포함 여부 검사
      • 부분 집합에 어떤 원소가 포함되어 있는지 검사할 때 AND 연산을 통해 확인 가능
      • (ex) 부분 집합 A에 0이 있나? → 100001110 & 000000001 = 000000000 → 없네!
    2. 숫자 추가
      • 부분 집합에 특정 원소를 추가하려 할 때 OR 연산을 통해 추가 가능
      • (ex) 부분 집합 A에 5를 추가해야지 → 100001110 | 000100000 = 100101110
    3. 특정 숫자 제거
      • 부분 집합에서 특정 원소를 제거하려 할 때 NOT 연산과 AND 연산을 통해 제거 가능
      • (ex) 부분 집합 A에서 8을 제거해야지 → 8(10) = 100000000(2) 을 NOT 연산 → 011111111(2) → 100001110 & 011111111 = 000001110
    4. 토글 연산
      • 부분 집합에서 특정 원소가 있으면 제거하고, 없으면 추가하려 할 때 XOR 연산을 통해 가능
      • (ex) 부분 집합 A에서 3을 토글해야지 → 100001110 ^ 000001000 = 100000110
    5. 전체 집합, 공집합 표현
      • 전체 집합 = ( 1 << N ) - 1
      • 공집합 = 0

Recursive (재귀)

  • 자기자신을 호출하는 방법
  • 비트마스크와 유사하게 각 원소가 두 가지 선택지를 가질 때 사용
  • 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 식으로 사용
  • 시간 복잡도 = O(N)
  • (ex) 피보나치 수열
  • 신경써야 할 포인트
    • 탈출 조건
    • 현재 함수의 상태를 저장하는 파라미터 필요
    • return문 여부
  • 다이나믹 프로그래밍과의 차이점 : 완전 탐색은 해결 가능한 방법을 모두 탐색한다 → 다이나믹 프로그래밍은 일반적인 재귀 중 조건을 만족하는 경우에 적용 가능

Permutation (순열)

  • 서로 다른 N개를 일렬로 나열하는 경우의 수 → 순서가 중요
  • 시간 복잡도 = O(N!)
  • {a, b, c}를 사전식으로 나열하면 {a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a} 
    • {a, b, c}가 최초 순열 (오름차순), {c, b, a}가 최종 순열 (내림차순)
    • 사전식 순열의 규칙 : N개의 데이터가 있고 1 ~ i 번째 데이터 설정시, i번째 데이터 기준 최종 순열은 i+1부터 N까지가 모두 내림차순, 반대로 최초 순열이면 i+1부터 N까지가 오름차순
    • 위 규칙을 통해 이전/다음 순열을 구할 수 있다
    • 위 규칙을 통해 모든 순열을 완전 탐색하는 로직을 구현할 수 있다

BFS (너비우선탐색) & DFS (깊이우선탐색)

  • BFS : 현재 정점과 인접한 정점을 우선으로 탐색
  • DFS : 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색
  • 별도 포스팅 예정

참고 : 겐지충 프로그래머 :: 알고리즘 - 완전탐색(Exhaustive Search) (tistory.com)

저작자표시