2023.01.27

선택 정렬

선택 정렬(selection sort)는 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아 가며 선택하는 방법이다.
선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n2)으로 효율적이지 않아 코딩테스트에서는 많이 사용하지 않는다. 선택정렬원리만 간단히 알아보고 넘어가겠다.

선택 정렬의 색심 이론

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심이다.

선택정렬의 과정

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다.
3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분 범위를 축소한다.
4. 전체 데이터 크기 만큼 index가 커질 때까지, 즉, 남은 정렬 부분이 없을 떄 까지 반복한다.

선택 정렬 자체를 묻는 코딩 테스트는 잘 나오지 않지만, 이 원리를 응용하는 문제는 나올 수 있다.

내림차순으로 자릿수 정렬하기(1427번)

배열을 정렬하는 것은 쉽다. 수가 주어지면 그 수의 각 자릿수를 내림차순으로 정렬하시오

입력
2143

출력
4321

# sort 함수로 풀었을떄

import sys
input = sys.stdin.readline
n = int(input())
arr = []
for i in str(n):
    arr.append(int(i))
arr.sort(reverse=True)
answer =''
for i in range(len(arr)):
    answer +=''.join(str(arr[i]))

print(answer)

# swap으로 풀었을떄

import sys
input = sys.stdin.readline
n = int(input())
arr = []
for i in str(n):
    arr.append(int(i))
for j in range(len(arr)):
    # tmp =0
    for k in range(j+1,len(arr)):
        if arr[j] < arr[k]:
            tmp = arr[k]
            arr[k] = arr[j]
            arr[j] = tmp
answer = ''
for i in range(len(arr)):
    answer += ''.join(str(arr[i]))
print(answer)

# 선택정렬 사용

import sys
print = sys.stdout.write
A = list(input())

for i in range(len(A)):
    Max = i
    for j in range(i+1,len(A)):
    #여기서 i+1부터 len(A)까지 A[j]의 가장 큰 인덱스를 구해나가는것
        if A[j] > A[Max]:
            Max = j
    if A[i] < A[Max]:
        tmp = A[i]
        A[i] = A[Max]
        A[Max] = tmp
for i in range(len(A)):
    print(A[i])

회고

sys.stdout.write를 선언 하면 리스트에 담은 인풋이 프린트문에 찍히지 않고 오류가 발생하는데, 이 부분은 조금더 확인 해볼 필요가 있을듯.

삽입 정렬

삽입 정렬(insertion sort)는 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.
시간 복잡도는 O(n2)으로 느린편 이지만 구현하기 쉽다.

삽입정렬의 핵심 이론

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심이다.

삽입 정렬 과정

1. 현재 index에 있는 데이터 값을 선택한다.
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.
5. 전체 데이터의 크기만큼 index가 커질 떄까지, 즉 선택할 데이터가 없을 떄 까지 반복한다.

적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 (binary search) 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.

ATM(11399번)

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사림이 줄을 서 있다.
사람은 1번에서 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 P(i) 분 이다.
사람들이 줄을 서는 순서에 따라서 돈을 인출하는 데 필요한 시간의 합이 달라진다.
예를 들어 총 5명이 있고, p1 = 3, p2=1, p3=4, p4=3, p5=2 일 때를 생각해보자. [1,2,3,4,5] 순서로 줄을 선다면 1번 사람은 3분만에 돈을 뽑을 수 있다.
2번 사람은 1번 사람이 돈을 뽑을때 까지 기다려야 하므로 3+1 =4 분이 걸린다.
3번 사람은 1,2번 사람이 돈을 뽑을 떄까지 기다려야 하므로 3+1+4 = 8분이 걸린다. 4번 사람은 3+1+4+3 =11분, 5번 사람은 3+1+4+3+2=13분이 걸린다.
즉 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이다.
근데 만약 [2,5,1,4,3] 순서로 줄을 선다면, 2번은 1분, 5번은 1+2 = 3분, 1번은 1+2+3 = 6분, 4번은 1+2+3+3= 9분, 3번은 1++3+3+4 = 13분이 걸리므로 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다.
이 순서보다 모든 사람이 돈을 인출하는데 걸리는 시간이 짧을순 없다

문제 분석하기

ATM에서 모든 사람이 가장 빠른 시간에 인출하는 방법을 그리디 방식으로 해결해 봅니다.
ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 것이 곧 그리디 방식이다.
그리고 이를 위해서 인출시간을 기준으로 값을 정렬해야 한다.
N의 최댓값이 1000이고, 시간제한이 1초이므로 시간 복잡도가 O(n2)이하인 정렬 알고리즘 중 아무거나 사용해도 된다.
여기는 삽입 정렬을 이용해보자. 정렬을 마친 후에는 각 사람이 인출하는데 필요한 시간을 더하면 되겠네요.

줄을 서있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 P가 주어졌을때 각 사람이 돈을 인출하는데 걸리는 최소 시간을 구하시오

입력
5
3 1 4 3 2

출력
32

n = int(input())
arr = list(map(int,input().split()))
sumarr = [0]*n

for i in range(1,n):
    insert_point = i
    insert_value = arr[i]
    for j in range(i-1,-1,-1):
        if arr[j] < arr[i]:
            insert_point = j + 1
            break
        if j == 0:
            insert_point = 0
    for j in range(i,insert_point,-1):
        arr[j] = arr[j-1]
    arr[insert_point] = insert_value
sumarr[0] = arr[0]
for i in range(1,n):
    sumarr[i] = sumarr[i-1] + arr[i]
print(sum(sumarr))

회고

for i in range(시작,끝,갭)
ex. for i in range(5,0,-1) ==> 5부터 1까지 -1씩 줄여가겠다. (끝 값은 포함 안하니깐 5 부터 1까지 ) => 5,4,3,2,1
ex. for i in range(5,-1,-1) ==> 5부터 1까지 -1씩 줄여가겠다. (끝 값은 포함 안하니깐 5 부터 1까지 ) => 5,4,3,2,1,0
ex. for i in range(0,5,2) ==> 0부터 5까지 2씩 늘랴가겠다. (끝 값은 포함 안하니깐 0부터 4까지) => 0,1,2,3,4

• for 문으로 높은 값에서 시작해서 줄어드는 원하는 수만큼 줄이는 방법
• 소스상으로 이해 안가는 부분이 있어 직접 손으로 풀어나가봄

풀이

1. 1부터 n 까지 i가 1씩 늘어나서 돌아감.
2. ip 와 iv가 arr 배열에 맞게 값을 지정
3. j for문 실행 => 결국 i의 앞쪽(인덱스 0)의 인덱스를 모두 돌면서 파악함
4. 최초 1회만 if j ==0 을 타고 나머지는 if arr[j] < arr[i]를 탐
5. 그 다음 for range(i,insert_point,-1)을 타면 더 작은 인덱스에 큰 값이 있으면 더 뒤로 밀어넣는다.
   ex. [1,2,3,4,4] 그 다음 arr[insert_point] 에 insert_value 를 그 바뀌는 작은 인덱스 위치에 넣는다. => [1,2,3,3,4]
6. 합 배열을 구할때 sumarr[i-1]의 한개 앞의 값과 현재의 arr[i]값을 더해야 하기 때문에 for문은 1부터 len(arr)까지 도는거고 그렇기 때문에 sumarr[0]에 arr[0]을 넣고 시작한다.
7. 합배열 값 합을 sum 함수로 구함