반응형
완점 탐색
모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법이다.
01 브루트 포스(Brute force)
모든 가능한 결우를 순차적으로 나열하면서 원하는 결과를 찾는 방법이다.
예시 : 비밀번호
02 순열(Permutation)
선택 순서가 결과에 영향을 미치는 경우에 사용하는 방법이다.
03 조합(Combination)
선택 순서가 결과에 영향을 주지 않는 경우에 사용하는 방법이다.
04 백트래킹(BackTracking)
현재 상태에서 가능한 후부군으로 가지를 치며 탐색하는 알고리즘이다. 해가 될 것 같지 않은 경로는 더 이상 탐색하지 않고 되돌아간다.
예시 : 스도쿠
05 비트 마스크(Bit Mask)
이진수의 각 비트를 사용하여 경우의 수를 줄여가며 탐색하는 방법이다.
예시 : 부분 집합
언제 사용할까?
1) 입력으로 주어지는 데이터(N)의 크기가 작은 경우
2) 답의 범위가 작고 임의의 답을 선택한 후 역추적이 가능한 경우
3) 문제 조건 중 하나를 고정 시켜서 문제가 단수화 되는 경우
반응형
'코딩테스트 준비 > 자료구조 & 알고리즘' 카테고리의 다른 글
C# - DFS/BFS 둘 중 어느것을 사용해서 문제를 풀어야 할까? (0) | 2023.12.16 |
---|---|
C# - Where와 Count를 사용해서 배열에 특정 요소의 개수 구하기 (0) | 2023.12.15 |
C# - 모듈러 연산(나머지 분배 법칙) (1) | 2023.12.04 |
C# - 퀵 정렬(Quick Sort) (0) | 2023.11.27 |
C# - PadLeft, PadRight메서드 사용해서 문자열 특정길이로 만드는 법 (2) | 2023.11.21 |
댓글