Dev

[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리

파이썬으로 코딩테스트를 진행하며 가장 많이 쓰는 기본 자료형은 리스트(list)와 문자열(string), 딕셔너리(dictionary), 집합(set) 정도이다. 기본 자료형을 벗어난 것 중 많이 쓰는 것은 collections 모듈의 Counter와 deque 정도가 있겠고, 아주 가끔 itertools 모듈의 permutations 혹은 combinations 정도를 쓰는 것 같다(사실 이 둘은 시간복잡도가 터져버리기 때문에 거의 안 쓴다). 약간 난이도가 있는 코딩테스트 문제들은 항상 시간복잡도와 공간복잡도에 대한 제약이 주어진다. 특히 시간복잡도에 대한 제약은 아주 중요하며, 이를 고려하기 위해서는 이용하는 자료형의 메소드 별 시간 복잡도를 알고 있어야 한다. 그래서 이번 기회에 정리를 해볼까 한..

[자료구조][파이썬/Python] 덱 (Deque)

덱(Deque, Double Ended Queue) 덱(Dequeue)은 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 덱은 스택(Stack)과 큐(Queue)의 연산을 모두 지원하는 자료구조로, 양 끝에서 모두 삽입과 삭제가 가능한 큐라고 생각하면 된다. 나머지 부가적인 덱의 길이를 반환하는 연산이나 덱이 비어있는지 확인하는 연산 등은 스택과 큐에 구현되어 있는 연산들과 유사하게 구현된다. Python의 모듈을 이용하기 큐를 설명할 때 언급했지만 collections라는 모듈에 deque라는 클래스로 이미 구현되어 있다. 여기서 특별한 점은 양 끝에서 삽입과 삭제를 할 수 있어야 하므로 양방향 연결리스트(Doubly Linked List)로 구성되어 있다. 단순히 값을 삽입하고 삭..

[알고리즘][파이썬/Python] 퀵 정렬 (Quick Sort)

정의 기준 값을 중심으로 작은 원소들은 왼쪽 부분집합으로, 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방식의 정렬 알고리즘 * 퀵 정렬도 분할과 정복(divide and conquer) 기법을 이용하는 정렬 알고리즘이다. 하지만 병합 정렬과 차이가 있는데, 병합 정렬이 분할 후 정복하는 원리였다면, 퀵 정렬은 정복 후 분할하는 원리의 정렬 알고리즘이다. 우선 기준 값보다 작은 원소들을 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 구분하는 정복 절차를 밟고, 기준 값을 중심으로 2개의 부분 집합으로 분할한다. 동작 방식 0. 기준 값을 보통 피벗(pivot)이라고 부르며, 선택하는 기준은 다양하겠으나 일반적으로 가장 왼쪽 원소를 피벗으로 지정한다. 본 글에서도 가장 왼쪽 원소를 ..

[알고리즘][파이썬/Python] 병합 정렬 (Merge Sort)

정의 입력 자료를 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 다음에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법 중 하나로, 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식의 정렬 알고리즘 동작 방식 (2-way 병합, 오름차순 정렬 기준) 0. 일반적으로 정렬한 상태의 자료를 담기 위해 입력 자료의 크기만큼의 새로운 배열(리스트)을 선언해줌. 그러나 해당 포스팅에 기재한 소스코드는 정렬한 원소를 새로운 리스트에 담지 않고 입력값인 기존의 리스트를 재사용했음. 동작 방식에 대한 설명은 새로운 리스트를 선언했다고 가정한 채 진행. 1. 입력 자료를 두 개의 부분집합으로..

[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)

정의 - 일정 간격(interval) 떨어져 있는 원소들끼리 부분집합을 구성한 후 각 부분집합의 원소들에 대해서 삽입 정렬을 수행하되, 간격을 줄여가며 삽입 정렬을 반복하여 전체 원소들을 정렬하는 방식의 정렬 알고리즘 * 쉘 정렬은 삽입 정렬의 문제점을 극복하기 위해 개선한 정렬 알고리즘이다. 삽입 정렬의 경우, 주어진 자료의 정렬 상태에 따라 시간 복잡도가 많이 달라졌는데, 역순으로 정렬되어 있는 형태에 가까울수록 비교횟수가 아주 많이 늘어나는 치명적인 문제점이 존재했다. 그래서 Donald L. Shell 은 '간격(interval)'이라는 개념을 도입하여 위 언급한 문제점을 극복해내는 '쉘 정렬'을 고안해냈다. 동작 방식 0. 간격(interval) h = 정렬할 배열(혹은 리스트)의 길이 % 2 ..

[알고리즘][파이썬/Python] 삽입 정렬 (Insertion Sort)

정의 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식의 정렬 알고리즘 동작 방식 0. 정렬할 배열(혹은 리스트)은 두 개의 부분집합 S와 U로 구분 * S (Sorted) : 정렬된 앞부분의 원소들 * U (Unsorted) : 아직 정렬되지 않은 나머지 원소들 1. U의 가장 앞에 있는 원소를 꺼내어 S의 마지막 원소부터 첫 번째 원소까지 대소 비교하며, S 내에 적절하게 삽입될 위치를 탐색 2. 대소 비교가 끝나면, U에서 꺼낸 원소를 탐색한 위치에 삽입 3. 그 결과, S의 원소는 하나 증가하며 U의 원소는 하나 감소 4. U가 공집합이 될 때까지 위 과정을 반복하며 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Ca..

[알고리즘][파이썬/Python] 선택 정렬 (Selection Sort)

정의 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 반복 시작 시, 시작 index를 최소값의 index로 지정 2. 시작 위치 이후에 있는 모든 원소를 한 번씩 방문하며 최소값과 비교 3. 더 작은 값이 발견될 경우, 해당 값의 index를 최소값의 index로 업데이트 4. 반복이 끝난 후 시작 index와 최소값 index가 다를 경우, 두 index에 위치한 원소들을 교환 5. 위 과정을 반복하면서 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : 처음 비교할 때 (n-1)회, 두 번째 비교할 때 (n-2)회, ..., i..

[알고리즘][파이썬/Python] 버블 정렬 (Bubble Sort)

정의 차례로 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 배열(혹은 리스트)의 첫 번째 원소부터 마지막 원소까지 인접 원소 간 대소 비교를 반복하는데, 더 큰 값을 가진 원소가 왼쪽에 있다면 서로 자리를 바꿈 (swap) 2. 위 과정을 반복하여 한 단계가 끝나면 가장 큰 값을 가진 원소가 배열 (혹은 리스트)의 마지막 자리로 정렬되어 있음 3. 한 단계가 끝날 때마다 맨 끝에 위치한 원소는 정렬된 상태이므로 다음 단계에서는 정렬된 원소를 제외하고 대소 비교를 실행 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : i번째 실행 시 (n-i) 번 비교하므로..