알고리즘/알고리즘_ps
15649_N 과 M (1)
해피코딩
2021. 10. 8. 13:29
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
브루트포스
모든 경우의 수를 순서대로 탐색하는 알고리즘.
문제에서 브루트포스로 접근이 가능한지의 유무는 시간복잡도를 계산하여 대략적으로 알 수 있다.
접근1
브루트포스를 이용한 방식으로 접근하여 이 문제를 해결하면 생각보다 간단하게(?) 구현 가능하다.
N개의 자연수 중에서 중복없이 M개를 고르는 방법.
ex)
N = 3 , M = 1 -> (1) ,(2) ,(3)
N = 3 , M = 2 -> (1,2),(1,3), (2,1), (2,3), (3,1), (3,2)
중복없이 수열을 만들기 위하여 c라는 배열을 만들어 중복을 제거하고 제귀적인 구조로 모든 배열을 출력하자.
