.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
시간 복잡도별 알고리즘
•
O(1): 해시 테이블 조회, 상수 시간 연산
•
O(log n): 이진 탐색, 균형 이진 탐색 트리
•
O(n): 선형 탐색, 최대/최소값 찾기, 단일 패스 문제들
•
O(n log n): 퀵 정렬, 병합 정렬, 힙 정렬
•
O(n²): 버블 정렬, 선택 정렬, 삽입 정렬, 플로이드-워셜 알고리즘
•
O(n³): 일부 동적 계획법 문제들, 플로이드-워셜 알고리즘
•
O(2^n): 피보나치 수열(재귀), 부분집합 문제, 재귀적 배낭 문제
•
O(n!): 순열 생성, 여행하는 외판원 문제
기본 자료구조 & 메서드
1. O(1) - 상수 시간
리스트(List)와 덱(Deque)에서의 특정 연산
•
list.append(value) – 끝에 값 추가: O(1)
•
list.pop() – 끝에서 값 제거: O(1)
•
deque.append(value) – 끝에 값 추가: O(1)
•
deque.appendleft(value) – 앞에 값 추가: O(1)
•
deque.pop() – 끝에서 값 제거: O(1)
•
deque.popleft() – 앞에서 값 제거: O(1)
해시 테이블 기반 자료구조 (딕셔너리, 세트)
•
dict[key] = value – 값 할당: O(1)
•
dict.get(key) – 값 가져오기: O(1)
•
set.add(value) – 값 추가: O(1)
•
set.remove(value) – 값 제거: O(1)
•
key in dict – 키 존재 여부 확인: O(1)
•
key in set – 값 존재 여부 확인: O(1)
2. O(log n) - 로그 시간
이진 탐색 트리 및 힙
Python 표준 라이브러리에는 직접적으로 이진 탐색 트리가 구현되어 있지는 않지만, heapq 모듈로 우선순위 큐를 힙으로 사용할 수 있다.
•
heapq.heappush(heap, value) – 힙에 값 추가: O(log n)
•
heapq.heappop(heap) – 최소값 제거: O(log n)
•
heapq.heapify(list) – 리스트를 힙 구조로 변환: O(n)
3. O(n) - 선형 시간
리스트(List)
•
list.pop(i) – i번째 원소 제거: O(n) (맨 끝이 아닌 경우)
•
list.insert(i, value) – i번째 위치에 값 삽입: O(n)
•
list.remove(value) – 특정 값을 찾아서 제거: O(n)
•
value in list – 값 존재 여부 확인: O(n)
문자열(String)
•
str.find(substring) – 부분 문자열 검색: O(n)
•
str.replace(old, new) – 문자열 교체: O(n)
딕셔너리(Dictionary), 세트(Set)
•
Iteration (반복): O(n) (모든 키나 값에 대해 반복)
덱(Deque)
•
deque.rotate(k) – 덱을 k칸 회전: O(n)
•
deque.remove(value) – 특정 값을 제거: O(n)
4. O(n log n) - 선형 로그 시간
정렬 및 병합
•
sorted(list) – 리스트 정렬: O(n log n)
•
list.sort() – 리스트 자체 정렬 (in-place): O(n log n)
•
heapq.merge(*iterables) – 여러 이터러블을 병합: O(n log k) (k는 병합할 이터러블의 개수)
5. O(n²) - 이차 시간
리스트(List)
•
list.sort()에서 최악의 경우: O(n²) (이미 정렬된 상태에서 비효율적인 피벗을 선택한 경우)
6. O(n * m) - 동적 계획법(DP) 관련 연산
동적 계획법(DP)을 구현할 때 주로 2차원 배열을 사용하여 O(n * m) 복잡도를 가지는 문제를 해결하게 된다.
리스트(List) 내 2차원 배열 접근
•
dp[i][j] – 2차원 리스트의 값에 접근: O(1) (단일 접근)
•
전체 반복 및 연산: O(n * m) (DP 문제에서 모든 상태를 갱신할 때)
7. O(2^n) - 지수 시간
일반적으로 재귀 알고리즘에서의 메모이제이션(Memoization)을 사용하지 않으면, 중복 계산으로 인해 발생하는 지수 시간 복잡도의 문제들이 있다.
Python에서는 동적 계획법에서 메모이제이션을 통해 복잡도를 최적화할 수 있다.
•
재귀적 피보나치 수열 계산: O(2^n) (메모이제이션 없을 때)
외장 메서드
1. 정렬 관련 메서드
sorted()
•
설명: 새로운 정렬된 리스트를 반환한다.
•
시간 복잡도: O(n log n) (Timsort 알고리즘 사용)
•
사용 예시:
sorted_list = sorted([3, 1, 2]) # [1, 2, 3]
Python
복사
list.sort()
•
설명: 리스트 자체를 정렬(in-place)한다.
•
시간 복잡도: O(n log n) (Timsort 알고리즘 사용)
•
사용 예시:
arr = [3, 1, 2]
arr.sort() # arr는 [1, 2, 3]으로 변경
Python
복사
sorted(iterable, key=lambda x: x[1])
•
설명: 특정 기준(key)을 기준으로 정렬할 수 있다.
•
시간 복잡도: O(n log n)
•
사용 예시:
arr = [(1, 'a'), (3, 'c'), (2, 'b')]
sorted_by_second = sorted(arr, key=lambda x: x[1]) # [(1, 'a'), (2, 'b'), (3, 'c')]
Python
복사
2. 데이터 변환 및 조작
map()
•
설명: 주어진 함수를 이터러블의 모든 요소에 적용하여 새로운 이터러블을 반환한다.
•
시간 복잡도: O(n)
•
사용 예시:
nums = [1, 2, 3]
squared = list(map(lambda x: x**2, nums)) # [1, 4, 9]
Python
복사
filter()
•
설명: 주어진 조건을 만족하는 요소만 필터링하여 반환한다.
•
시간 복잡도: O(n)
•
사용 예시:
nums = [1, 2, 3, 4]
even_nums = list(filter(lambda x: x % 2 == 0, nums)) # [2, 4]
Python
복사
zip()
•
설명: 두 개 이상의 이터러블의 요소들을 묶어서 튜플 형태로 반환한다.
•
시간 복잡도: O(n) (n은 가장 짧은 이터러블의 길이)
•
사용 예시:
a = [1, 2, 3]
b = ['a', 'b', 'c']
zipped = list(zip(a, b)) # [(1, 'a'), (2, 'b'), (3, 'c')]
Python
복사
enumerate()
•
설명: 이터러블의 요소에 인덱스를 부여하여 튜플 형태로 반환한다.
•
시간 복잡도: O(n)
•
사용 예시:
arr = ['a', 'b', 'c']
enumerated = list(enumerate(arr)) # [(0, 'a'), (1, 'b'), (2, 'c')]
Python
복사
3. 수학 관련 함수
sum()
•
설명: 이터러블의 모든 요소의 합을 구한다.
•
시간 복잡도: O(n)
•
사용 예시:
total = sum([1, 2, 3, 4]) # 10
Python
복사
min() / max()
•
설명: 이터러블의 최솟값/최댓값을 반환한다.
•
시간 복잡도: O(n)
•
사용 예시:
minimum = min([3, 1, 2]) # 1
maximum = max([3, 1, 2]) # 3
Python
복사
math 모듈
•
설명: 수학 관련 함수들을 제공한다.
•
시간 복잡도: O(1) (제곱근, 최대 공약수 등 대부분의 기본 연산)
•
주요 메서드:
◦
math.sqrt(x) – 제곱근 계산: O(1)
◦
math.gcd(a, b) – 최대 공약수 계산: O(log(min(a, b)))
◦
math.factorial(n) – 팩토리얼 계산: O(n)
◦
math.ceil(x) – 올림 함수: O(1)
◦
math.floor(x) – 내림 함수: O(1)
•
사용 예시:
import math
result = math.sqrt(16) # 4.0
Python
복사
4. 반복 및 조합 관련 함수
itertools 모듈
•
설명: 반복과 관련된 다양한 함수를 제공하는 모듈로, 조합(combination), 순열(permutation) 등을 생성하는데 자주 사용된다.
•
주요 메서드:
◦
itertools.permutations(iterable, r) – r개를 선택해 순열 생성: O(r!)
◦
itertools.combinations(iterable, r) – r개를 선택해 조합 생성: O(nCr) = O(n! / (r! * (n - r)!))
◦
itertools.product(iterable, repeat=n) – 모든 가능한 데카르트 곱 생성: O(n^r)
◦
itertools.chain(*iterables) – 여러 이터러블을 하나로 연결: O(n)
•
사용 예시:
from itertools import permutations, combinations, product
# 순열 생성
perm = list(permutations([1, 2, 3], 2)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
# 조합 생성
comb = list(combinations([1, 2, 3], 2)) # [(1, 2), (1, 3), (2, 3)]
# 데카르트 곱
prod = list(product([1, 2], repeat=2)) # [(1, 1), (1, 2), (2, 1), (2, 2)]
Python
복사
5. 카운팅 및 통계
collections.Counter
•
설명: 이터러블의 요소를 카운팅하여 빈도를 저장하는 딕셔너리 형태로 반환한다.
•
시간 복잡도: O(n)
•
사용 예시:
from collections import Counter
cnt = Counter([1, 2, 2, 3, 3, 3]) # Counter({3: 3, 2: 2, 1: 1})
Python
복사
statistics 모듈
•
설명: 평균, 중앙값 등 통계 관련 함수들을 제공한다.
•
시간 복잡도: O(n)
•
주요 메서드:
◦
statistics.mean(data) – 평균 계산: O(n)
◦
statistics.median(data) – 중앙값 계산: O(n log n) (정렬 필요)
◦
statistics.mode(data) – 최빈값 계산: O(n)
•
사용 예시:
import statistics
mean_value = statistics.mean([1, 2, 3, 4]) # 2.5
Python
복사
6. 문자열 처리
str.split()
•
설명: 문자열을 특정 구분자로 나누어 리스트로 반환한다.
•
시간 복잡도: O(n)
•
사용 예시:
sentence = "a b c"
words = sentence.split() # ['a', 'b', 'c']
Python
복사
str.join()
•
설명: 리스트 등의 이터러블을 하나의 문자열로 합친다.
•
시간 복잡도: O(n) (리스트의 모든 문자열을 연결하는 작업)
•
사용 예시:
words = ['a', 'b', 'c']
sentence = " ".join(words) # 'a b c'
Python
복사
str.replace()
•
설명: 문자열에서 특정 부분을 다른 값으로 치환한다.
•
시간 복잡도: O(n)
•
사용 예시:
sentence = "hello world"
new_sentence = sentence.replace("world", "python") # 'hello python'
Python
복사
floatFirstTOC: right
YAML
복사
