인프런 커뮤니티 질문&답변

qhdmswns님의 프로필 이미지
qhdmswns

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-A

1-A 문제 질문있습니다!

작성

·

516

0

안녕하세여 강사님! 강의 듣던 도중에 의문점이 생겨서 질문 드립니다!
 
50초 부근에서 9명중에 7명을 뽑는것은 9C7인것은 이해가 가는데,
n의 범위가 작다고 해서 combination이 permutation으로 풀수 있는게 가능한건가요?
 
combination과 permutation의 정의가 애초에 다른것 아닌가요?
 
아니면 permutation을 써서 나오는 결과들이 combination의 경우를 모두 포함하고 있기 때문에 이번문제에서 그냥 permutation으로 하는건가요?
 
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;
int cnt;
int main() {
	const int r = 7;
	vector<int> arr(9);
	for(int i = 0; i<9; i++){
             cin>> arr[i];
        }
        sort(arr.begin() , arr.end());
	vector<bool>temp(arr.size(), 1);
	for (int i = 0; i < arr.size() - r; i++) { 
		temp[i] = 0; // 앞에 false가 n-r개 채워지고 뒤에 true 가 r개 채워지게 하면
	}
	do {
		cnt = 0;
		for (int i = 0; i < arr.size(); i++) {			
			if (temp[i]) {
				cnt += arr[i];
			}
		}
		if (cnt == 100) {
			for (int i = 0; i < arr.size(); i++) {
				if (temp[i]) {
					cout << arr[i] << "\n";
				}
			}
			break; 
		}
	} while (next_permutation(temp.begin(), temp.end()));
	return 0;
}

 

 

 

그냥 순열이 아닌 조합으로 어떻게든 next_permutation을 써서 해보려고 했는데 위의 코드처럼 하면 처음에 말씀하신 9C7이 되지 않을까요..? 잘 모르겠습니다..

 

답변 3

1

큰돌님의 프로필 이미지
큰돌
지식공유자

유희준님이 너무나 잘 답변해주셨는데요. ㅎㅎ 첨언하자면 다음과 같습니다. 

permutation을 써서 나오는 결과들이 combination의 경우를 모두 포함하고 있기 때문에 이번문제에서 그냥 permutation으로 하는건가요?
 
네 그렇습니다. 예를 들어 {1, 2} 중 "순서와 관계있이" 2개를 뽑는 경우의 수를 생각해보죠. {1, 2}와 {2, 1}이 있겠죠? 자, 그렇다면 여기서 "순서와 관계없이" 뽑는 경우의 수는 어떨까요? {1, 2} 한개겠죠? 즉, 순열은 조합을 포함하는 관계에 있습니다. 그렇기 때문에 이렇게 N이 작은 경우 순열로 풀어도 된다 라는 것이죠.
 
또 질문사항있으시면 언제든 말씀 부탁드립니다. 감사합니다. 강사 큰돌 올림.
qhdmswns님의 프로필 이미지
qhdmswns
질문자

넵 감사합니다! 

1

우선 강사님이 아닌데 답글을 달아서 죄송합니다

질문 하신거에 대해 제 생각을 설명하자면

모든 경우를 출력하는게 아니라 오름차순으로 정렬해서 가장 먼저 되는 한개만 출력하기 때문에

combination과 permutation의 차이가 무의미 해져 permutation으로 했다고 생각합니다.

그리고 위의 코드가 안되는 이유는

next_permutation(temp.begin(), temp.end())

에서 temp 벡터 안에 있는 값들의 순서는 변경되는데

temp벡터와 대칭되는 arr 벡터의 값들의 순서는 변경되지 않아서 값이 다르게 나오는것 같습니다.

 

그리고 강의에서 제공해주는 코드에서 next_permutation() 했을 때 a배열 안의 값이 어떻게 변하는지 한번 확인 하시는게 좋을것 같다고 생각합니다.

qhdmswns님의 프로필 이미지
qhdmswns
질문자

넵 답변 달아주셔서 감사합니다! 근데 제가쓴 코드 제출하면 맞았습니다! 뜨는데 맞는것 같습니다. 

 

제가 애초에 설계할때 bool배열이랑 arr배열을 오름차순으로 했습니다.( 만약 9C2면 bool배열은 {0,0,0,0,0,0,0,1,1} 이런식으로요) 

그래서 9C2의 경우, bool 배열은 밑에과정처럼 while문이 진행되는데, 1과 같은 인덱스에 대응하는 arr의 원소끼리 조합을 한것입니닷

 ( 2309번 출력예시를 보자면)

만약 8C2면 {0,0,0,0,0,0,0,1,1} -> 23, 25에 대응시키고

{0,0,0,0,0,0,1,0,1} -> 20,25에 대응시키고,

{0,0,0,0,0,0,1,1,0} -> 20,23에 대응시키고 

이런방식으로 하면 

bool 배열을 바탕으로 next_permutation을 수행해서 1이 되는 배열의 값과 대응되는 조합을 구하면 제가 짠 코드처럼 됩니다!

0

안녕하세요.  좋은 강의 항상 감사합니다.

풀이에 대해 질문있습니다!

문제에서 오름차순으로 출력하라고 했는데, 최초에 배열을 sort하긴 했지만 do-while을 순회하면서 탐색하는 배열에 요소들은 계속 섞이는데, 출력할 떄 최종적으로 오름차순으로 sort 해줘야 하지 않나요?

애초에  do-while permutation을 하는 이유가 모든 경우수를 순회하기 위함인데 이 경우에 굳이 앞에서 sort 할 필요가 있나요?

 

 

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 코딩꾼님. 제가 교안에 permutation을 하려면 sort를 먼저 해야 된다고 명시를 해두었죠? 해당 부분 다시 읽고 오길 바라며. 

코드를 한번 바꿔볼까요? 아래처럼 찍어보면 어떻게 될까요? 순열이라는 것은 순서를 바꾸긴 해도 가장 끝에서부터 바꾸는 함수 입니다. 

#include <bits/stdc++.h>
using namespace std;  
int a[9];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i = 0; i < 9; i++){
        cin >> a[i];
    }
    sort(a, a + 9);
    do{
        int sum = 0;
        for(int i = 0; i < 7; i++) sum += a[i];
        for(int it : a) cout << it << " ";
        cout << '\n';
        if(sum == 100)break;
    }while(next_permutation(a, a + 9));
    for(int i = 0; i < 7; i++) cout << a[i] << "\n";
    return 0;
}

따라서... 위의 코드를 실행하게 되면
7 8 10 13 15 19 20 23 25
7 8 10 13 15 19 20 25 23
7 8 10 13 15 19 23 20 25
7 8 10 13 15 19 23 25 20
7 8 10 13 15 19 25 20 23
7 8 10 13 15 19 25 23 20
7 8 10 13 15 20 19 23 25
7 8 10 13 15 20 19 25 23
7 8 10 13 15 20 23 19 25
7 8 10 13 15 20 23 25 19
7 8 10 13 15 20 25 19 23
7 8 10 13 15 20 25 23 19
7 8 10 13 15 23 19 20 25
7 8 10 13 15 23 19 25 20
7 8 10 13 15 23 20 19 25
7 8 10 13 15 23 20 25 19
7 8 10 13 15 23 25 19 20
7 8 10 13 15 23 25 20 19
7 8 10 13 15 25 19 20 23
7 8 10 13 15 25 19 23 20
7 8 10 13 15 25 20 19 23
7 8 10 13 15 25 20 23 19
7 8 10 13 15 25 23 19 20
7 8 10 13 15 25 23 20 19
7 8 10 13 19 15 20 23 25
7 8 10 13 19 15 20 25 23
7 8 10 13 19 15 23 20 25
7 8 10 13 19 15 23 25 20
7 8 10 13 19 15 25 20 23
7 8 10 13 19 15 25 23 20
7 8 10 13 19 20 15 23 25
7 8 10 13 19 20 15 25 23
7 8 10 13 19 20 23 15 25
 
이런 식으로 순서가 지켜진체 배열이 나오게 되죠? 우리는 앞에서부터 7개를 뽑으니 순서는 지켜지게 되구요.
 
감사합니다.
상사 큰돌 올림.
 

감사합니다!

qhdmswns님의 프로필 이미지
qhdmswns

작성한 질문수

질문하기