완전탐색

완전탐색 이란?

• 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법
  • 무식하게 가능한 것을 다 해보는 것 (= Exhaustive search, Brute force)
• 직관적이어서 이해하기 쉽고, 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하고 기초적인 방법
• 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게 됨
• 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용
• 효율적으로 동작하지는 않음

완전탐색 기법 활용

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2. 가능한 모든 방법을 다 고려한다.
3. 실제 답을 구할 수 있는지 적용한다.

완전탐색 방법

Brute Force

• 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법
• 이 방법만을 사용하는 문제는 거의 나오지 않음
  • ex) 자물쇠 암호 찾기

Bitmask

• 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 나뉘는 경우 유용하게 사용
  • ex) ‘원소가 n개인 집합의 모든 부분 집합’
    • 각 원소가 포함되는지, 되지 않는지 0,1로 구분하여 배열에 저장해둠

AND연산 (&)	둘 다 1이면 1
OR연산	둘 중 1개만 1이면 1
NOT연산 (~)	1이면 0, 0이면 1
XOR연산 (^)	둘의 관계가 다르면 1, 같으면 0
Shift연산 (<< ,>>)	A<<B라고 한다면 A를 좌측으로 B 비트만큼 미는 것

재귀함수

• Bitmask와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용하게 사용
• 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출
  • ex) 피보나치 수열
• 시간 복잡도 O(N)

1. 재귀를 탈출하기 위한 탈출 조건 필요
2. 현재 함수의 상태를 저장하는 Parameter 필요
3. Return문을 신경 쓸 것

순열

• 서로 다른 N개를 일렬로 나열하는 방법
• 모든 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리수가 되어야 함
• 순열에 원소를 하나씩 채워가는 방식
• 재귀함수 이용
• 시간 복잡도 O(N!)

너비 우선 탐색(Breadth-Fist Search, BFS)

• 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문
• 재귀적으로 동작하지 X
• 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐 사용 (FIFO)
• 넓게 탐색
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

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

• 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색
• 재귀적으로 동작 (재귀, 스택)
• 모든 노드를 방문하고자 할 때 사용
• BFS보다 간단, BFS에 비해 검색속도가 느림

BFS & DFS

• 그래프 탐색의 경우, 노드 방문 여부 검사 필수 (검사하지 않으면 무한루프)
• 길 찾기 등에 주로 쓰이는 알고리즘 → 단순 길찾기에는 BFS/DFS만 써도 무방하지만,장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색 병용 ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고 A와 B 사이에 존재하는 경로 찾을 때
  • BFS : A와 가까운 관계부터 탐색한다.
  • DFS : 모든 친구 관계 다 살펴야한다.