정렬-버블정렬, 선택정렬

이론

📖 버블 정렬

• 데이터의 인접요소끼리 비교하고, SWAP연산을 수행하여 정렬.
• 시간복잡도 : O(n^2) -----> 속도가 느린편이다.

📖 선택 정렬

• 대상에서 가장 크거나 작은 데이터를 데이터가 나열된 순으로 찾아가 선택을 반복하면서 정렬.
• 시간복잡도 : O(n^2) -----> 구현방법이 복잡, 효율적x

문제풀이

📖 백준 1377 (🔗백준 1377 문제)

✏ 문제해석=swap이 한번도 일어나지 않을때가(정렬이 완료될때가) 언제인지(몇번째루프인지) 알아내기.

✏ sort()의 시간복잡도는 O(nlogn)이다.

✏ 시간초과에 유의.

✏ 버블정렬이기 때문에 swap수행 시 데이터가 이동하는 최대거리가 1이 된다. 따라서, 정렬 전과 정렬 후(sort함수이용)의 index를 비교하여, 가장 많이 이동한 값 찾기.

• 주어진 값이 10 1 5 2 3 이다.
• sort()를 이용하여 정렬하면 1 2 3 5 10 이 된다.
• 정렬 전과 정렬 후의 index를 빼면 표의 파란색부분의 값들이 나온다.
• 표의 파란색부분의 값(정렬 전과 정렬 후의 index)들 중 최대값을 max()를 이용해 찾는다.
• 최대값+1을 하면 답을 구할 수 있다.

#문제해석=swap이 한번도 일어나지 않을때가(정렬이 완료될때가) 언제인지(몇번째루프인지) 알아내기.
#sort()의 시간복잡도는 O(nlogn)이다.

import sys
input=sys.stdin.readline

n=int(input())
a=[0]*n
arr=[]

for i in range(n):
	a[i]=(int(input()),i)

sort_a=sorted(a)

for i in range(n):
	arr.append(sort_a[i][1]-i)

print(max(arr)+1)

📖 백준 1427 (🔗백준 1427 문제)

n=list(map(int,input()))
n.sort(reverse=True)

for i in n:
	print(i,end="")

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준