인프런 커뮤니티 질문&답변
작성한 질문수
다중 for loop 조합이 dfs 보다 안 좋은 점이 무엇인가요?
해결된 질문
작성
·
449
1
예를 들어 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++)
{
// 조합완성
}
}
}답변 2
2
김태원
지식공유자
탐색하는 과정은 둘다 동일한 과정입니다. 다만 문제에 따라 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로 코드를 구현하는 것입니다.
0
