2학기 6주차_알고리즘( 백준15649번 : N과 M)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

📌 내풀이

 

 

 

 

일단 문제를 이해하려고 최대한 적어보면서 노력해봤다.

프로그램의 방향성이나 입출력 되는 방향은 이해를 했다. 

근데 이해한 (중복되지않게 최대한 배열을 하기) 것을 어떻게 코드로 구현을 해야할 지 고민이 들었다.

 

일단 배열을 사용해서 숫자를 저장해야할 것 같고, if문을 활용해서 경우의 수를 나눠봐야할 거같다라는 생각을 하고 문제풀이를 시작했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {

	int N, M;
	int array[100] = { 0 };

	scanf("%d", &N);
	scanf("%d", &M);
	for (int i = 1; i<=N ; i++) {
		for (int j = i + 1; j <= M; j++) {
			
		}
		
		printf("%d\n", array[100]);

	return 0;
}

 

 

헤당 코드를 기반으로 코드를 짜보려고 했다. 그런데 모든수열을 중복되지않게 구현하기는 쉽지않을 것 같다는 생각이 들어서 도움을 받아봤다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int result[10];
int V[10];

void dfs(int N, int M, int D) {
    if (D == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }

    for (int num = 1; num <= N; num++) {
        if (!V[num]) {
            V[num] = 1;
            result[D] = num;
            dfs(N, M, D + 1);
            V[num] = 0;
        }
    }
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    dfs(N, M, 0);
    return 0;
}

 

1. result와 V로 배열을 선언한다.
2. dfs로 함수를 만들고 메일에서 구현될 수 있도록 코드를 구현했다.
3. if 만약 D,M이 같다면 M보다 작을때까지 result에 i값을 저장하도록 구현한다.
4. for (int num = 1; num <= N; num++): 1부터 N까지의 자연수를 하나씩 확인한다.
5. if (!V[num]): 현재 숫자(num)가 방문되지 않았다면 (V[num]이 0이라면), 다음과정을 진행한다.
6. V[num] = 1;: 현재 숫자를 검사했다는 표시
7. result[D] = num;: 현재 숫자를 결과 배열 result 인덱스에 저장한다.
8. dfs(N, M, D + 1);: 다음 숫자를 선택하기 위해 D 값을 1 증가시킨다.
9. V[num] = 0;: 현재 숫자를 다른 경로에서도 사용할 수 있도록 검사표시를 해제한다.

 

 

 

두번째 문제가 첫번째 문제보다 까다롭고 시간도 많이 걸렸지만, 백트래킹이라는 방법을 사용해볼 수 있는 좋은 경험이었다.

 

▶백트래킹(Backtracking) 이란?

 

백트래킹(Backtracking)은해결책을 구하기 위해 모든 가능성을 시도해보는 것이 아니라, 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지 여부를 검사해가며 해답을 찾아가는 알고리즘입니다.

 

 

[ 참고 학습 자료 ]

 

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 | ChanBLOG (chanhuiseok.github.io)

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

백트래킹(BackTracking) (oopy.io)

백트래킹(BackTracking)