재시민

www.acmicpc.net/step/34

고등 확률과 통계에서 배우는 순열과 조합이다.

순열과 조합을 구현하는데에 있어 매번 구글링 하기 귀찮아 좋은 정보를 얻어 정리를 해보려고한다.

출처 : hongchan.tistory.com/5

덕분에 좋은 정보를 얻었다.

순열 nPr

void printArray(int a[], int r) {
    for (int i = 0;i < r;i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void permutation(int pArr[], bool check[], int n, int r, int depth) {
    if (depth == r) {
        printArray(pArr, r);
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!check[i]) {
            check[i] = true;
            pArr[depth] = i;
            permutation(pArr, check, n, r, depth + 1);
            check[i] = false;
        }
    }
}

int main(void) {

    int n, r;
    cin >> n >> r;
    int* pArr = new int[r];
    bool* check = new bool[n + 1];
    for (int i = 0;i < r;i++) {
        pArr[i] = 0;
    }
    for (int i = 0;i < n + 1;i++) {
        check[i] = false;
    }
    permutation(pArr, check, n, r, 0);

    return 0;
}

1. pArr[] : n 까지의 숫자의 경우를 저장할 배열
2. check[] : 순열에서 중복의 여부를 확인하는 배열 ( 이 배열을 뺀다면 중복 순열이 된다. )

알고리즘 설명

1. check 가 false 인지 확인 ( 이미 나온 숫자인가? )
2. false 이면 true 로 할당
3. pArr[] 에 i 할당 ( 1부터 저장하기 위해 i = 1 로 지정 )
4. Permutation(...,depth + 1) 실행하여 중복되지 않는 수를 확인하고 배열에 삽입
5. depth == r 이 된다면 pArr 에 있는 원소 모두 출력
6. check 를 차례대로 false 로 할당하면서 함수 빠져나옴
7. for 문 반복

조합 nCr

void combination(int pArr[], int n, int r, int depth, int next) {
    if (depth == r) {
        printArray(pArr, r);
        return;
    }

    for (int i = next; i <= n; i++) {
        pArr[depth] = i;
        combination(pArr,n, r, depth + 1, i+1);// i+1 을 i로 바꿔주면 중복 허용
    }
}

int main(void) {

    int n, r;
    cin >> n >> r;
    int* pArr = new int[r];
    for (int i = 0;i < r;i++) {
        pArr[i] = 0;
    }
    combination(pArr, n, r, 0, 1);

    return 0;
}

순열과 다른 점 

• 조합은 순열과 달리 오름차순으로 정렬이 된다.

따라서, for 문의 i 값이 combination 이 실행될 수록 이 전 i 값보다 커야한다.

그리고, check[] 배열을 사용하지 않는 이유는 i 값을 늘려줌으로써 이전의 i 값이나 동일한 값이 들어가지 않기 때문이다.

그래서, i 의 값을 유지시킨다면 중복 조합이 된다. 

재귀로된 순열과 조합을 설명해 보았다.

하지만, 재귀인만큼 큰 수로 접근하게 된다면 overflow 발생 가능성도 있고 무엇보다 느리다.

이와 관련된 문제를 풀었었는데 까먹었다. ㅎㅎ

www.acmicpc.net/problem/9012

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main(void) {
	int i,T;
	stack<char> s1;
	cin >> T;
	string line;
	for (i = 0;i < T;i++) {
		cin >> line;

		for (int j = 0;j < line.size();j++) {
			char a;
			a = line.at(j);
			if(a == '(')
				s1.push(a);
			else if (a == ')') {
				if (!(s1.empty())) {
					if (s1.top() == '(')
						s1.pop();
				}
				else if (s1.empty())
					s1.push(a);
				else s1.push(a);
			}
		}
		if (s1.empty())cout << "YES"<<'\n';
		else {
			cout << "NO" << '\n';
			while (!s1.empty()) {
				s1.pop();
			}
		}
	}
	return 0;
}

2학년때 후위도 표기로 구현된 계산기를 만들때가 생각난 문제

조금 다른느낌이지만 괄호구현하는거 때문에 애가 탔었던 기억이 난다.

EZ

www.acmicpc.net/problem/10773

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
	int T, num;
	int sum = 0;

	cin >> T;
	int i;
	stack<int> number;
	for (i = 0;i < T;i++) {
		cin >> num;
		if (num != 0)
			number.push(num);
		else if (num == 0) {
			if (number.empty()) number.push(num);
			else number.pop();
		}
	}
	int size =number.size();
	for (i = 0;i < size;i++) {
		sum += number.top();
		number.pop();
	}
	cout << sum;
	return 0;
}

힌트를 안보고 풀다가 좀 헤맸는데 결국 풀어냈다.

스택에 전부 집어넣고 하다가 안풀려서 생각의 전환을 해봤다.

그래서 히히 난 천재야 하며 즐거워했지만

밑에 힌트가 있었다는게 함정이었다.ㅠㅠ

www.acmicpc.net/problem/1546

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	double T,i;
	double num, max;
	double sum = 0.0;
	cin >> T;
	vector<double> mean;
	for (i = 0;i < T;i++) {
		cin >> num;
		mean.push_back(num);
		
	}
	max = *max_element(mean.begin(), mean.end());
	//cout << max << '\n';
	for (i = 0;i < T;i++) {
			mean[i] = mean[i] / max * 100;
	}
	for (i = 0;i < T;i++) {
		sum += mean[i];
	}
	cout << sum / T;
	return 0;
}

처음에는 되게 쉽다고 시작했는데

중간에 이상한 코드를 하나 짜서 나의 능지에 의심을 품었지만 찾아버리고 말았다.

하지만 브론즈 1문제 였고..

아직 갈길이 멀다.

얼른 실버 찍어야징