완전 탐색(2) - 수열

코테에 나오는 완전 탐색 종류

1. (1) N개 중 중복을 허용하여 (A)M개를 순서있게 나열하기
2. (1) N개 중 중복을 허용하여 (B)M개를 고르기
3. (2) N개 중 중복 없이 (A)M개를 순서있게 나열하기
4. (2) N개 중 중복 없이 (B)M개를 고르기

1. N개중 중복을 허용하여 M개를 순서 있게 나열하기

BOJ 15651 - N과 M (3)

def dfs(cnt):
	if cnt == m:
    # 수열 완성
    for i in arr:
    	sys.stdout.write(str(i) + ' ')
     sys.stdout.write('\n')
    else:
    	for i in range(1, n+1):
        	arr[cnt]=i
            dfs(cnt+1)
            arr[cnt]=0
 dfs(0)

2. N개중 중복을 허용하여 M개를 고르기

BOJ 15652 - N과 M(4)

def dfs(cnt):
	if cnt == m:
    	for i in arr:
        	sys.stdout.write(str(i) + ' ')
        sys.stdout.write('\n')
    else:
    	start = 1 if cnt==0 else arr[cnt-1]
    	for i in range(start , n+1):
        	arr[cnt]=i
            dfs(cnt+1)
            arr[cnt]=0

3. N개중 중복없이 M개를 순서있게 나열하기

BOJ 15649 - N과 M(1)

def dfs(cnt):
	if cnt == m:
    	#수열 완성
        for i in arr:
        	sys.stdout.write(str(i)+' ')
        sys.stdout.write('\n')
    else:
    	for i in range(1, n+1):
        	if i in arr:
            	continue
        	arr[cnt]=i
            dfs(cnt+1)
            arr[cnt]=0

4. N개중 중복없이 M개를 고르기

BOJ 15650 - N과 M (2)

def dfs(cnt):
	if cnt==m:
    	for i in arr:
        	sys.stdout.write(str(i) + ' )
        sys.stdout.write('\n')
    else:
    	start=0 if cnt==0 else start=arr[cnt-1]+1
    	for i in range(start, n+1):
            arr[cnt]=i
            dfs[cnt+1]
            arr[cnt]=0

완전 탐색 문제를 접근할 때는

• 고를 수 있는 값의 종류 파악하기
• 중복을 허용하는지
• 순서가 중요한지