3322번 - 정렬의 시간복잡도 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 13 | 6 | 6 | 75.000% |
문제
꿍은 자료구조를 공부할때 각 정렬마다 비교횟수를 구해보라는 문제를 볼때마다 화가난 나머지 세상에서 제일 거지같은 문제를 만들어보고자 다음과 같은 문제를 만들었다.
N과 X가 주어질 때, 삽입정렬이 퀵정렬보다 비교를 최대 X번 더 하는 {1,2,...,N} 으로 구성된 순열의 개수를 구해야 한다. 단, 숫자가 매우 커질수 있으므로 출력값은 1234567로 나눈 나머지를 출력한다.
아래 코드는 삽입정렬 코드이며 비교횟수도 계산해준다.
procedure insertionSort(int N, array A[1..N]) defined as:
A[0] := -Infinity
for i := 2 to N do:
j := i
Increment(comparison_count)
while A[j - 1] > A[j] do:
SWAP(A[j - 1], A[j])
j := j - 1
Increment(comparison_count)
end while
end for
아래코드는 퀵정렬 코드다. 만약 정렬하려는 배열의 길이가 L이라면, partition 알고리즘은 L-1번의 비교를 한다.
procedure quickSort(list A) defined as:
list less, greater
if length(A) <= 1 then
return A
pivot := A[1]
for i := 2 to length(A) do:
Increment(comparison_count)
if A[i] < pivot then append A[i] to less
else append A[i] to greater
end if
end for
return concatenate(quickSort(less), pivot, quickSort(greater))
예를 들어, 순열 (3,1,4,2)를 생각하자. 삽입정렬의 비교횟수는 총 6회로 i=2일때 2번, i=3일때 1번, i=4일때 3번의 비교가 이루어진다. 반면 퀵정렬의 비교횟수는 총 4회로 3이 pivot일때 3회의 비교를 한 후 (1,2)와 (4)로 partition이 이루어진다. 이후 (1,2)에서 1번의 비교가 이루어지므로 총 4회의 비교가 이루어진다.
입력
입력의 첫 번째 줄에 두 개의 정수 N과 X가 주어지며 각각의 범위는 1 < N < 32, 1 ≤ X ≤ N^2 이다.
출력
삽입정렬이 퀵정렬보다 최대 X번 비교를 더 하게되는 순열의 개수를 1234567로 나눈 나머지를 출력한다.
예제 입력 1
3 1
예제 출력 1
2
예제 입력 2
6 2
예제 출력 2
719
예제 입력 3
21 3
예제 출력 3
660773
힌트
N=3 일때 가능한 6개의 순열과 각 경우의 정렬별 비교횟수는 아래와 같다.
1 2 3 - NI = 2, NQ = 3 1 3 2 - NI = 3, NQ = 3 2 1 3 - NI = 3, NQ = 2 2 3 1 - NI = 4, NQ = 2 3 1 2 - NI = 4, NQ = 3 3 2 1 - NI = 5, NQ = 3
이 문제의 데이터는 총 10개이고, 다음과 같다.
- N = 5, X = 1
- N = 12, X = 2
- N = 18, X = 3
- N = 20, X = 1
- N = 22, X = 5
- N = 23, X = 3
- N = 24, X = 4
- N = 29, X = 2
- N = 30, X = 5
- N = 31, X = 1
출처
Olympiad > Central European Olympiad in Informatics > CEOI 2009 > Day 2 5번
- 문제를 번역한 사람: seok9311
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호