[ps]dfs로 조합,순열,중복 끝장보기 (다시 정리)

06 Jun 2024

6.12에 다시 시험이다.. 하지만 나에게 남은건 도로묵의 정신 상태일뿐.. 기억이 다 안난다., 지금까지 풀었던 것들을 다시 한 번 리마인드 해서 얹고 다음 step으로 가자. (어차피 Pro 딸떄도 기억안나면 다시 다해야함)

순열, 조합, 중복 순열, 중복 조합

DFS 개념을 잡을 떄 해당 조합 문제를 푸는 것이 직관적인 방법중에 하나 인것 같다. (사실 new_permutaion stl을 쓰면 웬만한건 다 풀린다.)

backtracking의 개념도 해당 조합 문제를 풀떄 들어가고, 조합과 순열의 개념을 잡는 방식에서도 DFS는 유용하다. (사실 완전 탐색의 문제중 하나기에 논리는 일맥상통 할 것이다.)

DFS는 결국 방문처리의 개념일텐데,, 이부분은 DP memoization하고 비슷할 것 같다. -> 순열 조합에서는 selected 개념이 들어가면 될 것 같다. -> 기존에는 map에서 visited를 통해 완전탐색을 진행했다. 그래서 visited를 어따가 넣어서 처리할것인가에 따라 복잡도가 달라짐

[1,2,3,4,5] 의 map에서 3개를 고른다고 가정하자
5C3, 5P3

1. 조합

1,2,3,4,5 5개의 숫자중에서 순서 없이 3개를 뽑는 것!

즉, 1,2,3 을 뽑던, 1,3,2를 뽑던 같음 (순서를 생각하려면 순열!)

#include <iostream>
using namespace std;

int map[5] = {4,2,1,3,5};
int n = 5; k = 3;
int select[5] = {0,};  // select는 각 map의 자릿수들이 뽑혔는지 여부를 판단하기 위함

void DFS(int select[], int idx, int cnt){
  if(cnt == k){ // k개 만큼 뽑으면 종료시키기, 이떄 select들은 각 자리수 만큼 위치가 되도록 뽑혔을 것임 
    print(select,map); // select의 index가 1이면 map의 해당 값을 출력하기 
    return ;
  }

  for (int i= idx; i<n; i++){
    if(select[i] ==1) continue;
    select[i] = 1;
    DFS(select,i,cnt+1); // 4 2 1, 4 2 3, 4 2 5,  
    select[i] = 0;
  }

}

int main(){
  DFS(select,0,0);
  return 0;
}

2. 중복 조합

조합과 중복 조합의 차이는 뽑았던 것을 중복으로 뽑을 수 있는가의 차이다. 즉, 4를 뽑고 다시 4를 뽑을 수 있다. 즉, 4 4 4 가 된다는 의미! 그러면 코드는 어떻게 짜야할까?

기존의 조합 코드에서 어떤점이 달라지면 될까? 생각해보면된다. 조합과 순열의 차이점은 idx를 dfs로 계속 넘겨준다는 차이점이 있다면, 조합과 중복조합의 차이는 select를 넣는냐 넣지 않느냐의 차이로 귀결시킬 수 있다. 그러면 어떻게 값을 누적시킬것인가? 그건 새로운 vector를 DFS로 돌리자!

#include <iostream>
using namespace std;

int n = 5 ; k = 3;
int map[5] = {4,3,2,1,5}

void dfs(int idx, int cnt, vector<int> v){
  if(cnt == k){ //원하는 수 만큼 뽑았으면 그만 뽑기
    print(v);
    return;
  }
  else{
    for(int i = idx ; i<n; i++){
      v.push_back(map[i]);
      dfs(i,cnt+1,v);
      v.pop_back();
    }
  } 

}

int main(){
  vector<int> v;
  dfs(0,0)
  return 0;
}

3. 순열

순열과 조합의 차이는 이전에도 말했지만, 순서있게 뽑는가! 의 차이이다. 4 3 2 , 4 2 3 의 차이가 있을떄 순열은 두개가 다르게 뽑았다고 생각하는 것이다. 엄청 달라보이지만 사실 코드상으로는 크게 차이있지 않다. 약간 중복조합과 조합두개를 짬뽕시킨다는 느낌!

중복이 걸러져야 한다. –> select 을 사용해야한다. (즉, visited가 있어야 한다.)
선택한 값들의 순서가 있어야한다. -> vector로 넣어주면 된다. 그리고 dfs로 누적시켜서 돌려버리지뭐
다음값을 선택하는 것이 idx가 아니라 0부터 시작해야한다. 왜일까? -> 조합이 왜 idx 부터 시작했는지를 생각해보자! 조합의 경우에는 이전 값에 대해서 다시 되돌아갈 필요가 없었다. 즉, 4 3 2 1 5 중에서 4 3 2 를 뽑았으면, 4 3 1, 4 3 5 를 뽑으면 된다. 하지만 순열의 경우, 4 3 2 를 뽑았으면 나중에 4 2 3 을 뽑을 수도 있지 않을까? 즉, 4 2를 뽑고도 그다음값을 3을 뽑아야 한다. 즉, 처음으로 돌아가서 방문처리 안한것들이 있는지 파악해야하기 떄문에 0부터 시작하는 것이다. 반면, 조합의 경우에는 그런 것 없이 4 3 2 뽑았으면, 4 2 3 은 뽑을 필요가 없다. 4 3 2 나 4 2 3 은 똑같기 떄문에 즉 다음의 이유들로 순열은 idx가 0 부터 시작하게된다. (꼭 기억해두길..) 왜냐하면! 순서가 중요하기 떄문에!!

코드 상으론 다음과 같다.

#include <iostream>

using namespace std;

int n =5; k = 3;
int map[5] = {4,3,2,1,5};

void dfs(int cnt,vector<int> v, int selected []){
  if(cnt == k){
    print(v);
    return;
  }
  else{
    for(int i = 0; i<n; i++){ //순열은 뽑는 순서가 중요하기에, idx 로 시작하지 않아야함.
      if(selected[i] == 1) continue; // 이미 골랐으면 고르지 말기
      selected[i] = 1; //고른 것에 대한 방문처리, 즉 순열이나 조합은 항상이렇게 해야함
      v.push_back(map[i]); // 고른 것을 순서를 지켜줘야하니 챙겨줘야함
      dfs(cnt+1, v, selected)
      v.pop_back(); // 골랐으면 다시 되돌아갈때 뺴줘야지!
      selected[i] = 0; //방문했던 것을 다시 
    }
  }
}

int main(){

  int cnt = 0;
  vector<int> v;
  int selected[5] = {0,};

  dfs(0,v,selected);
  return ;
}

4. 중복순열

마지막 중복순열이다. 이쯤되면 순열과 중복 순열의 차이는 조합과 중복조합의 차이로 추론할 수 있을 것이다. 즉, select만 없으면 골랐던 것들을 다시 고를 수 있다. 즉, 444 442 443 이 된다. 하지만 순열이기에 424와 434는 442와 443과 다르다. 즉, 탐색 위치를 시작할때는 무조건 처음부터 진행한다.

코드상으로는 다음과 같다.

#include <iostream>
using namespace std;

int n=5; k=3;
int map[5] = {4,3,2,1,5};

void dfs(int cnt, vector<int> v){
  if(cnt==k){
    print(v);
    return;
  }
  else{
    for(int i=0; i<n; i++){
      v.push_back(map[i]);
      dfs(cnt+1, v);
      v.pop_back();
    }
  }
}

int main(){
  vector<int> v;
  int cnt=0;
  dfs(0,v);
  return;
}

3줄요약

DFS로 조합, 순열, 중복조합, 중복순열을 조건따라서 구현할 수 있다. (결국 DFS는 완전탐색이기 떄문에)
조합류는 다시 되돌아 올 필요가 없기 떄문에 (즉, 순서가 상관없기 떄문에) 다음 값을 고를때 idx 를 계속 넘겨줘야한다. 반면 순열류는 순서가 중요하기 때문에 처음부터 되돌아가서 값을 찾아야한다. 그럼으로 다음 값 탐색을 0부터 진행하면된다.
중복화의 차이는 현재 값을 한번더 뽑을 수 있는가의 차이기에 select를 넣는냐 마느냐의 차이이다. (selected를 넣으면 방문처리를 진행한 것이기에 뽑았던 값들은 다시 안뽑힘)