Stable Sort (안정 정렬) 중복된 키를 순서대로 정렬하는 정렬 알고리즘 같은 값이 2개 이상 리스트에 등장할 때 기존 리스트에 있던 순서대로 중복된 키들이 정렬된 다는 것을 의미 list = [2, 8, 9, 4(1), 1, 4(2), 6, 7]는 4라는 값이 중복됨 Stable sort 알고리즘으로 정렬 시 [1, 2, 4(1), 4(2), 6, 7, 8, 9] Unstable sort 알고리즘으로 정렬 시 [1, 2, 4(2), 4(1), 6, 7, 8, 9] stable sort로 정렬하는 알고리즘들의 순서는 항상 똑같기에 항상 결과가 같음을 보장할 수 있음 첫 문자를 기준으로 문자열을 정렬하는 경우 정렬할 때마다 순서가 다르면 혼란스러울 수 있기 때문에, 항상 안정적으로 같은 리스트가 리..

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()..

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번: 버블 소트 첫째 줄에 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이므로 데이터의 정렬 전 인덱스와 정렬 수 인덱스를 비교..

문제 오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력 3 1 3 5 5 2 3 6 7 9 1 2 3 3 5 6 7 9 분석 sort()의 시간복잡도 : nlogn ➔ 정렬된 두 리스트 합치기 시간복잡도 : n 풀이 # 시간복잡도 n n=int(input()) a=list(map(int,input().split())) m=int(input()) b=list(map(int,input().split())) c=[] # 정답 리스트 p1=p2=0 while p1