본문 바로가기

전체 글228

[정렬] 기수정렬 정렬정렬 알고리즘정의시간복잡도삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식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.
[정렬] 백준 1517번 문제버블정렬에 관한 이야기 진행- 인접해 있는 두 수를 swap하며 정렬 진행- (배열 크기 + 배열 제공)- 버블정렬을 진행할 때, swap하는 횟수를 구하는 프로그램을 작성하시오시간 제한 : 1초버블정렬 시간복잡도 : O(N^2)배열 범위 : 1 문제분석버블정렬로 진행할 시, 시간 초과로 인해 swap을 구하더라도 문제에 제시되어있는 시간을 지킬 수가 없다.따라서, O(NlogN)을 가진 정렬하는 방식을 채택해야함(병합 정렬 선택)병합정렬 선택시 주의할점)병합정렬이 swap되는 횟수를 구하는 것이 아닌, 버블정렬이 swap되는 횟수를 구해야함인덱스 위치의 변화를 통한 , 버블정렬의 swap 횟수를 구해야함예시2를 이동시에 5와 6을 뒤로 보내야한다 ( 버블정렬 시 swap되는 항목 )(2,5) , (.. 2024. 11. 13.
[병합 정렬] 백준 2751번 문제- 배열의 크기 N 제공- 배열 제공 ( 개행을 통해 입력 )- 해당 배열을 오름차순으로 정렬(1 문제분석1,000,000이므로 O(NlogN)으로 해결할 수 있는 정렬 방법 탐색- 병합정렬을 이용하여, 정렬 진행  병합정렬 예시순서배열첫번째42 (set1)32 (set2)24 (set3)60 (set4)15 (set5)5 (set6)90 (set7)45 (set8)두번째32 (set1)42 (set1)24 (set2)60 (set2)5 (set3)15 (set3)45 (set4)90 (set4)세번째24( set1)32 (set1)42 (set1)60 (set1)5 (set2)15 (set2)45 (set2)90 (set2)네번째 (정렬)515243242456090set를 작은 단위의 그룹으로 나눈.. 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. 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.

티스토리툴바