시간 복잡도

파이썬 프로그램은 1초에 2,000만 ~ 1억개의 의 연산을 수행할 수 있다.

시간복잡도 유형

1. 빅-오메가 - 최선일 때의 연산 횟수를 나타낸 표기
2. 빅-세타 - 평균일 때 연산 횟수를 나타낸 표기
3. 빅-오 - 최악일 때 연산 횟수를 나타낸 표기

빅오 표기의 시간 복잡도 유형

1. 시간복잡도는 데이터의 크기에 따라 수행시간이 다르며 비교 시 수치는 아래와 같다.

2. O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)

3. log 계산 방법

   import math
   print(math.log2(1000000)) # 19.931568569324174

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨

디버깅

정의 - 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정

디버깅 방법

1. 코드에서 디버깅 할 위치에 중단점을 설정
2. IDE의 디버깅 기능 실행

자료구조

배열과 리스트

배열 - 메모리의 연속 공간에 값이 채워져 있는 형태로 인덱스를 통해 데이터를 참조할 수 있고 선언한 자료형의 값만 저장이 가능

1. 특징
   1. 인덱스를 사용해 값에 바로 접근 가능
   2. 값을 삽입하거나 삭제하려면 인덱스 주변 값을 이동 시키는 과정이 있어 값 변경이 어렵다.(파이썬 배열의 특징은 아닌 듯)
   3. 배열의 크기는 선언 시 지정 가능하며 한번 선언 이후 크기를 늘리거나 줄일 수 없다.
   4. 구조가 간단하다.

리스트 - 값과 포인터를 묶은 노드

1. 특징
   1. 인덱스가 없어 Head 포인트부터 순서대로 접근해야 한다.(=접근 속도가 느림)
   2. 포인터로 연결되어 있어 데이터의 삽입, 삭제 연산 속도가 빠름
   3. 선언 시 크기를 별도 지정하지 않아도 되며 변동이 잦은 쉬운 데이터를 다룰 때 적절
   4. 포인터 저장 공간이 필요해 배열보다 구조가 복잡

파이썬 리스트

1. 위의 설명된 배열 + 리스트의 특징을 모두 가지고 있어 편리

구간 합

정의 - 합 배열을 이용해 시간복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘

숫자로 가득찬 리스트 A의 특정 인덱스까지의 합을 구할 때 시간 복잡도는 O(N)이지만 미리 합배열을 만들어 구해놓으면 O(1)로 시간복잡도가 변한다.

TIP : 입력 받는 부분에서 손실을 발생시키지 않으려면 아래와 같이 input 을 설정한다.

import sys 
input = sys.stdin.readline

투 포인터

정의 - 2개의 포인터로 알고리즘의 시간 복잡도를 최적화

요약 - 2개의 포인터(시작과 끝점)에서 조건을 만족시키며 하나씩 줄어들거나 늘어나며 교차할 때 까지 연산하는 방식의 알고리즘

슬라이딩 윈도우

정의 - 2개의 포인터로 범위 지정 후 범위를 유지한 채로 이동하며 문제 해결

요약 - 정해진 윈도우 크기 안에서 포인터를 움직이며 작업 수행

스택

정의 - 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조, list로 스택을 구현한다.

주로 DFS(Depth First Search)에서 사용

큐

정의 - 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조, deque 라이브러리로 큐를 구현

주로 BFS(Breadth First Search)너비 우선 탐색에서 자주 사용

비슷한 이름으로 우선순위 큐(priority queue)가 있으나 deque가 아닌 heap을 이용해 구현하며 우선 순위가 높은 데이터가 먼저 나오는 자료 구조

버블 정렬

정의 - 두 인접한 데이터의 크기를 비교해 정렬하는 방법으로 O(n**2)의 시간 복잡도를 가진다.

정렬 과정

1. 비교 연산이 필요한 루프 범위 설정
2. 인접한 데이터 값 비교
3. swap 조건에 맞는 경우 swap
4. 루프 범위가 끝날 때 까지 2,3 반복
5. 4번이 끝난 뒤 swap 조건에 맞는 최종 값이 끝에 정렬되어있기 때문에 해당 영역은 제외하고 1~5를 반복한다.

swap이 한번도 발생하지 않았다면 이미 조건에 맞게 정렬되어 있으니 정렬할 필요가 없다.

선택 정렬

정의 - 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택

시간복잡도 - O(N**2)으로 효율적이지 않아 잘 사용하지 않는다.

정렬 과정

1. 남은 정렬 부분에서 최솟값 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞의 데이터와 선택된 데이터를 swap 한다.
3. 가장 앞의 데이터(가변)와 위치를 변경해 남은 정렬 부분의 범위를 축소한다.
4. 전체 데이터 크기만큼 index가 커질 때 까지 반복한다.

삽입 정렬

정의 - 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식

시간복잡도 - O(N**2)이나 구현하기가 쉬움

정렬 과정

1. 현재 index에 있는 데이터 값을 선택한다.
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.
4. 삽입 윛에 현재 선택한 데이터를 삽입하고 index ++연산을 수행한다.
   1. 전체 데이터이ㅡ 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복

퀵 정렬

정의 - 기준값(pivot)을 정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 작업을 반복해 정렬

시간복잡도 - O(nlogn) ~ O(n**2)

시간복잡도가 pivot 선택에 따라 달라지기 때문에 자주사용은 하지 않음

정렬 과정

1. 데이터 분할에 필요한 pivot을 설정
2. pivot을 기준으로 아래의 과정을 거쳐 2개의 집합으로 분리
   1. start < pivot = start++
   2. end > pivot = end —
   3. start > pivot && end < pivot = start, end를 swap 후 start ++, end —
   4. start와 end가 만날 때 까지 a~c를 반복
   5. start와 end가 만나면 만난 지점(point)의 데이터와 pivot이 가리키는 데이터를 비교해 point < pivot = point ++ / point > pivot = point — 로 데이터 이동
3. 분리 집합에서 각각 다시 pivot을 선정
4. 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복

병합 정렬

정의 - 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘

시간복잡도 - O(nlogn)

정렬과정

1. 가장 작은 단위로 그룹을 만들어 2배씩 늘려가며 통합
2. 병합의 개념은 투포인터 개념을 이용해 그룹별 시작점을 별도로 놓고 정렬 조건에 맞춰 비교하며 저장해 하나의 그룹으로 만든다.

기수 정렬

정의 - 값을 비교하지 않는 정렬로 값을 놓고 비교할 자릿수만 정한 뒤 자릿수만 비교(숫자만 가능)

시간복잡도 - O(kn) / k = 자릿수

시간복잡도가 가장 짧은 정렬로 활용도가 높음

정렬과정

1. 10개의 큐를 이용하며 아랫자리 수 부터 큐를 이용해 순서대로 저장
2. 1에서 저장된 순서 기준으로 다음 자릿수를 비교해 큐에 저장
3. 모든 자릿수 계산이 끝난 뒤 앞에서 부터 pop

깊이 우선 탐색(DFS)

정의 - 그래프의 시작 노드에서 출발해 최대 깊이까지 탐색을 마친 후 다른 분기로 이동해 다시 탐색을 수행하는 알고리즘

시간복잡도 - O(V + E) / V = 노드 수, E = 엣지 수(간선)

특징 - 재귀 함수(스택 오버 플로우 주의), 스택

너비 우선 탐색(BFS)

정의 - 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하며 탐색하는 알고리즘

시간복잡도 - O(V + E)

특징 - Queue, 선입선출

이진 탐색

정의 - 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘

시간복잡도 - O(logN)

탐색 과정

1. 현재 데이터셋의 mid(=중앙값)을 선택
2. mid > target = mid를 기준으로 왼쪽으로 이동
3. mid < target = mid를 기준으로 오른쪽으로 이동
4. 1~3을 반복하며 mid == target일 때 탐색 종료

그리디

정의 - 현재 상태에서 취할 수 있는 선택지 중 최선의 선택을 하는 알고리즘

수행 과정

1. 해 선택 : 현 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다, 전체 문제를 해결하지 못하는 경우 1로 돌아가 다시 같은 과정을 반복한다.

---

출처 : Do it! 알고리즘 코딩 테스트 - 파이썬 편