WEEK01 | 완전탐색

1. 완전탐색이란?

• 가능한 모든 경우의 수를 다 탐색해서 답을 찾는 방법
  // 무식하게 가능한 거 다 해보겠다 뭐 그런 뜻
  // 브루트 포스(Brute Force) 라고도 함
  // 직관적, 정확하고 기초적인 방법
  // 시간, 메모리는..?
  ⇒ ㅇㅇ 그거때문에 제한적으로 사용
  
• 알고리즘을 사용할때는
  1. 적절한 알고리즘인가(문제해결가능한지)
  2. 효율적으로 동작하는가
  두 가지를 고려하는데, 1번은 확실하지만, 2번은 그렇지 않음
• 완전탐색을 사용하는게 효율적인지 문제파악이 먼저돼야함

2. 방법

• 고려할 사항

1. 해결하려는 문제의 경우의 수를 대략적으로 계산

2. 가능한 모든 방법을 고려

3. 실제 답을 구할 수 있는지 적용

   🔑 가능한 모든 방법

   1. 브루트 포스 - 반복/조건문을 활용해 모든 경우를 테스트
   2. 순열(Permutation) - n개의 원소 중에 r개의 원소를 중복 없이 나열하는 방법
      // 조합, 중복순열, 중복조합, 같은 것이 있는 순열, 원순열 얘들도..?
   3. 재귀 호출
   4. 비트마스크 - 2진수 표현 기법을 활용하는 방법
      // 그냥 리스트 만들어서 인덱스에 맞게 0,1넣으면서 쓸수도
   5. BFS(너비우선탐색), DFS(깊이우선탐색)를 활용

① 브루트 포스

• 반복, 조건문을 통해 가능한 모든 경우를 찾는 방법
• 단순하고 무식하게 다해보기
• like 자물쇠 0000~9999

② 순열

• 순열 : 서로 다른 n개 중에 r개를 선택하는 경우 ( 순서O / 중복X )
  // 1,2,3 ≠ 2,1,3 ≠ 3,2,1

• 같은 데이터를 가지고 순서를 통해 연결되는 이전, 다음 수열을 찾아내는 경우를 계산할 수 있음(?)
  // Permutation 함수 구현 가능

• 그냥 n개를 줄 세우는 경우의 수는 n!

• 사전 순 정렬을 해보면 어떻게 돌아가는지가 잘 보임

  123을 사전순으로 정렬하도록 돌리면
  ⇒ 123(최초순열) 132 213 231 312 321(최종순열)
  1234를 돌리면
  ⇒ 1234(최초순열) 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321(최종순열)

• n개의 데이터가 있고 각 인덱스를 기준으로 0번째 인덱스가 i인 경우중에 1번째 인덱스부터 최초순열은 오름차순, 최종순열은 내림차순으로 나타남
  i=1 일 때 ⇒ 1234(최초순열) 1243 1324 1342 1423 1432(최종순열)

• 0이랑 1로 말했지만 x번째 인덱스를 고정하면(x-1번째까지는 그대로고)
  x+1번째 인덱스부터 봤을때 최초순열은 오름차순, 최종순열은 내림차순임

• 내림차순이 끝나면 다음으로 넘어가야하는데
  x번째를 고정하면 x+1부터 끝(n)까지 내림차순인 경우가 최종순열로 끝이나고
  다음은 x+1번째부터 오름차순이 되는 최초순열이 돼야함
  x는 x+1부터 n까지 자신보다 크지만 가장 작은 숫자와 교환하고
  x+1부터 n은 다시 오름차순이 됨

🔑 순열을 구현하는 방법

• 현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자. 예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.
• 아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.

1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)

   → 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음

   A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.
   

2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.

   → 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.

   A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.
   

3. A[i-1]과 A[j]를 Swap한다.

   → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.

   A={7, 2, 4, 6, 5, 3, 1}
   

4. i이후의 순열을 모두 뒤집는다.

   → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.

   A={7, 2, 4, 1, 3, 5, 6}*
   

• 이렇게 구하면 시간복잡도가 O(N!) 임 // 아주 높은거
• 그래서 이 방법은 문제에서 주어진 n의 크기를 고려해야함

③ 재귀

• 재귀 = 자기 자신을 호출
• 2중 3중 for문 즉, 다수의 반복문을 대체함
• 재귀 Point

1. 탈출 조건 : n개를 모두 고르거나, 범위를 다 돌거나, 등등
   // 재귀가 끝나는 지점을 만들어줘야함
   // index에러나 무한루프가 발생할 수 있음
2. 현재 상태를 저장하는 파라미터 : 뭘 골랐는지, 몇개를 골랐는지, 어디까지 했는지 등등
   // 얼마나 진행했는지 전달해야함
   // 이걸 알아야 탈출조건도 만들지
3. return문 주의 : 연산결과를 반환하거나 추가 연산을 해야하는 경우 반환하는 경우나 값을 유의할 것

④ 비트마스크

- 

⑤ DFS

- 

참고 :: https://hongjw1938.tistory.com/78#1.-완전탐색-알고리즘이란?