다중 for loop 조합이 dfs 보다 안 좋은 점이 무엇인가요?

Question

예를 들어 0~5 중에 3개를 조합한다고 하면 아래처럼 3중 포문을 돌리는 게 dfs 를 쓰는 것과 유의미한 차이가 있나요? 과정만 보면 설명하신 거랑 크게 다를 게 없을 것 같은데..

for (i = 0; i <=5; i++)
{
  for (j = i+1; j <= 5; j++)
  {
    for (k = j+1; k <= 5; k++)
    {
      // 조합완성
    }
  }
}

Answer

탐색하는 과정은 둘다 동일한 과정입니다. 다만 문제에 따라 DFS를 선택해야만 할 때가 있습니다.

다중 for문은 nC3(n개중 3개를 뽑는경우수) 처럼 뽑는 수가 정해진 문제에만 사용할 수 있습니다.

nCr(n개중 r개를 뽑는 경우수)처럼 n과 r이 모두 변수로 입력될 때 다중 for문으로는 대처하기가 힘듭니다.

즉

6 4(6개 중 4개를 뽑는 각각의 경우들을 출력하라)

9 5(9개 중 5개를 뽑는 각각의 경우들을 출력하라)

20 12(20개 중 12개를 뽑는 각각의 경우들을 출력하라)

처럼 r값이 다양하게 들어오는 문제의 경우 다중 for문으로는 대처가 힘듭니다. 이런 경우 DFS로 코드를 구현하는 것입니다.

Answer

아하 감사합니다!