알고리즘 스터디 4일차

목차

1. 버블 정렬

2. 버블 정렬 실전 문제

3. 선택 정렬

4. 선택 정렬 실전 문제

5. 삽입 정렬

6. 삽입 정렬 실전 문제

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 버블 정렬

두 인접한 데이터의 크기를 비교해 정렬하는 방법 (하나의 정렬이 끝나면 비교대상이 없을 때까지 반복 : N*N)

시간복잡도 : O(n²)

 

 

2. 버블 정렬 실전 문제

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

처음코드

import sys
input = sys.stdin.readline

N = int(input())
A=[]
for i in range(N):
    A.append(int(input()))

B=A.copy()
for i in range(N-1):
    if B[i] > B[i+1]:
        B[i],B[i+1] = B[i+1],B[i]
answer = 1

while(A!=B):
    A=B.copy()
    for i in range(N-1):
        if B[i] > B[i+1]:
            B[i],B[i+1] = B[i+1],B[i]
    answer+=1
print(answer)

 

결과는 역시나 시간초과.. ㅜㅜ 

검색을 통해 풀었는데 해결법은 다음과 같다.

1) 값과 순서를 함께 저장

2) sort를 이용해 정렬시킨 후 기존의 리스트에서 순서 부분을 뺌 = 이동한 거리

3) 최대 이동한 거리 = 버블 정렬의 마지막 회차

따라서 코드는 다음과 같다.

import sys
input = sys.stdin.readline

N = int(input())
A = []
for i in range(N):
    A.append((int(input()),i))
sorted_A = sorted(A)
answer=[]
for i in range(N):
    answer.append(sorted_A[i][1] - A[i][1])
print(max(answer) + 1)

 

 

 

3. 선택 정렬

최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

(최솟(최댓) 값 정렬 -> 나머지 부분에서 최솟(최댓) 값 정렬 -> 반복 : n*(n-1)*...*1 = n²)

시간복잡도 : O(n²)

 

 

4. 선택 정렬 실전 문제

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

풀이코드

N = list(map(int,input()))

for i in range(len(N)):
    t = N[i:].index(max(N[i:])) +i #문제의 부분
    N[i],N[t] = N[t] , N[i]
for i in range(len(N)):
    print(N[i],end='')

처음엔 t = N.index(max(N[i:])) 였고 에러가 났다. 왜인지 하나하나 값을 넣어가며 확인해 봤더니 max(N[i:])의 값을 N전체에서 찾는다는 것을 간과하고 있었다. 또한 t로 변수를 따로 안 주면 리스트의 순서 바꾸기가 안된다. 그 이유는 나중에 찾아봐야겠다. sort로 풀면 간단한 문제지만 선택정렬로 풀어 먼 길을 돌아온 느낌이다. 하지만 풀면서 몰랐던 사실을 알게 되어 기쁘다.

 

 

5. 삽입 정렬

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식

시간복잡도 : O(n²) , O(log N)

 

 

6. 삽입 정렬 실전 문제

https://www.acmicpc.net/problem/11399

11399번: ATM

 

풀이코드

N = int(input())
P = list(map(int,input().split()))
answer_list=[]
answer=0
for i in range(N):
    answer_list.append(P.pop(P.index(min(P))))
for i in range(len(answer_list)):
    answer += sum(answer_list[:i+1])
print(answer)

 

사실 삽입정렬을 의식하며 풀었는데 풀고 보니 선택정렬이 되었다. 강의를 보고 삽입정렬로 푼 코드를 이해는 했으나 다시 비슷한 문제를 만나도 선택정렬이나 sorted() 함수를 쓸 것 같다. (시간복잡도에 큰 차이도 없고 간단하기 때문)