728x90 반응형 버블 소트2 [백준] 1517번 : 버블 소트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제의 제목은 버블 소트이지만 N의 최대 범위가 500,000이므로 버블 정렬을 사용하면 제한 시간을 초과하게 된다. 하여 해당 문제는 버블 정렬이 아닌 O(nlogn) 시간 복잡도를 가지는 병합 정렬을 사용해야 한다. 병합 정렬에서 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있으므로 병합 정렬을 사용해 문제를 풀어도 문제의 정답인 swap 횟수를 구할 수 있다. 병합 정렬로 정렬을 하는.. 2024. 1. 16. [백준] 1377번 : 버블 소트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 버블 정렬의 swap이 한 번도 일어나지 않는 루프가 언제인지 알아내는 문제이다. 버블 정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬되었다는 의미이다. 해당 경우에는 반복을 종료하여 시간 복잡도를 줄일 수 있다. 해당 문제의 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있기 때문에 다른 방법으.. 2024. 1. 13. 이전 1 다음 728x90 반응형
