스파르타코딩클럽 알고리즘 강의

정렬

데이터를 순서대로 나열하는 방법.

버블 정렬

가장 쉽고 직관적인 정렬.
방법:
1. 배열의 처음부터 끝까지 반복
2. 현재값과 다음값을 비교했을 때 정렬이 되어있지 않다면 두 값 교환

def bubblesort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    iters = len(lst) - 1
    for iter in range(iters):
        # 이미 구한 최댓값은 범위에서 제외한다.
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

선택 정렬

선택해서 정렬하는 방식.
1. 배열의 처음부터 끝까지 반복
2. 최솟값을 찾아서 i번째와 교환

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

삽입 정렬

전체에서 하나씩 올바른 위치에 삽입하는 방식.

def insertionsort(lst):
    # 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst


def insertionsort_2(lst):
    for idx in range(1, len(lst)):
        val = lst[idx]
        cmp = idx - 1

        while lst[cmp] > val and cmp >= 0:
            lst[cmp + 1] = lst[cmp]
            cmp -= 1

        lst[cmp + 1] = val

    return lst

퀵 정렬

분할 정복을 통해 정렬.
1. 기준 설정 (마지막 요소)
2. 기준과 비교해서 작은 집합과 큰 집합으로 나눔
3. 집합들 사이에 기준 삽입
4. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤 결과 합치기

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)
    return lst

병합 정렬

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result
    
def mergesort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    L = lst[:mid]
    R = lst[mid:]
    return merge(mergesort(L), mergesort(R))

힙 정렬

1. 기존에 구현했던 BinaryMaxHeap을 이용해 힙의 구조로 저장.
2. 힙의 요소들을 역순으로 추출하여 리스트에 저장. (BinaryMinHeap 이용 시 필요 x)

def sorted_by_heap(lst):
    maxheap = BinaryMaxHeap()
    for elem in lst:
        maxheap.insert(elem)

    desc = [maxheap.extract() for _ in range(len(lst))]
    return list(reversed(desc))

페어 프로그래밍

문제풀이

1. 가장 긴 증가하는 부분 수열

구현 방법을 직접 생각하는건 어려웠지만 페어들의 설명을 듣고 바로 이해할 수 있었다.

풀이

A: 입력값들의 리스트
B: 가장 긴 증가하는 부분 수열을 담을 리스트 ([0])
D: A의 i번째 요소를 삽입할 B의 위치

1. N만큼 반복문
   1-1. 만약 A의 i번째 요소가 B의 마지막 요소보다 크다면 무조건 A[i]를 B에 추가.
   1-2. 아니면 B를 반복하면서 A[i]와 같거나 큰 값이 나오면 해당 인덱스에 A[i]를 저장.
   

전체 코드

N = int(input())

A = list(map(int, input().split()))[:N]
B = [0]

for i in range(N):
    if A[i] > B[-1]:
        B.append(A[i])
    else:
        for j in range(len(B)):
            if B[j] >= A[i]:
                B[j] = A[i]
                break

print(len(B)-1)

2. 계단 오르기

오늘 문제 중 제일 이해하기 어려웠던 문제다.
조건:
1. 이동은 다음 계단 or 다음 다음 계단
2. 세 계단 연속 밟기 안됨
3. 마지막 계단은 반드시 밟아야 함

풀이

N: 계단의 개수
stairs: 계단 별 점수 리스트
max_value: 최대 합 리스트

1. N이 2 이하인 경우 최대 합은 계단 점수의 합
2. N이 3 인 경우 [0]+[2]와 [1]+[2] 중 큰 값을 max_value에 저장
3. N이 3보다 큰 경우:
   3-1. s[i] + s[i-1] + max[i-3]
   (3칸 연속으로는 갈 수 없기 때문에 현재값 + 이전값 + 3개 전 최대값)
   3-2. s[i] + m[i-2]
   (3칸 연속으로 갈 수 없기 때문에 현재값 + 2개 전 최대값)
4. 3-1, 3-2 중 더 큰 값을 max_value에 저장

전체 코드

N = int(input())

stairs = []
max_value = []

for i in range(N):
    stairs.append(int(input()))

max_value.append(stairs[0])
if N >= 2:
    max_value.append(stairs[0]+stairs[1])
    if N > 3:
        max_value.append(max(stairs[0]+stairs[2],stairs[1]+stairs[2]))
        for i in range(3,N):
            max_value.append(max(stairs[i] + stairs[i-1] + max_value[i-3],stairs[i] + max_value[i-2]))
print(max_value[-1])

3. 신나는 함수 실행

오늘 문제 중 그나마 무난했던 문제다.
5주차 강의에서 동적 계획법 기법을 설명할 때 피보나치 수열을 구하는 함수를 예로 들었는데 그 방법을 적용해서 구현해보았다.

풀이

memo: a,b,c 입력들에 대한 함수 호출 값을 저장하는 21x21x21 크기의 리스트

1. memo의 모든 요소를 0으로 초기화
2. 문제에서 제공하는 w 함수에서 몇가지 수정
   2-1. 3번째 if문 추가: a,b,c에 대한 값이 이미 memo에 저장되어있다면 해당 값 바로 반환
   2-2. 4번째 if문과 마지막 두 줄: 함수 호출 값을 memo[a][b][c]에 저장 후 해당 값 바로 반환

• 피보나치 수열의 원리와 같이 w함수를 memo 없이 재귀적으로 호출하면 이미 한 번 연산했던 작업을 반복해서 연산해야 한다.
• 하지만 이미 한 번 연산했던 값을 memo에 따로 저장해줌으로써 동일한 연산이 반복되는 것을 막을 수 있다.

전체 코드

memo = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]

def w(a, b, c):

    if a <= 0 or b <= 0 or c <= 0:
        return 1
    
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    if memo[a][b][c] != 0:
        return memo[a][b][c]
        
    if a < b and b < c:
        memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return memo[a][b][c]
    
    memo[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    return memo[a][b][c]

a, b, c = 0, 0, 0
ans = 0
while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    print(f'w({a}, {b}, {c}) = {w(a, b, c)}')