[데이터 취업 스쿨 스터디 노트] 알고리즘 1 - 4

 

---

 

선형검색

: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.

보초법 : 마지막 인덱스에 찾으려는 값을 추가, 찾는 과정을 간략화한다.

 

이진검색

: 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.

 

순위

: 수의 크고 작음을 이용해서 수의 순서를 정하는 것

 

버블정렬

: 인접한 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 끝으로 옮기는 알고리즘

array = [2, 5, 4, 3, 1, 8, 7, 6, 9]


def bubble_sort(array):
    # 9
    n = len(array)
    for i in range(n - 1):
        # 0 ~ 7 / 0 ~ 6 / ...
        for j in range(n - i - 1):
            # array[0] > array[1]:
            # array[0], array[1] = array[1], array[0]
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
        print(array)


print("before: ", array)
bubble_sort(array)
print("after:", array)

 

삽입정렬

: 정렬되어 있는 자료 배열과 비교하여 정렬 위치를 찾는다.

array = [8, 4, 6, 2, 9, 1, 3, 7, 5]

def insertion_sort(array):
    n = len(array)
    # 1 ~ 8
    for i in range(1, n):
        # 1, 0, -1
        for j in range(i, 0, -1):
            # array[1] > array[2]:
            # array[0], array[1] = array[1], array[0]
            if array[j - 1] > array[j]:
                array[j - 1], array[j] = array[j], array[j - 1]
        print(array[: i + 1])


print("before: ", array)
insertion_sort(array)
print("after:", array)

 

선택정렬

: 리스트 중 최소값을 찾아 0번 인덱스 자리에 위치한 값과 교체하는 방식으로 정렬한다.

array = [8, 4, 6, 2, 9, 1, 3, 7, 5]

def selection_sort(array):
    # 9
    n = len(array)
    # 0 ~ 8
    for i in range(n):
        min_index = i
        # 0 + 1, 9 / 1 ~ 8
        for j in range(i + 1, n):
            # array[1] < array[0]:
            # min_index = 1
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
        print(array[: i + 1])


print("before: ", array)
selection_sort(array)
print("after:", array)

 

최댓값 / 최솟값

: 자료구조에서 가장 큰 값 / 작은 값을 찾는다.

 

최빈값

: 데이터에서 빈도 수가 가장 많은 데이터

 

---

내일의 학습 목표

알고리즘 5 - 7