알고리즘15 [정렬] 기수정렬 정렬정렬 알고리즘정의시간복잡도삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식O(N) ~ O(N^2)버블데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식O(N^2)선택대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식O(N^2)퀵pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식O(NlogN) ~ O(N^2)힙이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해정렬하는 방식O(NlogN)병합이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식O(NlogN) + 추가적인 메모리 필요기수데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식O(N) + 추가적인 메모리 필요기수정렬이란?.. 2024. 11. 14. [정렬] 병합정렬 정렬정렬 알고리즘정의시간복잡도삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식O(N) ~ O(N^2)버블데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식O(N^2)선택대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식O(N^2)퀵pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식O(NlogN) ~ O(N^2)힙이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해정렬하는 방식O(NlogN)병합이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식O(NlogN) + 추가적인 메모리 필요기수데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식O(N) + 추가적인 메모리 필요 병합정렬병합.. 2024. 11. 12. [퀵 정렬] 백준 11004번 문제- Array를 오름차순 정렬했을 때 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오- 데이터 개수 ( 1 - K번째 수 ( 1 문제 분석시간 제한 2초 : 2억번 연산 내에 구현(NlogN 일경우, 시간제한에 있어서는 통과할 시간복잡도이다)- 오름차순 정렬이 필요하므로, 퀵정렬을 이용한 풀이를 진행pivot 정하는 방법pivot == k : k 번째 수를 찾은 것이므로 알고리즘을 종료pivot > k : pivot의 왼쪽 부분에 K가 있으므로 왼쪽 (S ~ pivot -1) 만 정렬을 수행한다pivot 퀵정렬은 pivot이 지정되있는 곳이 정렬된 숫자이다 슈도 코드N(숫자의 개수) K(K번째 수)A(숫자 데이터 저장 배열)for(N만큼 반복하기){ 배열 저장하기}퀵소트 실행K번째 데.. 2024. 11. 12. [정렬] 퀵 정렬 정렬정렬 알고리즘정의시간복잡도삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식O(N) ~ O(N^2)버블데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식O(N^2)선택대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식O(N^2)퀵pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식O(NlogN) ~ O(N^2)힙이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해정렬하는 방식O(NlogN)병합이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식O(NlogN) + 추가적인 메모리 필요기수데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식O(N) + 추가적인 메모리 필요 퀵정렬이란?.. 2024. 11. 11. [버블정렬] 백준 2750번 문제N개의 수가 주어졌을 때, 이를 오름차순 정렬하는 프로그램을 작성하시오.- 1번째 줄에 수의 개수 N (1 - 2번째 줄부터 N개의 줄에 숫자가 주어짐- 수는 중복되지 않는다 문제 분석하기숫자 범위가 1,000으로 매우 작기 때문에, O(N^2) 시간복잡도 알고리즘을 사용해도 문제 없음버블정렬 알고리즘을 이용하여 문제풀이 슈도코드N(정렬할 수 개수)A(정렬할 배열 선언)for(i : 0~N -1){ for(j : 0 ~ N -1 -i) { 현재 A배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기 }}A 배열 출력 구현import java.io.BufferedReader;import java.io.InputStreamReader;public class App .. 2024. 11. 7. [정렬] 버블정렬 정렬정렬 알고리즘정의시간복잡도삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식O(N) ~ O(N^2)버블데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식O(N^2)선택대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식O(N^2)퀵pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식O(NlogN) ~ O(N^2)힙이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해 정렬하는 방식O(NlogN)병합이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식O(NlogN) + 추가적인 메모리 필요기수데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식O(N) + 추가적인 메모리 필요 버블정렬데.. 2024. 11. 7. 이전 1 2 3 다음