연잎의 develog

문제집: N과 M (시리즈) (acmicpc.net) 문제집: N과 M (시리즈) www.acmicpc.net 오늘은 N과 M (시리즈 ) 를 통해 순열, 조합, 중복순열, 중복 조합을 연습해보려고 한다! 1. N과 M (1) : 순열 (nPm) 을 구하는 간단한 문제! [풀이] #include #include #include using namespace std; int n, m; int check[9] = { false, }; int pArr[8] = { 0, }; void permutaion(int depth) { if (depth == m) { for (int i = 0; i < m; i++) { cout num[i]; } sort(num, num + n); //오름차순 정렬 permutaion(0..

[C++] 순열(Permutation) 조합(Combination) 알고리즘 :: 개발 블로그 (tistory.com) [C++] 순열(Permutation) 조합(Combination) 알고리즘 백준에서 완전 탐색 문제를 풀다가 항상 조합과 순열을 만들 때 헷갈려서 아예 시간을 내어 정리하였다. 이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다. 이후 나오는 hongchan.tistory.com 브루트 포스 문제를 풀다보면 거의 순열 or 조합 의 연장선인 경우가 많다! 오늘은 c++ 로 순열과 조합을 어떤식으로 구현할 수 있는지 정리해보려고 한다. 1) 순열 (nPr) 서로 다른 n개 중 순서를 고려하여 서로 다른 r 개를 뽑는 경우. (순서O, 중복X) 중복을 막기위해 ch..

버블정렬이란? 인접한 두원소를 비교하여 왼쪽원소>오른쪽원소 라면 swap하고 가장 큰 데이터를 뒤로 보내면서 오름차순으로 정렬하는 기법 [원리] : 크기가 n인 배열에서 for문을 한번 돌때마다 arr[0] ~ arr[n-i] 중에 가장 큰값이 arr[n-i]번째에 오게됨. 1회전 -> 9가 맨오른쪽으로 이동. 2회전 ->8이 맨 오른쪽으로 이동. 3회전 -> 4가 맨 오른쪽으로 이동 ... 4회전 -> 2가 맨 오른쪽으로 이동 (정렬완료) 배열의 크기가 n이라고 했을때 n-1회전을 통해 배열의 원소를 모두 오름차순으로 정리할수있다. [코드] #include #include using namespace std; //정렬할 배열 vector arr; void bubbleSort(int n) { int cn..