기본 자료구조 / 알고리즘 정리

 

1. 기본 자료구조

1.1 리스트: 가장 기초적인 자료 구조

- 특징: 추가 / 탐색 / 제거 등 대부분 O(N)

list.count(obj): 요수 개수

list.index(obj): 요소 위치 idx

list.insert(idx, obj)

list.pop(idx): 마지막 요소 제거 및 반환 / 특정 요소 제거 및 반환 

list.remove(obj)

list.reverse(): 

list.sort(reverse=True): 기본 오름차순으로 정렬

 

1.2. Set: 중복을 허용하지 않음

- 특징: (파이썬) Set 자료구조는 Hash Table 구조로 O(1)로 탐색 가능

선언: set = set([1, 2, 3])

set.add(obj)

set.update(list): 

set.remove(obj): obj 제거, obj 없을 경우 err

set.discard(obj): obj 제거, obj 없어도 no err

set = set1 | set2: 합집합

set = set1 & set2: 교집합

set = set1 - set2: 차집합

set = set1 ^ set2: 대칭 차집합(합집합 - 교집합)

set1.issubset(set2): 부분집합 여부 확인

set1.issuperset(set2): 포함여부 확인

set1.isdisjoint(set2): 교집합 있는지 확인

 

3. Dictionary

dict.keys(): 모든 key 반환

dict.values(): 모든 value 반환

dict.items(): 모든 key-value tuple 반환

dict.clear(): 모든 원소 제거

dict1 = dict2.copy(): 복사

dict.fromkeys(seq, value): seq(key list)를 키로 갖는 신규 사전 생성 (모든 value=value(단일item))

dict.get(key, default=None): 해당 key의 value를 return, 없을 경우 None(default) 값 return

dict1.update(dict2): dict1에 dict2 추가

 

4. Heap: 기본 min-heap, 우선순위 큐로 종종 사용

q = []

heapq.heappush(q, (원소)): 원소 추가 O(logn)

heapq.heappop(q): 원소 꺼내기 O(logn)

heapq.heapify(list): 힙 정렬 O(N)

 

5. Deque: 큐로 종종 사용

deque.append(obj): 원소 추가

deque.popleft(): 원소 제거 및 return

deque.clear(): 모든 원소 제거

 

2. 기본 알고리즘

2.1. Greedy

: 현재 상황에서 최적만을 선택하는 알고리즘

 

2.2. 그래프의 표현: 인접 리스트 / 인접 행렬

 

2.2. DFS: 깊이 우선 탐색

 

2.3. BFS: 너비 우선 탐색

 

2.4. 정렬

- 계수 정렬

 

2.5. 이진 탐색

 

2.6. Dynamic Programming

- 메모이제이션

 

2.7 최단 경로 알고리즘

- 다익스트라

- Floyd-Warshall

- SPFA (Bellman-Ford)

 

2.8 그래프 알고리즘

- 서로소 집합 알고리즘: 서로소 집합 파악

- 무향 그래프의 cycle 파악: 서로소 집합 알고리즘

- 방향 그래프의 cycle 파악: DFS

- 최소 신장 트리: Kruskal

- 위상 정렬

 

2.9 구간 합 알고리즘