Coding Test/Sort

[10989] 수 정렬하기3 (1 ≤ N ≤ 10,000,000, K≤10,000, 계수 정렬)

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 분석 N의 최대 개수가 10,000,000으로 매우 큼. 주어지는 숫자의 크기가 10,000보다 작은 자연수 계수 정렬의 시간복잡도 : O(kn) 수열 A : 5 2 3 1 4 2 3 5 1 7 count 배열 0 1 2 3 4 5 6 7 ... 10001 0 2 2 2 1 2 0 1 0 풀이 """ N개의 수가 주어졌을 때, 이를 오름차순으로 정렬 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,00..

[1517] 버블 소트 (병합 정렬, swap 횟수)

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 분석 N(1 ≤ N ≤ 500,000)이므로 nlogn 병합정렬로 풀이 시간복잡도, 시간제한, 빅오(Big-O) 표기법 1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만 karla.tistory.com 풀이 """ 1517 N개의 수로 이루어진 수열 A[1], A[2], …, A[..

[2751] 수 정렬하기2 (1 ≤ N ≤ 1,000,000, abs(K) ≤ 1,000,000, 병합 정렬)

2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 분석 N(1 ≤ N ≤ 1,000,000) nlogn 병합정렬로 풀이 시간복잡도, 시간제한, 빅오(Big-O) 표기법 1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만 karla.tistory.com 풀이 import sys input=sys.stdin.readline n=int(input()..

[11004]K번째 수 (병합 정렬 풀이)

11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 N(1 ≤ N ≤ 5,000,000)로 nlogn 병합 정렬로 풀이 시간복잡도, 시간제한, 빅오(Big-O) 표기법 1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만 karla.tistory.com 내장함수 풀이 import sys input=sys.stdin.readline n,k=map(int,input().split()) a=list(map(int..

[11399] ATM (삽입 정렬 풀이, 그리디)

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 내장함수 풀이 n=int(input()) a=list(map(int,input().split())) a.sort() s=[0]*n # 합배열 s[0]=a[0] for i in range(1,n): # 합배열 만들기 s[i]=s[i-1]+a[i] total=0 for i in range(0,n): # 합배열 총합 구하기 total+=s[i] print(total) 삽입정렬 풀이 n=int(input()) a=list(map(int,input().split())) s=[0]*n # 합배열 # 삽입..

[1427] 소트인사이드 (내림차순 정렬, 선택정렬 풀이)

1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 내장함수 풀이 a=list(input()) a.sort(reverse=True) for i in range(len(a)): print(a[i], end="") 선택정렬 풀이 """ 1427 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬 N이 주어진다. N(1~1,000,000,000) 9 2143 """ a=list(input()) length=len(a) for i in range(length): maxIdx=i for j in range(i+1,length): if a[j]>a[maxIdx]: maxIdx=j if a[i]

[1377] 버블 소트 (정렬 인덱스, 안쪽 for문 실행 횟수, swap)

1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 분석 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제 버블정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다 == 이미 모든 데이터가 정렬됐다 N은 500,000보다 작거나 같은 자연수 : n^2불가 안쪽 루프는 1에서 n-j까지 swap 수행, 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이므로 데이터의 정렬 전 인덱스와 정렬 수 인덱스를 비교..