본문 바로가기
PS/Algorithm

[알고리즘 개념정리] 6. 완전탐색/백트래킹

by 이지이즤 2022. 1. 29.

**본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.**

 

 

완전 탐색(Brute Force)

: 모든 경우를 탐색해 가면서
  무언가를 세거나 어떤 조건이 가능한 경우가 있는지 확인하는 방법

 

★ 완전 탐색 문제 판별법

  • 하나의 경우마다 따져야 할 게 명확한 경우
  • 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제
  • 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 적은 경우 (N제한이 작을 때!!)

 

★ 완전 탐색 문제 접근법

  • 모든 경우(상태)를 생성할 수 있는 방법을 생각한다.
  • 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크한다.
    * 문제에 따라 모든 경우를 따질 필요가 없거나 각 경우에 대해 체크할 조건이 없는 등의 상황도 있다.

 

 

 

백트래킹

: 재귀를 이용한 완전 탐색!!
  현재 상태에서 전이될 수 있는 다음 상태들을 재귀적으로 탐색하다가
  특정 조건을 만족하면 문제에서 따져야 하는 무언가가 된다

*재귀?
: 재귀 함수는 자기 자신을 호출하는 함수이다.
  자기 자신을 호출하지만 호출할 때 다른 상태를 전달해서 호출한다. (사이클 형성되면 안됨)
  재귀 호출을 하면서 상태가 점차 base case(종료 조건)에 가까워져야 한다. 

 

★ 백트래킹 문제 접근법

  • 초기 상태가 무엇인지 생각한다.
  • 거기서 재귀적으로 전이될 수 있는 상태가 무엇인지 생각한다.
  • 생성하고 있는 상태가 어떤 사전 조건(base case)을 만족하게 된 경우
    문제에서 따져야하는 상태가 되는지 고민한다.
  • 생성된 상태를 어떻게 보관하고 어떻게 문제의 조건에 대해 따져줄지 고민한다.
  • 만들어진 상태에서 어떻게 이전 상태로 돌아가고 무엇을 보존할 지 고민한다.

 

★ 백트래킹에서 가지치기

  • 가능한 경우들 중 하나만 필요하다면 그 하나를 찾는 순간 나머지를 더 탐색할 필요가 없어진다.(-> exit)
  • 상태를 전이시켜가는 도중 우리가 목표하는 상태에 도달할 수 없다는 것을 미리 알수 있는 경우가 있다.
    즉, 모든 경우에 대해 따져주지 않아도 될 때가 있다.

 

 

 

 

관련 문제

'PS > Algorithm' 카테고리의 다른 글

[알고리즘 개념정리] 8. 그래프/그래프 탐색  (5) 2022.02.05
[알고리즘 개념정리] 7. 이분탐색/분할정복  (0) 2022.02.02
[알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)  (0) 2022.01.27
[알고리즘 개념정리] 4. 그리디  (0) 2022.01.22
[알고리즘 개념정리] 3. 동적계획법(DP)  (0) 2022.01.19

관련글

댓글

티스토리툴바