[백준 15651] N과 M (3)

[BanApp]

pypy3

############DFS활용#############
import sys
n,m = map(int,sys.stdin.readline().split())

arr = []

def find(d,n,m):
    if d == m:
        return print(*arr)

    for i in range(n):
        arr.append(i+1)
        find(d+1,n,m)
        arr.pop()

find(0,n,m)

########중복순열 활용#############
import itertools
import sys
from itertools import product
n,m = map(int,sys.stdin.readline().split())

arr = []

for i in range(1,n+1):
    arr.append(i)

for i in product(arr, repeat=m):
    print(*i)

전체탐색 문제는 DFS 최단거리 찾는 문제는 BFS를 쓰는게 정설이다.
굉장히 간단한 코드지만 사실 재귀를 통해서 반복문을 m+1번 돌려주는 코드다.
왜 m+1번이냐면 만약 m이 2라고 가정하면 1 1 이런식으로 두개의 조합을 출력해줘야 한다.
우선 함수를 실행한다(1번째)
먼저 첫번째 자리에 올 반복문이 실행되고 다시 함수(2번째)를 호출하는 재귀가 된다.
이에 다시 append를 해주면 1 1이 되는데 다시 함수를 호출하면(3번째) if문의 조건에 따라서 값을 return하고 함수를 탈출한다.
pop 함수를 실행하고 다시 for문을 돈다. 그러면 만약 2번째 함수의 반복문을 모두 돌면 2번째 함수를 탈출해서 다시 1번째 함수로 돌아가서 pop을 실행하면 arr은 빈리스트가 되고 드디어 1번째 함수의 반복문의 한번 실행이 끝났다. 이를 1번째 함수의 반복문이 끝날때 까지 진행하면 된다.
추가적으로 혹시나 싶어서 파이썬에서 기본적으로 제공하는 중복순열을 찾는 함수가 있다.
product라는 함수인데 시간복잡도가 O(N!)으로 알고있고 DFS는 O(N^2)라고 알고 있다.
근데 백준에서는 product함수를 사용한게 더 동작속도가 빠르게 나온다...

1. 내가 첫번째 코드를 잘못짰다.
2. 테스트케이스 숫자가 적어서 우연의 일치이다.
3. DFS의 시간복잡도가 O(N^2)이 아니고 product 함수의 시간복잡도도 O(N!)이 아니다.

셋중 무엇이 정답일까요..? 재귀 싫어~~

[ghdcksgml1]

둘다 시작복잡도는 O(N^N)인데 product 함수가 더 빠른 이유는 for문으로 구현했기때문에 DFS처럼 스택에 들어갔다 나왔다하는 과정이 생략되어서 더 빠릅니다!

간혹 어려운 코딩테스트에서 스택 메모리 제한이 있는경우에는 DFS같은 함수를 while이나 for문으로 구현해야 통과하는 케이스도 있어용

[BanApp]

근데 이거 라벨 어떻게 다나요?

[ghdcksgml1]

오른쪽에 Labels 탭에 설정모양 누르면 달수있어욘

[BanApp]

내가 invitation을 안받았었네,,ㅋㅋㅋㅋㅋㅋㅋㅋ

[ghdcksgml1]

백준 아이디 주시면 리드미에 추가해드릴게영

[BanApp]

blackberry97 입니돠