kark's

기존의 데이터 집합단위를 더이상 나눌수 없는 크기가 될때까지 분할한 뒤 임시 저장공간에 순서를 저장하며 재조합하며 정렬하는 방식 평균 시간복잡도는 분할단계로 집합을 절반씩 분할하므로 O(logN) 의 시간복잡도를 갖고 병합단계 모든요소가 비교되므로 O(N) 의 시간복잡도를 갖게 되므로 전체적인 시간복잡도는 O(N log N) 로 안정적인 성능을 제공하지만 주어진 집합요소(배열 , 리스트)가 있을때 임시로 저장해둘 똑같은 크기의 집합요소가 더 필요하게 된다. 또한 해당 알고리즘 구현시 데이터들을 다시 함수에 넣어줘야하므로 재귀에 대한 개념도 필요하며 두개의 집합으로만 정렬된 데이터를 구현하기위해 여러개의 포인터를 다뤄야하므로 구현이 조금 복잡할수 있다. 처음 알고리즘을 접하게될때 그림을 보고 조금 혼란스러..

피벗을 정하고 좌 , 우측 포인터를 가리키며 기준값보다 작다면 왼쪽 , 보다 크다면 오른쪽으로 정렬하는 알고리즘 한번의 탐색이 완료되면 피벗으로 정한 값은 정렬이 완료된다. 이후 다시 피벗을 정한뒤 재귀 함수를 사용해 반복시킨뒤 더이상 정렬할 데이터가 없을때까지 반복한다. 평균적인 시간 복잡도는 O(nlogn) 이지만 최악의 상황엔 O(N²)가 된다. 또한 기존의 정렬 방식과는 달리 분할된 데이터들을 다시 함수로 다뤄줘야하므로 재귀에 대한 개념도 필요하다. 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정..

현재 선택한(정렬되지않은) 데이터를 기존 정렬된 데이터의 적절한 위치에 삽입시켜 정렬하는 방식 시간 복잡도는 O(n²) 이고 구현하기 쉬운편 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 int count = int.Parse(Console.ReadLine()); int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse); for (int i = 1; i < count; i++) { int sel..

선택정렬은 내림차순 정렬일경우 다음 인덱스의 데이터들중 가장 작은값을 현재 인덱스로 옮기는 방법 구현 방법은 조금 까다롭고, 시간 복잡도도 O(n2)으로 효율이 떨어지는 방식 대신 N 번의 루프로 N번의 데이터 순서 정렬이 확실시 된다는 점이 있다. 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 Sort(Console.ReadLine()); void Sort(string input) { int[] arr = new int[input.Length]; for (int i = 0; i < input.Length; i++) ..

버블정렬은 인접한 두 데이터의 크기를 비교해 정렬하는 방식 구현은 쉬운편이나 O(n2) 시간 복잡도를 갖는다. 해당 알고리즘은 위처럼 인덱스를 넘겨가며 데이터의 크기를 비교한 뒤 원하는 조건으로 정렬해주면 된다. 이때 전체 배열의 한 루프가 종료되면 가장 마지막 데이터는 정렬이 완료된다는것을 알수있다. 한번의 루프가 종료될때마다 탐색구간이 줄어들며 비교대상이 없을때까지 반복해주면 된다. 또한 한번의 루프동안 교체가 일어나지 않는다면 정렬이 완료된것으로 간주하면 된다. 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거..