알고리즘 코딩테스트 - 정렬(버블, 선택, 삽입)

각 정렬의 핵심이론과 관련 백준 문제를 정리해보았습니다 😍

 

1. 버블정렬 핵심이론

• 시간복잡도 : O(n2) 
• 원리 시각화

• 바로 옆의 데이터와 비교해서, swap 조건에 부합하면 swap함
• 이러한 비교를 거쳐서, 오름차순일 경우 가장 큰 수가 오른쪽, 내림차순일 경우 가장 큰 수가 왼쪽에 위치하게 됨
• no swap 만 일어남 ? : 모두 정렬이 되었다는 의미

 

---

백준 문제로 버블 정렬 코드 짜보기 !! 🍀

 

백준 2750 : 버블정렬

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

2750번: 수 정렬하기

 

sort 함수를 이용하여 쉽게 풀 수 있지만, 버블정렬 단원이기 때문에, 버블정렬 개념을 이용하여 풀이하려고 합니다 !

• 버블정렬은 인접요소끼리 비교하고, 정렬이 필요하다면 swap을 해줌
• 버블정렬을 통해 루프를 하나씩 돌때마다, 가장 큰 수는 제일 오른쪽에 정렬이 됨
• 따라서, 두번째 for 문에서 n-1-i를 해주는 것임 (여기서 i는 몇 번째 루프인가 ? 를 뜻함)

 

# 백준 2750번
import sys
input = sys.stdin.readline

#입력받기
n = int(input())
a = list()
for i in range(n) :
    a.append(int(input()))

for i in range (n-1) :
    for j in range (n-1-i) :
        if a[j] > a[j+1] :
            temp = a[j]
            a[j] = a[j+1]
            a[j+1] = temp

for i in range(n) :
    print(a[i])

 

---

2. 선택정렬 핵심이론

• 시간복잡도 : O(n2) 
• 원리 시각화 : 말 그대로 정렬하는 숫자를 "선택" 하는 정렬법임

• 오름차순으로 정렬할 경우 최솟값을, 내림차순으로 정렬할 경우 최댓값을 찾음
• 찾은 데이터와 가장 앞에 있는 데이터를 swap 시켜줌 -> 선택된 데이터는 정렬이 되어짐
• 남은 데이터를 위와 같은 방법으로 반복 (swap이 일어나지 않을 때까지)

 

---

백준 문제로 선택정렬 코드 짜보기 !! 🍀

 

백준 1427 : 선택정렬

 

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

1427번: 소트인사이드

 

선택정렬을 이용하는 문제! 코딩테스트에서는 잘 안나온다고 합니다. 그러나, 문제 속에 사용될 수 있기 때문에 알고가야하는 개념입니다 !

• 내림차순으로 정렬하는 문제는 "최댓값" 찾기, 오름차순으로 정렬하는 문제는 "최솟값" 찾기
• 최댓값을 찾고, 가장 앞 부분에 있는 데이터와 swap 해줌 ( 선택정렬의 개념)
• 루프 하나를 돌 때마다, 제일 앞 부분의 값이 고정됨
• 예제 출력 값을 보면, 줄바꿈해서 출력하지 않음. 따라서, 아래의 코드를 사용해줍니다 !

print = sys.stdout.write

 

 

# 백준 2750번
import sys
print = sys.stdout.write #줄바꿈출력 안하도록
input = sys.stdin.readline

# 입력받기
a = list(input())

for i in range(len(a)-1) :
    max = i
    for j in range(i+1, len(a)) :
        if a[j] > a[max] :
            max = j

    if a[i] < a[max] :
        temp = a[i]
        a[i] = a[max]
        a[max] = temp

for i in range(len(a)-1) :
    print(a[i])

 

 

 

---

 

3. 삽입정렬 핵심이론

• 시간복잡도 : O(n2) 
• 원리 시각화 : 말 그대로, 현재 데이터를 적절한 위치에 "삽입" 하는 정렬 방법임

• 두번째 데이터부터 선택하여, 삽입될 위치를 탐색함
• 삽입 위치로 선택된 데이터를 옮겨주고, 삽입위치부터 현 위치 (index위치)까지 shift 연산을 수행해줌 (즉, 한 칸씩 옆으로 이동해준다) -> 이것이 시간복잡도가 O(n2) 나오는 이유임
• 선택할 데이터가 없을 때까지 위의 과정을 반복해줌
• 추가로 4번째 데이터 경우, 5보다 큰 값이 없으므로 현재 자리가 적절함. 따라서 이동이 없음

 

---

 

백준 문제로 삽입정렬 코드 짜보기 !! 🍀

 

백준 11399 : ATM인출 시간 계산하기

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

11399번: ATM

 

 

 

# 백준 11399번
import sys
n = int(input())
a = list(map(int,input().split()))
s = [0] * n #합배열

for i in range(n) :
    insert_point = i
    insert_value = a[i]
    for j in range(i-1, -1, -1) : #뒤에서부터 출력해주기
        if a[j] < a[i] :
            insert_point = j+1
            break

        if j == 0 :  #끝까지 탐색하는 경우
            insert_point = 0


    for j in range(i,insert_point, -1):
        a[j] = a[j-1]

    a[insert_point] = insert_value


s[0] = a[0]
sum = 0

for i in range(1, n) :
    s[i] = s[i-1] + a[i]
    sum += s[i]

print(sum)

 

 

* do it 알고리즘 코딩테스트 내용을 참고하였습니다.