알고리즘 강의 3일차: 스택(push, pop, peek), 큐(enqueue, dequeue, peek), 정렬(버블, 선택, 삽입)

오늘은 강의보다는 연습문제를 풀이하는데에 집중을 더 많이 했다.

그래도 배운 내용을 정리하면, 스택이랑 큐를 배운 다음 정렬을 배웠다.

스택은 LIFO로, 한쪽 끝으로만 자료를 넣고 뺄 수 있다.

top에 데이터 넣을 때 push(), top에 데이터 추출하고 없애기는 pop(), top의 데이터 조회는 peek()

큐는 FIFO로, 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있다. self.head와 self.tail로 구성되어 있다.

rear에 데이터 넣을 때 enqueue(), front에 데이터 추출하고 없애기는 dequeue(), front에 데이터 조회는 peek()

아직 앞과 뒤, top과 rear가 헷갈린다...

 

오늘 배운 정렬은 버블정렬, 선택정렬, 삽입정렬. 각각의 코드는 다음과 같다.

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    n = len(array) # array의 길이를 n에 저장해요! 루프 카운트 변수로 쓰겠죠?
    for i in range(n): # 이건 array를 순차적으로 돌겠다는 뜻이구요!
        # 이건 버블정렬 알고리즘의 특성처럼 1개씩 줄어들면서 반복하며 비교를 해요. 
        for j in range(n - i - 1):
            if array[j] > array[j + 1]: # 앞의 원소가 뒤의 원소보다 크면 바꿔야겠죠?
                array[j], array[j + 1] = array[j + 1], array[j]
                     
    return array

bubble_sort(input)
print(input)

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))


def selection_sort(array):
    n = len(array)
    for i in range(n - 1): # 이번에는 i ~ n - 2까지 돌면서 실험군을 선택해요!
        min_index = i # i번째에 들어갈 최소값을 찾아요!
        for j in range(n - i): # j ~ n - 2까지 돌면서 대조군을 선택해요!
            # 현재 최소값으로 설정된 친구보다 더 작은 친구를 발견하면!
            if array[i + j] < array[min_index]:
                min_index = i + j # 최소값 인덱스를 갱신합니다!
        # 루프를 한 번 돌면 최소값 선정 1번이 끝난거에요!
        # 인덱스 i에 위치할 친구의 인덱스 min_index에 위치한 친구를 i 인덱스로 보내고
        # 원래 인덱스 i에 위치한 친구는 min_index 인덱스로 보냅니다! swap!
        array[i], array[min_index] = array[min_index], array[i]
    return array


selection_sort(input)
print(input)

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))


def insertion_sort(array):
    n = len(array)
    # 삽입 정렬의 0번째 인덱스는 정렬된 상태라고 판단하므로 인덱스가 1부터 시작해요!
    for i in range(1, n):
        # 현재 index 범위 내에서 비교를 시작하죠! 비교 방향은 끝에서부터 시작해요!
        for j in range(i):
            if array[i - j - 1] > array[i - j]: # 뒤의 값보다 앞의 값이 크면 바꿔줘요!
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else: # 아니면 정렬된 상태이기 때문에 이번 루프는 바로 나가도 되어요!
                break
    return array

insertion_sort(input)
print(input)

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))