(파이썬 다시 보기)파이썬, python: 6. 알고리즘

목차

 

1. 알고리즘 복잡도

1-1. Big O (빅-오) 표기법: O(N)

- 가장 많이/일반적으로 사용하는 방법으로 알고리즘 최악의 실행 시간을 표기한다.

 

2. 정렬

- 버블 정렬: 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

- 삽입정렬: 두 번째 인덱스부터 시작하여 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사하고 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

- 선택 정렬: 먼저 주어진 데이터 중, 최소값을 찾고 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한 후 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

- 병합 정렬: 재귀용법을 활용한 정렬 알고리즘으로, 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나누고 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한  후 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

- 퀵 정렬: 피벗(pivot)이라고 부르는 기준점을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성하고 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함

 

sample_lst = [5, 3, 2, 4, 1]

# sort(): 정렬 후 저장
sample_lst.sort()
sample_lst
>>> [1, 2, 3, 4, 5]

# sorted(): 정렬 후 반환, 저장하진 않음
sorted(sample_lst)
>>> [1, 2, 3, 4, 5]

 

3. 탐색

- 순차 탐색: 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

- 이진 탐색: 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

- 깊이 우선 탐색(DFS): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
- 너비 우선 탐색(BFS): 정점의 자식들을 먼저 탐색하는 방식

 

3-1. 이진 탐색 예제

target = int(input())
n_list = [1,2,3,4,5]

start_idx = 0
end_idx = len(n_list) - 1

# 찾으려는 값이 있는idx를 도출, -1 반환
result = None
while start_idx <= end_idx:
    mid_idx = (start_idx + end_idx) // 2
    if target == n_list[mid_idx]:
        result = mid_idx
        break
    else:
        if target > n_list[mid_idx]:
            start_idx = mid_idx + 1
        elif target < n_list[mid_idx]:
            end_idx = mid_idx -1

if not result:
    result = -1
print(result)