C_C++ 프로그래밍/C_C++ 프로그래밍
-
-
유니온 파인드란?? (Union-Find)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 5. 12. 23:09
유니온 파인드(Union-Find)란 ? CS에서 서로소 집합을 찾는 기능을 구현하기 위해 중요한 역할을 하며 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. (MakeSet으로 각각의 요소를 생성하였다) (union 연산을 수 차례 수행하여 집합을 생성하였다) 출처 : 위키피디아 크게 세 가지 기능으로 분류를 할 수 있다. 1. Union function Union(x, y) // x와 y를 같은 집합으로 묶는 작업이다. xRoot := Find(x) // x의 최상단 부모를 찾음 (x의 집합이 어디인가?) yRoot := Find(y) // y의 최상단 부모를 찾음 (y의 집합이 어디인가?) xRoot.parent := yRoot // x와 y를 묶는다. 2...
-
[C++] 소수 구하기 (에라토스테네스의 체)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 22. 03:02
보통 소수라 하면, 1과 자기자신을 제외하고는 나누어 떨어지지 않는 수라고 불린다.이를 구하기 위해서 하나 하나씩 나누어 떨어지는 지 검사를 하고는 했는데 더 빠르게 구할 수 있는 방법이 있다. 바로'에라토스테네스의 체' 라는 알고리즘을 사용하는 것이다. 에라토스테네스의 체는, 미리 범위를 정하여 소수인지 아닌지 구하여배열에 저장을 한 뒤에, 일반적으로 사용이 된다. 로직은 다음과 같다. 1은 소수가 아니다. 2는 소수이다. -> 2의 배수는 소수가 아니다.3은 소수이다. -> 3의 배수는 소수가 아니다.4는 소수가 이미 아니다.5는 소수이다. -> 5의 배수가 소수가 아니다.... (반복) 식으로 구현이 가능하며, boolean 값을 가지는 check 배열을 사용하여반복문을 돌려준다. 1. 1의 소수가..
-
[C++] next_permutation을 사용한 조합 만들기C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 21. 21:28
순열을 사용하여 조합을 만들어내는 방법입니다. 로직을 설명하면 vector 를 2개를 선언하고 하나는 원소를 삽입하는 vector list를 또 다른 하나는 순서 제어를 위해서 next_permutation을 사용할 vector idx를 만듭니다. 이어서 몇 개의 원소를 뽑을지 결정하는 변수 r 만큼 idx에 1을 list의 크기 (n이라고 하겠습니다) - r 만큼 idx에 0을 넣습니다. 그 뒤로 idx를 next_permutation을 사용하여 반복하여 idx의 원소가 1일 때마다 list의 원소를 출력해주면 됩니다. 저는 내림차순으로 출력하기 위해서 desc라는 함수를 따로 작성하였습니다. 소스코드 12345678910111213141516171819202122232425262728293031323..
-
[C++] 삽입 정렬 (Insertion Sort)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 1. 23:20
삽입 정렬은 배열을 그룹을 두 개로 나누어 E = {5,4,3,2,1} 이 있다고 하면 {5}를 key로 두고, 이보다 작은 index을 확인하여, 삽입하는 정렬 방법이다. 그 다음의 key는 4... 3.. 2 .. 1 순이다. 아래 소스에서는 j를 유심히 잘 봐야 한다. #include using namespace std; int main(){ int size,i,j; cin >> size; int *arr = new int[size]; for(i = 0; i > arr[i]; for(i = 0; i = 0; j--){ if(key >= arr[j]) break; arr[j+1] = ..
-
[C++] 버블 정렬(Bubble Sort)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 1. 22:49
버블 정렬은 인접한 원소들을 교환하며, 이 모습이 흡사 거품들이 뾰로록 일어나는 것과 같다고 하여, Bubble Sort라고 불립니다. (교환 정렬이라고도 불립니다. Exchange Sort) ...더보기 이해 E[5] = {95, 75, 85, 100, 75}이며 이를 오름차순으로 정렬한다면. (95, 75), 85, 100, 50 => 75, 95, 85, 100, 50 75, (95, 85), 100, 50 => 75, 85, 95, 100, 50 75, 85, (95, 100), 50 => 75, 85, 95, 100, 50 75, 85, 95, (100, 50) => 75, 85, 95, 50, 100 자, 여기에서 마지막 요소가 배열의 최댓값으로 들어갔습니다. (75, 85), 95, 50, ..
-
[C++] 선택정렬(Selected Sort)C_C++ 프로그래밍/C_C++ 프로그래밍 2019. 4. 1. 22:15
간단하게 말해서, 선택 정렬은 입력된 값 중 원소를 선택하여 정렬하는 방식이다. ...더보기 이해 (원소1), (원소 2), 원소 3, 원소 4, 원소 5 (원소 1), 원소 2, (원소 3), 원소 4, 원소 5 ...... (원소 1), 원소 2, 원소 3, 원소 4, (원소 5) 까지 비교하여 원소 1에 최소 값이 들어갔으므로(오름차순이라면) 이제는 index 1부터 정렬을 시작하여 원소 1, (원소 2), (원소 3), 원소 4, 원소 5 ... 원소 1, (원소 2), 원소 3, 원소 4, (원소 5) 까지 비교하는 하는 방식이다. 최종적으로는 원소 1, 원소 2, 원소 3, (원소 4), (원소 5) 를 비교하게 된다. #include using namespace std; int main(){..
-
[C++] pair sortC_C++ 프로그래밍/C_C++ 프로그래밍 2019. 3. 21. 19:33
C++의 STL에서 vector 사용시, pair container와 함께 쓰이고는 하는데,이때, x좌표 오름차순 혹은 y좌표 오름차순으로 나타내고자 할때, sort의 세번째 인자로사용자 함수 bool compare를 작성하여, 사용하기도 한다. 1234567891011121314151617181920212223242526272829#include#include#include using namespace std; bool sortbyfirst(const pair &a, const pair &b) { return (a.first > n; // 입력 횟수 vectorv; while(n--){ int x,y; cin >> x >> y; v.push_back(make_pair(x,y)); } sort(v.beg..