04-1. 버블 정렬

• 버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.
• 간단하게 구현 할 순 있지만, 시간 복잡도는 $O(n^2)$ 으로 다른 정렬 알고리즘보다 느린 편이다.
• 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.

문제 15

수 정렬하기 1 ( 백준 브론즈 2 / 2750번 )

파이썬에서는 sort() 함수를 사용하면 쉽게 정렬이 되지만 여기서는 직접 구현해 문제를 풀어보겠다.

1. 먼저 n개를 받아 몇개를 정렬할 것인지 받는다.
2. 리스트 A에 입력데이터를 저장
3. 이중 for문을 사용하여 현재 리스트의 값보다 1칸 오른쪽 리스트의 값이 더 작으면 두 수의 자리를 바꾸어 준다.

A = [int(input()) for _ in range(N)]를 사용하여 반복문을 사용하지 않고 한번에 입력 받음

💻 코드

N = int(input())

# A = [0] * N           # 반복문으로 입력을 받을 수도 있지만 아래와 같이 한번에 입력을 받을 수 있다.
# for i in range(N):    
#     A[i] = int(input())

A = [int(input()) for _ in range(N)] 

for i in range(N-1):    # N개의 수를 두개씩 비교하면 N-1번 반복하게 됨
    for j in range(N-1-i):  # 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])

---

문제 16

버블 정렬 프로그램 1 ( 백준 골드 2 / 1377번 )

이 문제는 버블 정렬의 swap이 일어나지 않은 개수를 세는 문제이다. 하지만 이 문제를 버블 정렬로 문제를 풀면 N의 최대 범위가 5000,000이므로 시간 초과가 발생한다. 따라서 안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어가 필요하다.

안쪽 for 문이 몇 번 수행 됐는지 구하는 다른 아이디어

• 안쪽 루프는 1에서 n - j (책에서는 n - j 라고 나와있는데 내 생각은 n - i 인 것 같다) 까지 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다.
• 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가
  1 이라는 뜻이다. 즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 시간 초과없이 풀 수 있다.

따라서 정렬 전 index - 정렬 후 index 값 중 최대값을 찾아 왼쪽으로 몇 칸 이동 했는지 구할 수 있다. 그리고 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안하여 최대값에 1을 더한다.

처음 알게된 사실

sort()와 sorted()의 차이

• sort()는 A.sort() 와 같이 원본 A를 정렬 시킨다.
• sorted()는 변수 = sorted(A) 처럼 변수에 정렬 된 리스트를 저장하고 A는 원본 리스트를 계속 가지고 있다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
A =[]

for i in range(N):
    A.append((int(input()), i))  # 인덱스 순서를 알기 위해 인덱스 값과 리스트 값 동시 입력 받음

no_sort = 0
sorted_A = sorted(A)    # sort()와 sorted() 차이가 있다.

for i in range(N):
    if no_sort < sorted_A[i][1] - i:    # 정렬 전 index - 정렬 후 index 계산의 최댓값 저장
        no_sort = sorted_A[i][1] - i

print(no_sort + 1)  # 정렬이 다 완료 된 후 한번 더 for문을 돌기 때문에 1을 더해줌

---

04-2. 선택 정렬

• 선택 정렬은 대상 데이터에서 최대나 최소 데이터를 찾아 정렬하는 방법이다.
• 선택 정렬은 구현 방법이 복잡하고 시간 복잡도도 $O(n^2)$으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다.

선택 정렬 과정

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

문제 17

내림차순으로 자릿수 정렬하기 ( 백준 실버 5 / 1427번 )

• 먼저 input 데이터를 list 변환하여 값을 받는다. 각 자리수 별로 리스트화를 시킬 수 있다.
• 내림차순 정렬을 해야 하므로 최댓값을 찾아 맨 앞 자리와 swap하여 반복한다.

💻 코드

import sys
input = sys.stdin.readline
print = sys.stdout.write

A = list(input())

for i in range(len(A)):
    Max = i     # Max 변수에 첫번째 i 값 임시로 넣음
    for j in range(i+1, len(A)):    # i값 다음의 값부터 비교
        if A[j] > A[Max]:   # j값이 Max값보다 크다면
            Max = j
    if A[i] < A[Max]:       # Max 값을 맨 처음 i값으로 정렬 시켜주는 작업
        temp = A[i]
        A[i] = A[Max]
        A[Max] = temp

for i in range(len(A)):
    print(A[i])

---

04-3. 삽입 정렬

• 삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.
• 시간 복잡도는 $O(n^2)$으로 느린 편이다.

삽입 정렬 과정

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

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

문제 18

ATM 인출 시간 계산하기 ( 백준 실버 4 / 11399번 )

이 문제는 ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 맨 앞에 올수록 시간의 합이 가장 작게 된다.
N의 최댓값이 1,000이고 시간 제한이 1초이기 때문에 시간 복잡도 $O(n^2)$ 인 알고리즘 어떤 것도 사용 가능하다.

여기서는 삽입 정렬을 사용하겠다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
S = [0] * N

for i in range(1, N):                # 0번째는 의미가 없으니 1부터 N까지 
    insert_point = i                 # 삽입 인덱스 번호 초기화
    insert_value = A[i]              # 인덱스 값 초기화
    for j in range(i-1, -1, -1):     # i-1 부터 0까지 뒤에서부터 크기 비교
        if A[j] < A[i]:
            insert_point = j + 1
            break
        if j == 0:                   # 현재 비교하는 인덱스 값이 가장 작을 때
            insert_point = 0 
    for j in range(i, insert_point, -1):    # i부터 inser_point까지 뒤에서 부터 인덱스를 한칸 밀기
        A[j] = A[j-1]
    A[insert_point] = insert_value      # 현재 인덱스 값 삽입 위치에 넣기

S[0] = A[0]     # 0번 인덱스 값은 그대로 넣기

for i in range(1, N):   # 합 배열
    S[i] = S[i-1] + A[i]

sum = 0

for i in range(0, N):   # 합 배열 총합
    sum += S[i]

print(sum)

이상으로 Do it! 알고리즘 코딩테스트 4장. 정렬 4-1, 4-2, 4-3 풀이를 마친다.