가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법. → 무식하게 다 순회하면 됨
CS에서 문제 해결 알고리즘을 사용할 때 기본적인 두가지 규칙.
1) 사용된 알고리즘이 적절한가 (문제를 해결할 수 있는가)
2) 효율적으로 동작하는가
고려할 사항은 다음과 같다
1) 가능한 경우의 수를 대략적으로 계산
2) 가능한 모든 방법을 다 고려
3) 실제 답을 구할 수 있는지 적용
2에서의 모든 방법
- 완전탐색 → 반복/조건문을 통해 모든 경우의 수를 테스트하는 방법
- 순열(Permutation) → n개의 원소 중 r개의 원소를 중복 허용없이 나열하는 방법
- 재귀 호출 (Recursive)
- BFS, DFS
- 비트마스크 - 2진수 표현 기법을 활용하는 방법
순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법이다. 즉, 순서가 중요하다! → [1, 2, 3] ≠ [3, 2, 1] 같은 데이터가 입력된 수열이지만, 그 순서에 따라 의미가 있고 이 순서를 통해 연결되는 이전/다음 수열을 찾아낼 수 있는 경우에 계산할 수 있다.
자기 자신을 호출하는 것을 의미한다. 예를 들어 “숫자 n개 중 m개를 고르는 경우”를 보자. 이중 반복문으로 문제를 해결하게 되면, n과 m이 매우 큰 숫자라면..? 재귀 함수를 활용하여 자기 자신을 호출함으로써 다음 숫자를 선택할 수 있도록 이동시켜 전체 코드를 짧게 줄일 수 있다.
포인트
- 재귀를 탈출하기 위한 탈출 조건이 필요하다
- 이것이 없으면 n개를 모두 골랐음에도 더 숫자를 선택하고자 하여
- 선택된 숫자를 저장하는 배열에 범위 초과 오류가 나거나
- 다른 자료구조를 쓴 경우 잘못된 출력이 나올 수 도 있고
- 무한 루프가 발생할 수 있다.
- 현재 함수의 상태를 저장하는 parameter가 필요하다
- current, count를 통해 어떤 숫자까지 선택했는지, 몇 개를 선택했는지 전달해야 한다.
- 이것이 없다면 현재 함수의 상태를 저장할 수 없어서, 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 된다.
- return 문을 신경써야 한다
- 재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우도 있을 수 잇다.
- 즉, 문제 해결을 위한 정확한 정의를 수행해야 한다.
DP와 매우 흡사
top-down을 사용하면 재귀를 통해 수행하는데, 기저 사례를 통해 탈출 조건을 만들고, 현재 함수의 상태를 전달하는 parameter를 전달하고, return을 통해 필요한 값을 반환하여 ㄷ바을 구하는 연산에 사용한다.
완전 탐색의 재귀와 DP의 차이점
DP는 작은 문제가 큰 문제와 동일한 구조를 가져 큰 문제의 답을 구할 시에 작은 문제의 결과를 기억한 뒤 그대로 사용하여 수행 속도를 빠르게 한다.
완전탐색은 크고 작은 문제의 구조가 다를 수 있고, 이전 결과를 반드시 기억하는 것이 아니라 해결 가능한 방법을 모두 탐색한다는 차이가 잇다.
- 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.
BFS (너비 우선 탐색)
- 현재 정점과 인접한 정점을 우선으로 탐색한다.
DFS (깊이 우선 탐색)
- 현재 인접한 정접을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색한다.