완전 탐색 푸는 방법

1. 모든 정답 후보를 살펴보고 정답 구하기
2. 모든 문제 풀이의 시작은 완전 탐색이다.
3. 코테의 절반은 완전 탐색으로 끝난다. → 나머지 절반은 최적화 조금

안테나 문제를 읽고 해야할 일

1. 문제를 보고 표를 작성 → 1 ~ N까지 가능한 경우의 수를 표로 만들기
2. 표를 보고 경향성을 파악하기
   1. 값이 작아진다 or 커진다
   2. 왜 중간에 10인 값들이 있는가?
   3. 홀수면 가운데가 최적 위치, 짝수는 가운데 중심으로 좌우에서 최적

편의점

• 안테나를 2차원으로 확장한 문제
• x, y 좌표는 서로 영향이 없다
• x의 중앙값, y의 중앙값으로 모이면 최소 거리를 구할 수 있겠죠?

체커

• 시간, 범위를 보고 어떤 알고리즘으로 풀까? 라는 생각은 이제 버려라 → 무조건 완탐 먼저 생각

• 접근할 수 있는 방법 (여러가지 완탐 관점이 존재할 수 있음)

  • 모든 조합 해보기 → 오래 걸리는걸 알았으니 다른 관점으로 보자 → 답이 될 수 없는 점 조합을 고르겠다(최적화) → 점을 다 보기 때문에 똑같이 오래 걸림
    • 4개 중에서 1개 → 4 가지
    • 4개 중에서 2개 → 6 가지
    • 4개 중에서 3개 → 4 가지
    • 4개 중에서 4개 → 1 가지
    • 50개면? → 2^N - 1 → 상당함
  • 좌표 기준으로 확인하기 (1, 1) ~ (100만, 100만) → 얘도 오래 걸림
    • 1, 1 기준으로 N개의 거리 구하기 → 모든 경우를 탐색하고 최소값 찾기

• 가능한 완탐 관점 몇 가지를 최대한 생각 → 안된다?

  • 답이 될 수 없는 좌표를 거르겠다. (다음 해야 할 일의 방향성) → 이 방법을 최적화 해보자
  • 느리면 다음에 뭘 할지 다시 생각

• 최적화 방향을 생각하기

  • 점이 있는 x,y 교점들만 확인해보면 된다
    • 점이 있는 x좌표, y좌표만 확인하기
  • 교점의 개수 N^2개만 확인하면 된다