공부공부/알고리즘!14 유니온 파인드 [Union Find] 알고리즘 유니온 파인드 알고리즘이란? 두 노드에 대해 같은 그래프에 속해 있는지를 파악하는 알고리즘! 만약 아래처럼 노드들이 2개의 그래프로 나누어져 있다면 A와 B의 관계에 대해서 어떻게 알아낼 것인가에 대한 알고리즘입니다. 이름은 생소하지만 어렵지 않은 알고리즘! 구현 방법은 다음과 같이 정리해볼 수 있습니다. 1. 현재 노드의 부모노드들을 설정 2. 관계에 대해 알고싶은 두 노드들의 최종 부모노드를 비교 /판별 이것에 맞게 코드를 구성해 보겠습니다. 코드! 코드는 다음과 같이 간단하게 구성됩니다. int parents[51]; ... int Find(int x) { // 최종 부모노드 찾기 if (parents[x] == x) { return x; } return x = Find(parents[x]); } .. 2023. 6. 3. [알고리즘!]--(카라츠바 알고리즘 / c++) 카라츠 바 알고리즘이란? 수 백 자리 이상의 큰 수의 곱셈할 때 사용하는 알고리즘으로 곱셈의 올림수 연산을 생략한 상태로 계산 후 덧셈, 뻴셈연산으로 더욱 빠르게 계산할 수 있게 해주는 알고리즘! 형식은 아래처럼 한자리 곱셈으로 곱을 해주고 나머지는 모두 덧셈으로 풀리게 됩니다! 예시를 보면 이렇게! 위에서 보이는 것처럼 한자리 곱셈을 제외한 모든 것들이 덧셈으로 해결 가능합니다! 이제 코드로 한 번해보시죠! void nomalize(vector& num) {//마지막 자릿수 계산 num.push_back(0); for (int i=0; i 1 && num.back() == 0) num.pop_back(); } vector kara(const vector& a, const vector& b) {//int.. 2022. 6. 30. 정렬 알고리즘[2] -- 버블 정렬 알고리즘 버블 정렬 알고리즘이란? 한 값을 지정해놓고 이값과 다음값을 비교하며 크다면 이동 작다면 break로 값을 정렬하는 방식입니다! 마치 물속의 거품이 위로 올라오듯이 큰값은 비교와 swap을 통해 맨뒤로 이동하게됩니다! 만약 1 4 5 3 2 라는 배열이 있다면 1 4 3 5 2 -- 탐색중... 5, 3 스왑 1 4 3 2 5 -- 2, 5 스왑 1 3 4 2 5 -- 처음으로 돌아와 탐색..... 3, 4 스왑 1 3 2 4 5 -- 2, 4 스왑 1 2 3 4 5 -- 처음으로 돌아와 탐색..... 2, 3 스왑 이런식으로 정렬하는방식! 특징이 있다면 1. 다음값이 현재값보다 작을때 스왑시킨다. 2. 현재값의 정렬이 끝나면 처음으로 돌아와 다시 진행한다. 이제 코드! #include #include .. 2022. 6. 28. 정렬 알고리즘[1] -- 선택 정렬 알고리즘 선택 정렬 알고리즘이란? 배열의 값들중 가장작은 값을 구한후 앞쪽으로 이동시키는 방법! 만약 3 4 5 1 2 라는 배열이 있다면 1 4 5 3 2 --가장 작은 1과 앞자리 3을 변경 1 2 5 3 4 --그 다음 작은 2과 앞자리 4을 변경 1 2 3 5 4 --그 다음작은 3과 앞자리 5을 변경 1 2 3 4 5 --그 다음작은 4과 앞자리 5을 변경 이런식으로 swap을 통해 작은 순서대로 정렬시키는 알고리즘입니다. 이런식으로 구성하기 위해 코드에서 필요한 부분을 적어보면 1. 가장작은 숫자 탐색 2. count로 어디까지 정렬되었는지 표시 3. 두 위치를 swap을 통해 위치변경 이렇게 3단계로 이루워 질것 같습니다. 코드 시작! 코드 1 #include #include using namespa.. 2022. 6. 28. 알고스팟(algospot) 32장 네트워크 유량 32.1 도입이런 그래프가 하나 있을 때 크기가 10인 데이터는 아마 s--> a--> c--> t라는 경로만 지나가게 될 것입니다. 그런데 여기서데이터 전송 시 데이터를 쪼개서 여러 경로로 동시에 전송 가능하다면?나눠서 더 빠르게! 전송 가능--> 이것이 네트워크 유량! 좀 더 유량 네트워크- 간선의 용량이라는 속성이 존재하는 방향 그래프- 항상 세 가지 속성을 만족해야 한다.용량 제한 속성 - 각 간선의 유량(이동할 데이터량)은 해당 간선의 용량(이동할 수 있는 총량) 초과 x유량의 대칭성 - u에서 v라 흘러올 경우 udptjsms 음수의 유량을 보내는 것이라 생각하자-->?유량의 보존 - 나가고 들어오는 유량은 항상 같아야 함! 32.2 포드 -폴 커슨 .. 2022. 5. 22. 알고스팟(algospot) 31장 최소 스패닝 트리(크루스칼과 프림 알고리즘) 31.1 도입-스패닝 트리(=신장 트리)? --> 사이클이 없고, 그래프 내의 모든 정점을 포함하는 트리 -일반 스패닝 트리는 여러 개가 있을 수 있다. -최소 스패닝 트리는 무조건 1개! - 최소 스패닝 트리를 해결해줄 2가지 알고리즘! 크루스 칼 알고리즘--> 배타적 집합 자료구조의 사용! (Union find) 프림 알고리즘--> 다익스트라 알고리즘과 비슷 * 둘 다 무방향 그래프일 때만 사용! 31.2 크루스 칼의 최소 스패닝 트리 알고리즘 가중치가 작은 간선과 큰 간선중 어느 쪽이 최소 스패닝 트리에 포함될 가능성이 높을까?---> 당연히 작은 간선! 이를 통한 알고리즘!1. 모든 간선을 가중치의 오름 차순으로 정렬한 뒤2. 하나씩 추.. 2022. 5. 22. 이전 1 2 3 다음 728x90 반응형
