[Python][Recursive]순열 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
from collections import Counter as ctr

n, m = map(int, input().split())
series = list(map(int, input().split()))
series = list(ctr(series).items())
series.sort()
n = len(series)
nums, cnt = map(list, zip(*series))
answer = [0]*m
result = []

# 중복불허, 중복된 N 수열[9,7,9,1] 에서 M 출력, 비내림차순
def recur6(n, m, idx):
    if idx == m:
        print(' '.join(map(str, answer)))
        return

    for i in range(n):
        if idx > 0:
            if answer[idx-1] <= nums[i]:
                answer[idx] = nums[i]
                recur6(n, m, idx+1)
        else:
            answer[idx] = nums[i]
            recur6(n, m, idx+1)

recur6(n, m, 0)


# # 중복불허, 중복된 N 수열[9,7,9,1] 에서 M 출력, 순서고려
# def recur5(n, m, idx):
#     if idx == m:
#         print(' '.join(map(str, answer)))
#         return
#
#     for i in range(n):
#         if cnt[i] > 0:
#             cnt[i] -= 1
#             answer[idx] = nums[i]
#             recur5(n, m, idx+1)
#             cnt[i] += 1
#
# recur5(n, m, 0)


# # 중복허용한 N개 수중 M개 고른 비내림차순 수열
# def recur4(n, m, idx):
#     if idx == m:
#         print(' '.join(map(str, answer)))
#         return
#
#     for i in range(n):
#         if idx > 0:
#             if answer[idx-1] <= series[i]:
#                 answer[idx] = series[i]
#                 recur4(n, m, idx + 1)
#         else:
#             answer[idx] = series[i]
#             recur4(n, m, idx+1)
#
# recur4(n, m, 0)

# # 중복허용한 N개 수중 M개 고른 수열
# def recur3(n, m, idx):
#     if idx == m:
#         print(' '.join(map(str, answer)))
#         return
#
#     for i in range(n):
#         answer[idx] = series[i]
#         recur3(n, m, idx+1)
#
# recur3(n, m, 0)

# # 중복불허한 N개 수중 M개 고른 오름차순 수열, 순서 고려 함
# def recur2(n, m, idx, start):
#     if idx == m:
#         print(' '.join(map(str, answer)))
#         return
#
#     for i in range(start, n):
#         if check[i]:
#             continue
#         check[i] = True
#         answer[idx] = series[i]
#         recur2(n, m, idx+1, i+1)
#         check[i] = False
#
# recur2(n, m, 0, 0)

# # 중복불허한 N개 수중 M개 고른 수열, 순서 고려 안함
# def recur1(n, m, idx):
#     if idx == m:
#         print(' '.join(map(str, answer)))
#         return
#
#     for i in range(n):
#         if check[i]:
#             continue
#         check[i] = True
#         answer[idx] = series[i]
#         recur1(n, m, idx+1)
#         check[i] = False
#
# recur1(n, m, 0)

댓글

댓글 쓰기

이 블로그의 인기 게시물

[python]섬의 둘레구하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 direction = (( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )) def sol (st_y, st_x): global w, h cnt = 0 for d in direction: next_y = st_y + d[ 0 ] next_x = st_x + d[ 1 ] if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w or MAP[next_y][next_x] == 0 : cnt += 1 return cnt while True: w, h = map(int, input() . split()) if (w, h) == ( 0 , 0 ): break MAP = [list(map(int, input() . split())) for _ in range(h)] answer = 0 for i in range(h): for j in range(w): if MAP[i][j] == 0 : continue answer += sol(i,j) print (answer) 아이디어는 단순하다. 모든 좌표를 순회하면서 주변이 땅으로 연결되지 않을때 cnt를 하나씩 증가시킨다.
자세한 내용 보기

백트래킹으로 부분집합구하기(Get Powerset usiing Backtracking)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def backtrack (a, k, input): global MAXCANDIDATES c = [ 0 ] * MAXCANDIDATES if k == input: process_solution(a,k) #답이면 원하는 작업한다. else : k += 1 ncandidates = construct_candidates(a,k,input,c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k, input) def process_solution (a, k): print ( "(" , end = "" ) for i in range(k + 1 ): if a[i]: print (i, end = " " ) print ( ")" ) #후보군 구하는 함수 def construct_candidates (a, k, input, c): c[ 0 ] = True c[ 1 ] = False return 2 #Main MAXCANDIDATES = 100 NMAX = 100 a = [ 0 ] * NMAX backtrack(a, 0 , 3 )
자세한 내용 보기

[Python]DFS를 이용한 부분집합 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 def recur (idx): check[idx] = 1 tmp . append(n[idx]) if len(tmp) == 3 : a = sorted(tmp) if sum(a) not in result: result . append(sum(a)) else : for i in range( 7 ): if check[i] == 0 : recur(i) tmp . pop() check[i] = 0 # def subset(): # for i in range(1<<7): # tmp2 = 0 # cnt = 0 # for j in range(7): # if i & (1<<j): # tmp2 += n[j] # cnt += 1 # if tmp2 not in result and cnt == 3: # result.append(tmp2) for t in range(int(input())): n = list(map(int, input() . split())) result = [] for i in range(len(n)): tmp = [] check = [ 0 ] * 7 recur(i) # subset() res...
자세한 내용 보기