01. 완전 탐색

[1. 개요]

완전탐색이란 가능한 경우의 수를 일일히 나열하면서 답을 찾는 방법

컴퓨터가 충분히 빠르기 때문에 가능한 방법

 

 

 

[2. 재귀호출]

완전히 같은 코드를 반복해서 실행 및 다양한 알고리즘을 구현하는데 매우 유용한 도구

• 재귀 호출 작성 시 유의 할 점
  => 더 이상 쪼개지지 않는 최소한의 작업에 도달한 경우,
       답을 곧장 반환하는 조건문을 반드시(?) 포함하도록 한다.
  => 일명 기저 사례(base case) 에 대한 처리가 필요하다.

중첩 for 문 등을 아주 유용하게 대체 할 수 있다.

완전 탐색 구현 시 아주 유용한 도구

 

 

 

[3. 문제와 부분 문제]

• 문제
  => 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합
  
  
• 부분 문제 (원래 문제의 부분 문제)
  => 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제

 

 

[4. 중복으로 세어서 발생하는 문제(not question)]

한 경우를 중복으로 여러 번 세어서 오답이 발생함

 

이러한 상황을 해결하기 위해 선택 할 수 있는 좋은 방법은 

항상 특정 형태를 갖는 답만을 세는 것

• 사전순으로 가장 먼저 오는 답 하나만을 세는 것
• 2차원 배열에서 가장 윗 줄, 그 중에서도 가장 왼쪽부터 (경우에 따라)
• ...

 

 

 

[5. 기타 팁들]

• 입력이 잘못되거나 범위에서 벗어난 경우를 기저 사례로 택해서 맨 처음에 처리하도록 한다.
  => 실제 핵심 로직 작성 시 입력에 대한 검증이 따로 필요하지 않으며
       간결한 코드를 작성하는데 유용하다.

 

 

[6. 관련 예제]

https://testkernelv2.tistory.com/329

https://testkernelv2.tistory.com/330

https://testkernelv2.tistory.com/331