1차원 배열

버블 정렬

: 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동

def bubbleSort():
    for i in range(N-1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [0, 4, 6, 1, 3, 2, 5]
N = len(arr)

 

 

 

 

카운팅 정렬
: 항목들의 순서를 결정하기 위해 각 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여 선형시간에 정렬하는 효율적인 알고리즘

1. 데이터에서 각 항목들의 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열에 저장
2. 카운트 배열의 누적합 구하기
3. 뒤에서부터 해당 인덱스의 원소를 새로운 배열에 저장

def countingSort():
    C = [0] * N
    result = [0] * N

    # 원소 개수 카운팅하기
    for i in arr:
        C[i] += 1

    # 누적합 구하기
    for i in range(1, len(C)):
        C[i] += C[i-1]

    # 새로운 배열에 차례로 정렬
    for i in range(len(C)-1, -1, -1):
        C[arr[i]] -= 1
        result[C[arr[i]]] = arr[i]

    return result

arr = [0, 4, 6, 1, 3, 2, 5]
N = len(arr)

 

탐욕 알고리즘
: 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도출

연습문제) Baby Gin!
-> 6장의 카드 중 연속하는 숫자로 이루어진 3장의 카드 : run
-> 6장의 카드 중 같은 3장의 카드 : triplet

Baby Gin은 run과 triplet으로만 이루어진 조합을 말한다.

num = 456789
# i + 2번째 까지의 원소를 조회하기 위해서 2만큼 더 긴 길이의 배열 사용
C = [0] * 12

for i in range(6):
    C[num % 10] += 1
    num = num // 10

tri = run = 0
i = 0
while i < 10:
    # triple 제거
    if C[i] >= 3:
        C[i] -= 3
        tri += 1
        continue
    # run 제거
    if C[i] >= 1 and C[i+1] >= 1 and C[i+2] >= 1:
        C[i] -= 1
        C[i+1] -= 1
        C[i+2] -= 1
        run += 1
        continue
    i += 1

if run + tri == 2:
    print('Baby Gin')
else:
    print('Lose')