순열 조합 뿌시기

순열과 조합

순열

• 순서가 있는 조합
• 순서가 다르면 다르게 취급

조합

• 순서를 고려하지 않고 선택
• 원소는 같고 순서만 다른 중복허용하지 않음

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=2080

주사위를 던진 횟수 N과 출력형식 M을 입력 받아서 M의 값에 따라 각각 아래와 같이 출력하는 프로그램을 작성하시오.

중복순열

• 순서가 있는데(즉 순서가 다르면 다르게 취급) 중복원소 허용
• 주사위를 N번 던져서 나올 수 있는 모든 경우(중복순열)

def dice1(cnt, start):
    if cnt == N:
        print(*path)
        return
    for i in range(1, 7):
        path[cnt] = str(i)
        dice(cnt + 1, type, start)
path = [""] * 100
dice1(0, 1)

순열

• 순서가 있는데 중복 원소 허용 X
• 주사위를 N번 던져서 중복이 되는 경우를 제외하고 나올 수 있는 모든 경우(순열)
• 방문 체크 해줘야 됨

def comb(cnt, start):
    if cnt == N:
        print(*path)
        return
    for i in range(start, 7):
        path[cnt] = str(i)
        comb(cnt + 1, i)
path = [""] * 100
visit = [0] * 8
N = 3
comb(0, 1)

조합

• 순서 없고(순서 다른 데 원소만 같은 애들x) 중복원소 허용X
• 주사위를 N번 던져서 모두 다른 수가 나올 수 있는 모든 경우(조합)
• 빠져 나왔을 때 방문 다시 0으로 만들어 줘야 됨

def dice3(cnt, start):
    if cnt == N:
        print(*path)
        return
    for i in range(1, 7):
        if visit[i]: continue
        visit[i] = 1
        path[cnt] = str(i)
        dice(cnt + 1, type, start)
        visit[i] = 0
path = [""] * 100
visit = [0] * 8
dice3(0, 1)

💡

백트래킹, 완전탐색에서 많이 쓰이니 잘 알아두자!!!
기본기의 중요성!!