퀵정렬 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할 pivot을 기준으로, pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 이동 start, end을 지정해서, 위의 조건을 만족하면 swap한다. start>end가 되는 순간 리스트를 분할한다. 분할된 리스트들은 각각 quick sort을 진행한다. 분할된 리스트의 원소 갯수가 1개가 되면 더 이상 quick sort 진행 X 코드 package jason.quicksort; import java.util.Arrays; public class QuickSort { static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); } static void qu..

크루스칼 알고리즘이란? 최소 신장 트리를 구하기 위한 알고리즘이다. 크루스칼 알고리즘은 그리디 알고리즘의 일종이다. 즉, 그래프의 간선을 오름차순으로 정렬한 후, 최소 비용의 간선을 선택한다. 최소 신장 트리 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 그래프 Kruskal 알고리즘 동작 1. 그래프 간선들을 가중치의 오름차순으로 정렬한다. 2. 정렬된 간선 리스트에서 사이클이 생성되지 않는 간선을 순서대로 선택한다. 2.1. 가장 작은 가중치를 먼저 선택한다. 2.2. 사이클을 형성하는 간선은 제외한다. 3. 해당 간선을 현재의 MST(Minimum Spanning Tree 최소 신장 트리)에 추가한다. 사이클 생성 여부를 확인하는 방법 추가하고자 하는 간선의 ..

다익스트라 알고리즘은 연결되어있는 그래프에서 1개의 노드에서 출발하여, 다른 모든 노드까지의 최단 경로를 출력해주는 알고리즘이다. 출발 노드 설정 최단 거리 테이블 초기화(모두 무한) 방문하지 않은 노드들 중 최단 거리가 가장 짧은 노드를 선택한다. 우선순위 큐 사용(O(ElogV, V는 정점 수, E는 간선 수) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 최단 거리 테이블을 갱신한다. 3번과 4번을 반복한다. import heapq import sys input = sys.stdin.readline() INF = int(1e9) #무한을 의미하는 값으로 10억을 설정. #노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) #시작 노드 번호를 입력받..

ContentsEulerian cirtuit(오일러 서킷)Eulerian trail(오일러 트레일)  Eulerian Circuit(오일러 서킷)오일러 서킷이라는 것은 우리들에게 한붓그리기 문제로 더 알려져 있습니다. 오일러 서킷그래프가 주어졌을 때 그래프의 한 시작점으로부터 모든 간선을 한번씩만 지나 다시 시작점으로 돌아오는 경로를 말합니다.이러한 경로가 있으려면 어떠한 조건을 만족해야 할까요?가장 많이 사용되고 있는 방법으로는 단순하게 정점의 degree를 사용하는 것입니다.degree라는 것은 위상정렬 할 때 잠시 살펴보았죠? 그 때는 indegree를 이용하였고, 여기서 degree라는 것은 정점에 연결되어 있는 간선의 수를 말합니다. 그런데 도대체 degree가 갑자기 왜나올까요? 1) 무향그래..

[Algorithm] Binary Counting - 부분집합, power set 구하기void main(void){ int i, j; char arr[4] = { 'a', 'b', 'c', 'd' }; int n = 4; for (i = 0; i 12n의 값을 갖는다.원소가 n개일 경우의 모든 부분집합의 수를 의미한다.Power set(모든 부분 집합)-공집합과 자기 자신을 포함한 모든 부분집합-각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.i & (1 계산 결과는 i의 j번째 비트가 1인지 아닌지를 의미한다.10 진수이진수{A, B, C, D}00000 10001A20010B30011B, A40100C50101C, A60110C, ..

#define _CRT_SECURE_NO_WARNINGS #include #include using namespace std;vector subset;int n = 4;void search(int k){ if (k == n + 1) { for (int i = 0; i 1부터 n까지의 숫자로 만들 수 있는 부분 집합의 경우의 수를 출력하는 함수다.마지막 공집합은 빈 줄로 출력이 되기 때문에 실수로 놓치는 것에 주의한다. 우리가 부분집합을 손으로 (가지치기하여) 구할 때와 유사한 방식이라고 생각한다.다만 재귀 알고리즘은 익숙하지 않으면 코드 자체를 보고 실행결과를 예상하기가 힘들다.  아래는 n = 7 , r = 4 라고 가정..

Hash개념임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array이다키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수라고 한다해시값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)로 매우 빠르다해시함수위에 설명한 것과 같이 키에 대한 해시값을 만드는 함수계산이 복잡하지 않고 키값에 대해 중복 없이 해시값을 고르게 만들어 내는 함수가 좋은 함수 (충돌이 일어나지 않을수록 좋다)대표적으로 나눗셈 법(Division Method)과 곱셉 법(Multiplication Method)..