Python6 [정렬] 삽입정렬(Insertion Sort) 특징 구현이 간단하다 제자리 정렬이다 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 기본 아이디어 i는 1부터 시작하여 n-1까지 늘려간다. array[0]부터 array[i-1]까지 정렬되어 있을 때, array[i]를 포함하여 정렬한다. array[i]를 뒤에서부터 순차적으로 array[i-1], array[i-2] ... 과 비교하다가 자기보다 작은 숫자가 나오면 그 뒤에 삽입한다. 아래 영상 참고 www.youtube.com/watch?v=OGzPmgsI-pQ 비교연산은 1 + 2 + 3 + ... + (n-1) 회 일어나고, 스왑 연산의 횟수도 비교 연산과 같으므로 시간 복잡도는 O(n^2) 파이썬 코드 def insertion_sort(array): for i in range(1, l.. 2021. 3. 28. [정렬] 선택정렬 (Selection Sort) 특징 가장 기본적인 정렬 알고리즘이며 구현이 쉽다. 제자리 정렬 알고리즘이다. 불안정 정렬 알고리즘이다. 시간 복잡도가 O(n^2)으로 상당히 느리다. 기본 아이디어 배열을 순회하며 최소값을 찾는다. 최소값을 찾으면 배열의 가장 첫 인덱스에 있는 값과 자리를 바꾼다. (최대값을 찾을 수도 있다. 이때는 가장 뒤에 있는 값과 자리를 바꾼다.) 다시 배열을 순회하며 다음 최소값을 찾는다. 최소값을 찾으면 두 번째 인덱스에 있는 값과 자리를 바꾼다. 원소가 하나 남을 때까지 위 과정을 반복한다. 원소가 들어갈 자리는 이미 정해져 있고, 그 자리에 넣을 원소를선택하는 알고리즘 의사 코드 Algorithm selection_sort(array) input: array output: sorted array for .. 2021. 3. 26. [정렬] 버블정렬 (Bubble Sort) 특징 구현이 쉽다. 제자리 정렬이다. 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 스왑 연산이 많이 일어나기 때문에 굉장히 비효율적이다. 기본 아이디어 배열을 순회하면서 서로 인접한 두 원소를 비교한다. 만약 더 큰 원소가 앞쪽에 있다면 두 원소의 자리를 바꾼다(오름차순 기준). 만약 마지막까지 도달했는데 스왑이 한번도 일어나지 않았다면, 모든 원소가 정렬 상태에 도달한 것으로 판단할 수 있다. 이때는 연산이 끝나지 않았음에도 강제로 연산을 종료함으로써 수행시간을 조금 더 줄일 수 있다. 의사코드 Algorithm bubble_sort(array) input: array output: void n = length of array for i = n-1 to 2 by -1 do sorted = T.. 2021. 3. 11. [자료구조] 파이썬으로 단일연결리스트 구현하기 단일연결리스트 동적 배열의 단점 동적 배열은 연속된 메모리 공간에 값을 할당한다. 파이썬의 리스트는 값을 직접 저장하지 않고 해당하는 객체의 주소를 저장하는 레퍼런스 배열이기 때문에 다른 언어의 배열과는 약간 다르다. 동적 배열은 먼저 크기를 할당해 메모리 공간을 미리 확보해놓고 이후에 값을 저장하기 때문에 대부분의 경우 저장하는 요소의 수가 배열의 길이보다 작다. append 연산은 분할 분석 방식으로는 O(1) 의 시간복잡도를 가지지만 실제로는 배열이 가득 찼을 때 resize 연산을 하면서 O(n) 의 시간복잡도를 가진다. 즉 특정 시점(배열이 가득 찼을 때)에 연산 속도가 갑자기 느려진다. 이는 실시간 시스템에서는 문제를 유발할 수 있다. 동적 배열의 단점을 정리하면 아래와 같다. 동적 배열의 길.. 2020. 11. 8. [자료구조] 파이썬으로 큐(Queue) 구현하기 큐(Queue) 큐는 한쪽 끝에서 자료를 추가하고 한쪽 끝에서 자료를 꺼내는 선형 자료 구조로 가장 먼저 들어온 자료가 가장 먼저 나가는 FIFO(First In First Out) 방식입니다. 롤에서 랭크 게임을 매칭할 때 "큐를 돌린다"라고 표현하죠. 게임 시작 버튼을 먼저 누른 사람이 먼저 게임을 할 수 있도록 처리해줍니다. 큐는 이처럼 요청이 들어온 순서대로 일을 처리할 때 사용합니다. 큐의 동작 방식 큐가 동작하는 방식을 알아봅시다. 크기가 5인 큐를 만듭니다. Queue = [None, None, None, None, None] 우선 큐는 가장 먼저 들어온 데이터를 가리키는 front 변수와 가장 나중에 들어온 데이터의 위치를 가리키는 back 변수가 필요합니다. 처음에는 큐가 비어있으므로 f.. 2020. 11. 6. [자료구조] 파이썬으로 스택(Stack) 구현하기 스택(Stack) 스택은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조입니다. 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out)방식을 사용합니다. 웹브라우저의 뒤로가기나 편집기의 되돌리기(undo) 기능이 이런 방식을 이용합니다. 사실 파이썬의 리스트는 스택이 가져야할 메서드를 이미 가지고 있습니다. 따라서 스택 자료형을 따로 만들 필요는 없습니다. 하지만 그냥 공부한다는 생각으로 간단하게 스택 자료형을 만들어봅시다. 기본적으로 아래의 네 가지 연산이 필요합니다. S.push(e): Top에 새로운 요소를 추가 S.pop(): Top 요소를 반환하면서 제거 S.top(): Top 요소를 제거하지 않고 반환 S.is_empty(): 스택이 비어있으면 Tru.. 2020. 11. 6. 이전 1 다음
