연결성분 그래프에서 최대로 연결된 부분 그래프 어떻게 구할까 방법은 간단하다. 정점을 차례대로 DFS/BFS 를 실행한다. -> 이때 방문되면 서로 연결되어 있음 해당 visited 배열에 boolean 값 대신, 각각의 부분그래프를 나타낼 요소를 넣는다. visted 배열을 돌려가며 가장 빈도수가 높은 숫자의 요소들을 출력한다. * 아래 연결성분 찾는 메서드는 그래프의 간선이 1-2-3 4-5 이렇게 순차적으로 되어있다고 가정한것. - dfs 메서드를 포함한 graph 클래스 (인접리스트로 구현) class Graph{ private static int vn; //정점개수 private static int[] visited; //방문여부 private static ArrayList graph = new..
[자료구조 복습12] Radix Sort 기수정렬
해당 글은 geeks for geeks와 위키피디아 를 참고하여 쓰여졌습니다. 먼저 Radix sort가 어떻게 동작하는지 알아보자. Radix Sort는 요소 간의 비교 없이 동작하는 소팅 알고리즘 이다. 단순하게 생각하면 최댓값 n개의 배열을 만들고, 해당하는 수를 인덱스로 하는 배열 요소의 빈도수를 증가시킨 후 , 다시 배열을 돌면서 빈도수만큼 해당 인덱스를 출력해도 된다. 하지만 배열이 [1,2,10000,999,80] 이렇게 생긴 경우는 효율성이 매우 떨어진다. 이를 위해서 각 자리수를 비교해 나가며 정렬하는 Radix Sort를 학습해보자. 배열 [170, 45, 75 , 90 , 802 , 24 , 2 , 66 ] 을 예시로 들어보자. 1의자리수부터 최댓값 n의 최대 자리수까지 본다. 해당 ..
[자료구조 복습 11] Median of Three Quick Sort중간값 퀵소트
중간값 퀵소트 (중간값 퀵소트에 대한 내용은 https://blog.naver.com/occidere/220870294816 를 참고했음을 밝힌다. 피벗값을 맨 앞, 맨 뒤로 설정하는 것에 대한 대안이 바로 '중간값 퀵소트' "Median QuickSort" 이다. 중간값 퀵소트의 원리는 일단 다음과 같다. 1. front, mid, rear 세 부분을 먼저 소트 해준다. 2. 만약 요소가 4개 이상으로 남아있다면, 기존의 퀵소트와 같은 방식으로 파티션을 해준다. -> 이 후, 피벗값의 자리를 기준으로 피벗값 앞, 피벗값 뒤를 다시 퀵소트 알고리즘을 호출해준다. 헷갈리는 내용이 많으니 아래 그림과 정리를 보면서 이해해보자. 1) pivot 값을 rear - 1 로 옮겨주는 이유는, 파티션 루프를 통해서 ..
[자료구조 복습 10] Quick Sort 퀵 정렬
일반 퀵소트 1. 파티션 함수를 통해 '피벗값'을 정한다. - 여기서 파티션 함수의 수행은 이러하다 1) 피벗값을 중심으로 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰 값을 정렬한다. 2) 이를위해 left와 right이 배열을 따라 내려오면서, arr[left] > pivot 인경우와 arr[right] right 이 되는 경우, 즉 right과 left가 서로 교차하는 경우 루프를 멈추어준다. 4) 멈춘 곳에서 right과 우리가 정한 pivot의 자리를 바꾸어준다. 왜냐하면, pivot을 맨 첫번째 요소로 선택한다 했을때, pivot은 자신보다 작은 값과 바꾸어 져야하는데 pivot보다 작은 값을 마지막으로 가리키고 있는 것은 right이기 때문이다. 즉,pivot값 이렇게 위치해있으므로 ..