완전탐색
- 모든 경우의 수를 시도하여 정답을 찾는 방법이다.
- 무식하게 푼다는 의미로 Brute Force 라고도 한다.
- 상대적으로 간단하지만 경우의 수가 많아지면 시간이 길어지는 단점이 있다.
1. 단순 Brute-Force
- 특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함
- 이 방법으로 풀 수 있는 문제는 많지 않음
2. 비트마스크
- 각 원소를 두 가지 상태로 분류할 수 있을 때 사용
- 모든 경우의 수에서 각각의 원소가 포함되거나 포함되지 않는 경우
- 포함되면 1, 포함되지 않으면 0으로 구분한다 -> 2진수
- EX) 원소 n개인 집합의 부분집합 구하기
- 자세한 건 아래 게시글
- https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-8-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9
3. 재귀함수
- 재귀는 자기 자신을 호출한다는 뜻이다. -> 자기 함수 안에서 자기 함수를 다시 호출하는 작업을 수행한다.
- 호출된 함수 스택에 저장, 호출 완료시 스택에서 삭제
- for, while 같은 반복 코드를 간결하게 짤 수 있음
- 주의사항
- 사이클이 발생하면 안된다. -> 재귀 탈출 조건이 없는 경우 재귀함수는 계속하여 자기 자신을 호출하는 무한루프에 갇히고 스택 오버플로우가 일어난다.
- 재귀 탈출 조건을 적어주거나 재귀 발생 횟수를 적어줘야 한다.
4. 순열
- 서로 다른 n개를 일렬로 나열하는 경우의 수 (순서 o)
- n!
- 서로 다른 n개중 r개를 뽑아 일렬로 나열하는 경우의 수 (순서 o)
- n!/(r-1)! = nPr
- 시간 복잡도: O(n!)
- 시간복잡도가 높은 편이라 n이 한자리 수 일경우일 때 고려
- c++에서는 함수가 있지만, 자바에서는 직접 구현해야 한다.
- 코드
public class PermutationMain {
// 순열 구하기
public static void Permutation(String[] arr, int stat, int end) {
if(start == end) {
for(String s : arr) {
System.out.print(s+" ");
}
System.out.println();
}
else {
for(int i = start; i <= end; i++) {
swap(arr, start, i);
Permutation(arr, start+1, end);
swap(arr, start, i);'
}
}
}
// 인덱스 원소 바꾸기
public static void swap(String[] arr, int a, int b) {
String temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// EX) arr = ["A", "B", "C"] 순열 출력
public static void main(String[] args) {
String[] arr = {"A", "B", "C"};
Permutation(arr, 0, arr.length - 1);
}
}
// 출력
A B C
A C B
B A C
B C A
C A B
C B A
5. BFS / DFS
- 자세한 건 게시글 참조.
- https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-4-DFS-BFS
알고리즘 문제 추천
- 사탕 게임 (실버 2)
- 1, 2, 3 더하기 (실버 3)
- 가르침 (골드 4)
- 호석이 두 마리 치킨 (골드 5)
참고 자료
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89
'CS > 자료 구조 및 알고리즘' 카테고리의 다른 글
[알고리즘 이론] 8. 비트마스킹 (1) | 2023.05.09 |
---|---|
[알고리즘 이론] 7. 백트래킹 (0) | 2023.05.09 |
[알고리즘 이론] 5. 트리순회 (0) | 2023.05.05 |
[알고리즘 이론] 4. DFS, BFS (0) | 2023.05.05 |
[알고리즘 이론] 3. 그래프이론 (0) | 2023.05.05 |
댓글