알고리즘 :: 백준 :: Bruteforce :: 15650 :: N과 M (2)

Embedded June·2021년 2월 10일
0

알고리즘::백준

목록 보기
62/109
post-thumbnail

문제


문제링크

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

문제접근

'순서'적 관점

  • 오름차순을 만들기 위해서는 재귀함수 parameter에 현재까지 고른 수 중 가장 큰 수를 계속 가지고다녀야 한다.
  • 기존에 1부터 시작하던 for문을 해당 값보다 큰 값부터 시작하도록 수정한다.
  • 기존에는 중복을 막기 위해 c[]라는 배열에서 숫자를 체크했지만, 오름차순이므로 이번에는 체크할 필요가 없다.
  • 이번 재귀에서 수를 고른 뒤 다음 재귀로 넘어가면, 반드시 아까 고른 수보다는 큰 수를 고르게끔 되어있기 때문이다. 그러므로 중복이 발생하지 않는다.
  • 결과 배열에 숫자 M개가 만들어질 때 출력하도록 한다. 시간복잡도는 O(N!)O(N!)이다.

'선택'적 관점

  • 이번에는 '선택'하는 관점에서 문제를 풀어보자.

  • 지금까지는 결과 배열에서 0번째 인덱스 부터 M-1번째 인덱스까지 들어올 수 있는 수를 하나씩 조건에 맞도록 '순서대로' 맞춰나갔다면, 이번에는 1 부터 N까지 수에 대해 각각의 수를 '선택하냐', '선택하지않느냐'로 관점을 바꿔보자.

  • 12345678
    O/XO/XO/XO/XO/XO/XO/XO/X
  • 숫자 1부터 '선택 / 선택안함'을 선택하면서 M번 선택할 때 출력하도록 한다. 시간복잡도는 O(2N)O(2^N)이다.

코드

'순서'적 관점

#include <cstdio>
int n, m, a[9];
void solve(int idx, int num) {
    // m개를 만들었으니 출력한다.
	if (idx == m) {
		for (int i = 0; i < m; ++i) printf("%d ", a[i]);
		printf("\n");
		return;
	}
	// 'num'부터 시작해서 숫자를 만든다.
	for (int i = num; i <= n; ++i) {
		a[idx] = i;
		solve(idx + 1, i + 1);
	}
}
int main() {
	scanf("%d %d", &n, &m);
	solve(0, 1);
}

'선택'적 관점

#include <cstdio>
int n, m, a[10];
// num 이라는 수를 포함시킬지 안시킬지 '선택'한다.
void solve(int num, int cnt) {
   	// m개를 '선택'했으니 출력한다.
	if (cnt == m) {
		for (int i = 0; i < m; ++i) printf("%d ", a[i]);
		printf("\n");
		return;
	}
	if (num > n) return;	// 더 이상 선택할 수 있는 수가 없으니 예외처리
	a[cnt] = num;		// [고정] cnt번째 수로 num을 할당시키고
	solve(num + 1, cnt + 1);// [실행] cnt + 1번째 수를 찾으로 num + 1부터 탐색
	a[cnt] = 0;		// [해제] cnt번째 수를 초기화시켜주고 
	solve(num + 1, cnt);	// [실행] num을 선택하지 않았을 경우에 대해 탐색
}
int main() {
	scanf("%d %d", &n, &m);
	solve(1, 0);
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글