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

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)