너와!나의!알고!리즘!/백준

[백준 N과M 시리즈, Python] N과M 시리즈

moongchi98 2021. 3. 9. 00:40

우선, 시리즈를 앞서서 열심히 풀어봤지만 뒤로 갈수록 거의 앞선 코드 복붙의 향연이라 순열조합 마스터의 목표와는 다르게 복붙의 왕이 되었다,, 순열 조합 순서가 중요하고 말고는 알지만 몇번 문제가 정확히 어느건지는 모르니껭,,틀려도 이해해달라능 *'ㅂ'*~ 공대지만 수포자니께~~~ 

그리고 기본format을 고냥 복붙해서,,함수이름이 순열이든 조합이든 다 combi다 머쓱타드 ^^;;;

간단하게 정리하면 일단 idx로 뽑아주는 개수를 넘기고 sel이라는 매개변수(list)로 뽑은 애들을 넘겨준다.

🤷‍♀️ 중복을 허용한다면 방문체크는 필요 없다! 그리고, 조합을 만들려면 순서가 상관없슴 =>

결국 앞선 idx는 뒤에 반복문에서 돌지 않아야함 (1,2)나 (2,1)은 같은거니까..그래서 마지막 방문 reset과정을 for문을 하나 추가하여 범위를 그 인덱스(i)보다 하나 큰 녀석부터(i+1) 0으로 만들어준다!!!

[N과M-(1)]

🐤 순열

 

자기랑 같은 애는 나오면 안되고, 순서를 고려해야한다.

from sys import stdin
def combi(idx,sel):
    if idx == M:
        print(*sel)
    else:
        #for문이 있어야 모든 numbers가 나온다
        for i in range(N):
            if visit[i] == 0:
                visit[i] = 1
                combi(idx+1,sel+[numbers[i]])
                visit[i] = 0

#순열
N,M = map(int,stdin.readline().split())
numbers = [i for i in range(1,N+1)]
visit =[0]*(N)
combi(0,[])

[N과M-(2)]

🐤 조합

역시 마찬가지루 자기랑 같은건 안되고, 순서가 상관없다! 

#조합
def combi(idx,sel):
    if idx == M:
        print(*sel)

    for i in range(N):
            if visit[i] == 0:
                visit[i] = 1
                combi(idx+1,sel+[num[i]])
                #뽑았던 것은 다음 라운드에 안나오게 해주도록 i빼고 reset
                for j in range(i+1,N):
                    visit[j] = 0

from sys import stdin
N,M = map(int,stdin.readline().split())
num = [i for i in range(1,N+1)]
visit =[0]*(N)
combi(0,[])

[N과M-(3)]

🐤 중복순열

1번 처럼 순열이지만, 같은걸 뽑아도 가능! 순서고려해야한다

from sys import stdin
N,M = map(int,stdin.readline().split())
def comb(idx,sel):
    if idx==M:
        print(*sel)
        return
    for i in range(N):
        comb(idx+1,sel+[num[i]])

num = [i for i in range(1, N + 1)]
comb(0, [])

[N과M-(4)]

🐤 중복조합

비내림차순의 등장! 애초에 sel에 추가할때부터 마지막 인덱스와 비교하여서 같거나 큰 값들만 추가될 수 있도록 설정해준다. 만약 빈 list라면 그냥 추가해도 되니까 그 조건도 같이!

from sys import stdin
N,M = map(int,stdin.readline().split())
def comb(idx,sel):
    if idx==M:
        print(*sel)
        return
    for i in range(N):
        if len(sel) == 0 or sel[-1] <= num[i]:
            comb(idx+1,sel+[num[i]])

num = [i for i in range(1, N + 1)]
comb(0, [])

[N과M-(5)]

🐤 순열

다만 이제는 숫자 list를 만들지 않고, 주는 녀석을 사용. 

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        print(*sel)
        return
    for i in range(N):
        if visit[i] == 0:
            visit[i] = 1
            comb(idx+1,sel+[num[i]])
            visit[i] = 0
visit = [0]*N
comb(0, [])

[N과M-(6)]

🐤 조합

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        print(*sel)
        return
    for i in range(N):
        if visit[i] == 0:
            visit[i] = 1
            comb(idx+1,sel+[num[i]])
            #앞에서 나왔던 숫자가 나오면 안될때는 i빼고 reset
            for j in range(i+1,N):
                visit[j] = 0
visit = [0]*N
comb(0, [])

[N과M-(7)]

🐤 중복순열

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        print(*sel)
        return
    for i in range(N):
            comb(idx+1,sel+[num[i]])
comb(0, [])

[N과M-(8)]

🐤 중복조합

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        print(*sel)
        return
    for i in range(N):
        if visit[i] == 0:
            if len(sel) == 0 or sel[-1]<=num[i]:
                comb(idx+1,sel+[num[i]])
            for j in range(i+1,N):
                visit[j] = 0
visit = [0]*N
comb(0, [])

[N과M-(9)]

🤢순열인디 주어지는 숫자 list에 중복되는 숫자가 있어서 자동으로 중복되는 순열이 만들어지구 그걸 없애줘야하는 것

이 문제가 제일 힘들었다, 그냥 단순히 sel을 result라는 큰 list에 추가한다음에 set으로 해서 sort하면 끝아녀~ 했는데 set안에는 list같은 mutable data가 들어가면 안되나보다..

그래서 처음에는 아예 sel을 문자열로 만들었다,, 예쩨는 통과햇는데 왜 미통과지 하고 질문칸의 반례들을 검색한 결과

1000과 같은 두자리 이상의 숫자들은 문자열에서 1 0 0 0 처럼 하나씩 인식되서 틀리는것,,

결국 sel을 tuple형태로 만들어서 처리하였다!

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        result.append(tuple(sel))
        return
    for i in range(N):
        if visit[i] == 0:
            visit[i] = 1
            comb(idx+1,sel+[num[i]])
            visit[i] = 0
visit = [0]*N
result = []
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
    print(*r)


#not in으로 중복 점검 => 시간 초과
#str로 치환 경우에는 두자리 이상의 숫자가 하나하나로 처리
# ex)10000 => 1 0 0 0 0

[N과M-(10)]

🤢요상한 조합

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        result.append(tuple(sel))
        return
    for i in range(N):
        if visit[i] == 0:
            visit[i] = 1
            if len(sel) == 0 or sel[-1] <= num[i]:
                comb(idx+1,sel+[num[i]])
            visit[i] = 0
visit = [0]*N
result = []
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
    print(*r)

[N과M-(11)]

🤢요상한 중복 순열

from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        result.append(tuple(sel))
        return
    for i in range(N):
        comb(idx+1,sel+[num[i]])

result = []
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
    print(*r)

[N과M-(11)]

🤢요상한 중복 조합

여기서 예상치 못하게 통과를 못했는데 아래와 같은 예시에서 걸렸던 것 같다. 그런데 반복 확인하는 visit없애고 다시 작성하니까 제대로 동작,,

#예시
3 2
1 11 111

#처음내코드 출력
1 1
1 11
1 111
11 111
111 111

#나와야하는 출력
1 1
1 11
1 111
11 11
11 111
111 111
from sys import stdin
N,M = map(int,stdin.readline().split())
num = list(map(int,stdin.readline().split()))
num.sort()
def comb(idx,sel):
    if idx==M:
        result.append(tuple(sel))
        return
    for i in range(N):
        if len(sel) == 0 or sel[-1] <=num[i]:
            comb(idx+1,sel+[num[i]])

result = []
visit= [0]*N
comb(0,[])
result = list(set(result))
result.sort()
for r in result:
    print(*r)