본문 바로가기

C_C++ 프로그래밍/C_C++ 프로그래밍11

[Cpp] 입출력 실행속도 줄이는 법 (시간 단축) 보호되어 있는 글 입니다. 2021. 12. 23.
유니온 파인드란?? (Union-Find) 유니온 파인드(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... 2019. 5. 12.
[C++] 소수 구하기 (에라토스테네스의 체) 보통 소수라 하면, 1과 자기자신을 제외하고는 나누어 떨어지지 않는 수라고 불린다.이를 구하기 위해서 하나 하나씩 나누어 떨어지는 지 검사를 하고는 했는데 더 빠르게 구할 수 있는 방법이 있다. 바로'에라토스테네스의 체' 라는 알고리즘을 사용하는 것이다. 에라토스테네스의 체는, 미리 범위를 정하여 소수인지 아닌지 구하여배열에 저장을 한 뒤에, 일반적으로 사용이 된다. 로직은 다음과 같다. 1은 소수가 아니다. 2는 소수이다. -> 2의 배수는 소수가 아니다.3은 소수이다. -> 3의 배수는 소수가 아니다.4는 소수가 이미 아니다.5는 소수이다. -> 5의 배수가 소수가 아니다.... (반복) 식으로 구현이 가능하며, boolean 값을 가지는 check 배열을 사용하여반복문을 돌려준다. 1. 1의 소수가.. 2019. 4. 22.
[C++] next_permutation을 사용한 조합 만들기 순열을 사용하여 조합을 만들어내는 방법입니다. 로직을 설명하면 vector 를 2개를 선언하고 하나는 원소를 삽입하는 vector list를 또 다른 하나는 순서 제어를 위해서 next_permutation을 사용할 vector idx를 만듭니다. 이어서 몇 개의 원소를 뽑을지 결정하는 변수 r 만큼 idx에 1을 list의 크기 (n이라고 하겠습니다) - r 만큼 idx에 0을 넣습니다. 그 뒤로 idx를 next_permutation을 사용하여 반복하여 idx의 원소가 1일 때마다 list의 원소를 출력해주면 됩니다. 저는 내림차순으로 출력하기 위해서 desc라는 함수를 따로 작성하였습니다. 소스코드 12345678910111213141516171819202122232425262728293031323.. 2019. 4. 21.
[C++] 삽입 정렬 (Insertion Sort) 삽입 정렬은 배열을 그룹을 두 개로 나누어 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] = .. 2019. 4. 1.
[C++] 버블 정렬(Bubble Sort) 버블 정렬은 인접한 원소들을 교환하며, 이 모습이 흡사 거품들이 뾰로록 일어나는 것과 같다고 하여, 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, .. 2019. 4. 1.

티스토리툴바