본문 바로가기
코딩테스트 준비/자료구조 & 알고리즘

C# - 완전 탐색(Brute force, 백트래킹,순열 조합,비트 마스크)

by 코딩하는 돼징 2023. 12. 8.
반응형

완점 탐색

모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법이다.


01 브루트 포스(Brute force)

모든 가능한 결우를 순차적으로 나열하면서 원하는 결과를 찾는 방법이다.

예시 : 비밀번호


02 순열(Permutation)

선택 순서가 결과에 영향을 미치는 경우에 사용하는 방법이다.


03 조합(Combination)

선택 순서가 결과에 영향을 주지 않는 경우에 사용하는 방법이다.


04 백트래킹(BackTracking)

현재 상태에서 가능한 후부군으로 가지를 치며 탐색하는 알고리즘이다. 해가 될 것 같지 않은 경로는 더 이상 탐색하지 않고 되돌아간다.

예시 : 스도쿠


05 비트 마스크(Bit Mask)

이진수의 각 비트를 사용하여 경우의 수를 줄여가며 탐색하는 방법이다.

예시 : 부분 집합


언제 사용할까?

1) 입력으로 주어지는 데이터(N)의 크기가 작은 경우

2) 답의 범위가 작고 임의의 답을 선택한 후 역추적이 가능한 경우

3) 문제 조건 중 하나를 고정 시켜서 문제가 단수화 되는 경우

반응형

댓글