DFS 적용 - 조합

조현수·2023년 2월 5일
0

조합 구하기 문제를 통해 DFS 전반적으로 이해할 수 있을 것이다.

⚽ 조합 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요. N개 중 M개 뽑기

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

▣ 입력예제 1
4 2

▣ 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
6

import sys
# sys.stdin = open("input.text", "rt")

n, m = map(int, input().split())
res = [0] * m
cnt = 0
def DFS(L, start): #현재 레벨과 어디서부터 시작해야하는지 들어와
    global cnt
    if L == m: #M개 다 뽑은 경우 종료조건
        for x in res:
            print(x, end = " ")
        print()
        cnt += 1
    else:
        for i in range(start, n+1):
            res[L] = i #이번 단계에서 i사용
            DFS(L+1, i+1)
            
DFS(0,1)      
print(cnt)            
            

코멘트

조합 구하기를 베이스로 해서 많은 문제들이 응용되어서 출제된다!! 이 문제를 잘 기억하고 활용만 잘하면 모든 것이 해결된다 !!

  • BFS + 조합으로 연구소 문제를 들 수 있다.

지금까지 중복 순열, 순열을 통해 DFS를 연습했다. 그것과 코드는 거의 동일한데, 상태트리가 약간 달라 ! - 머릿 속으로 시각화 잘 해놔야한다 !

만약 이 문제처럼 4개중 2개를 뽑는다 했을 때

현재 레벨(L)에서 선택했을 때 다음 레벨에서는 선택하면 안되잖아. (물론 오름차순 기준) 그렇기에 해당 숫자 +1을 다음단계로 넘겨서 반복문을 그때부터 돌리면 돼(그 변수가 start)

  • 다른 문제와 엮어서 생각할 때는 중복체크를 한 후에 다시 안뽑게 할 수도 있다!!

  • 이 과정을 제외하고는 중복 순열, 순열과 모두 동일해 !!

⚽ 조합 활용한 문제풀 때 생각

수들의 조합

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.

▣ 입력설명
첫줄에 정수의 개수 N(3<=N<=20)과 임의의 정수 K(2<=K<=N)가 주어지고,
두 번째 줄에는 N개의 정수가 주어진다.
세 번째 줄에 M이 주어집니다.

▣ 출력설명
총 가지수를 출력합니다.

▣ 입력예제 1
5 3
2 4 5 8 12
6

▣ 출력예제 1
2

import sys
# sys.stdin = open("inAA.pyput.text", "rt")

n, k = map(int, input().split())
data = list(map(int, input().split()))
m = int(input())
res = [0] * k

cnt = 0
def DFS(L, start):
    global cnt
    if L == k: #다 뽑았으면 종료조건
        if sum(res) % m == 0:
            cnt += 1
    else:
        for i in range(start, n): #자료의 개수
            res[L] = data[i] #삽입하는거라 백트랙킹시 원상복구 코드 필요없음, append pop쓸때는 해줘야지
            DFS(L+1, i+1)

DFS(0,0)
print(cnt)

코멘트

똑같이 data에 저장된 숫자 n개 중에서 k개를 뽑을 것이다. k개를 뽑았을 때
그 값이 m의 배수인지 확인하면 될 것이다.

이 문제의 경우도 n개 중 k개를 뽑아서 부분집합을 만든다고 생각.
상태트리는 DFS(L, start, sum) 이렇게 할 것인데, L은 레벨(인덱스) start는 for문이 시작되는 시작지점, sum은 지금까지의 합 !
(물론 위처럼 res에 넣어둔 후에 한번에 sum해도 되는데 결국 그렇게 하면 O(n)시간 만큼 필요하기에 파라미터로 sum을 더해나가는 것으로 하는게 좋을 수도 있겠다.

profile
back-end, 지속 성장 가능한 개발자를 향하여

0개의 댓글