파이썬 알고리즘 공부기록
Basic of Python Code
LeetCode 기출문제 분석을 통한 코딩테스트 준비
✏️ 6장 문자열 조작
- 유효한 팰린드롬 | 슬라이싱
- 문자열 뒤집기 | s.reverse()
- 로그 파일 재정렬 | 람다 표현식 정렬
- 가장 흔한 단어 | 입력값 전처리, 리스트 컴프리헨션, collection.Counter()
- 그룹 애너그램 | 정렬하여 딕셔너리에 추가, sorted(), ' '.join(s)
- 가장 긴 팰린드롬 부분 문자열 | 슬라이딩 윈도우, 투 포인터 확장
파이썬의 정렬 알고리즘 : 팀소트(Timosrt) (삽입 정렬과 병합 정렬을 휴리스틱하게 조합하여 사용하는 정렬 알고리즘으로, 가장 빠른 시간 복잡도를 보인다.
✏️ 7장 배열
- 두 수의 합 | 시간복잡도
- 빗물 트래핑 | 투 포인터 이동, 난이도 상 ⭐⭐⭐
- 세 수의 합 | 투 포인터
- 배열 파티션1 | Pythonic Way
- 자신을 제외한 배열의 곱 | 아이디어 문제
- 주식을 사고팔기 가장 좋은 시점 | 최대, 최소 갱신
✏️ 8장 연결 리스트
- 팰린드롬 연결 리스트 | 데크(Deque), 런너(Runner), 다중 할당
- 두 정렬 리스트의 병합 | 변수 스왑
- 역순 연결 리스트 | 반복이 재귀보다 공간복잡도, 실행 속도 면에서 우수하다.
- 두 수의 덧셈 | 전가산기(Full Adder), divmod, functools.reduce()
- 페어의 노드 스왑 | 스왑(swap), 반복구조와 재귀구조
- 홀짝 연결 리스트 | 문제 이해의 중요성
- 역순 연결 리스트2 | 반복 구조로 노드 뒤집기
✏️ 9장 스택, 큐
- 유효한 괄호 |스택 일치 여부 판별
- 중복 문자 제거 | 재귀를 이용한 분리, 스택을 이용한 문자 제거
- 일일 온도 | 시각화, 스택 값과 현재 값 비교
- 큐를 이용한 스택 구현 | push(x), pop(), top(), empty()
- 스택을 이용한 큐 구현 | push(x), pop(), peek(), empty()
- 원형 큐 디자인 | enQueue(), deQueue(), Front(), Rear(), isEmpty(), isFull()
스택(Stack) 은 LIFO(Last-In-First-Out)(후입선출), 큐(Queue) 는 FIFO(FIrst-In-First-Out)(선입선출)로 처리된다.
파이썬의 리스트는 스택과 큐의 모든 연산을 지원하지만, 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 데크(Deque)라는 별도의 자료형을 사용해야 더 좋은 성능을 낼 수 있다.
✏️ 10장 데크, 우선순위 큐
- 원형 데크 디자인
- k개 졍렬 리스트 병합 | PriorityQueue vs heapq
데크(Deque) 는 더블 엔디드 큐(Double-Ended Queue)의 줄임말로, 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. 구현은 배열이나 연결 리스트 모두 가능하지만, 이중 연결 리스트(Doubly Linked List) 로 구현하는 편이 가장 잘 어울린다.
우선순위 큐 는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다. 힙(Heap) 자료구조와 관련이 깊다.
파이썬 전역 인터프리터 락(GIL) : 하나의 스레드가 자원을 독점하는 형태로 실행된다.
✏️ 11장 해시 테이블
- 해시맵 디자인 | put(key, value), get(key), remove(key)
- 보석과 돌 | defaultdict, Counter, Pythonic Way
- 중복 문자 없는 가장 긴 부분 문자열 | 슬라이딩 윈도우, 투 포인터
- 상위 K 빈도 요소 | zip(), 아스테리스크(*), Unpacking/Packing
해시 테이블 또는 해시 맵 은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조다. 해시 함수 란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.
✅ 성능 좋은 해시 함수의 특징
* 해시 함수 값 충돌의 최소화 -> **비둘기집 원리**
* 쉽고 빠른 연산
* 해시 테이블 전체에 해시 값이 균일하게 분포
* 사용할 키의 모든 정보를 이용하여 해싱
* 해시 테이블 사용 효율이 높을 -> **로드 팩터** 낮을수록 효율이 좋다.
비둘기집 원리
n개 아이템을 m개 컨테이너에 넣을 때, n>m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리
로드 팩터(Load Factor)
해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것
31
정수형 해싱 기법인 모듈로 연산을 이용한 나눗셈 방식(Modulo-Division Method)에서, m 값으로 가장 적절한 매직 넘버(Magic Number) 이자 메르센 소수(Mersenne Prime)(2의 거듭제곱에서 1이 모자란 수 중 소수로 매우 신비한 성질을 지닌다)
// C
/* hash: 문자열 s에 대한 해시 값 구성 */
unsigned hash(char *s) {
unsigned hashval;
for (hashval = 0; *s != '/0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
// Java
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
✅ 충돌(Collusion) 발생 시
- 개별 체이닝(Separate Chaining) : 충돌 발생 시 연결 리스트로 연결
- 오픈 어드레싱(Open Addressing) : 충돌 발생 시 탐사(Probing)를 통해 빈 공간을 찾아나서는 방식 *(파이썬에서 사용되는 방식)
✏️ 12장 그래프
- 섬의 개수 | dfs 재귀 호출, 파이썬 중첩함수
- 전화 번호 문자 조합 | dfs 재귀 호출, dictionary 활용
- 순열 | dfs, 객체 복사[:], itertools.permuatations()
- 조합 | dfs, itertools.combinations()
- 조합의 합 | dfs
- 부분집합 | 트리를 구성하여 dfs
- 일정 재구성 | 재귀 vs 반복
- 코스 스케줄 | DFS로 순환 구조 판별, 가지치기, defaultdict 순회 문제
그래프 란, 객체의 일부 쌍(pair)들이 '연관되어' 있는 객체 집합 구조를 말한다.
오일러 경로
모든 edge를 한 번씩 방문하는 유한 그래프
오일러의 정리에 의하면, 모든 vertex가 짝수 개의 degree를 갖는다면, 모든 다리를 한 번씩 건너서 도달하는 것이 성립 가능하다.
해밀턴 경로(Hamiltonian Path)
각 vertex를 한 번씩 방문하는 무향 또는 유향 그래프
대표적인 NP-complete 문제로, 최적 알고리즘이 없다.
외판원 문제(TSP)
해밀턴 순환의 최단거리를 찾는 문제
NP-난해 문제이다.
NP문제
비결정론적 튜닝 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합
"P 집합은 NP 집합의 부분집합이다. P=NP 인지는 아직 알려지지 않았다."
NP 문제이면서 NP-난해 문제 : NP-완전 문제
그래프 순회(그래프 탐색) : 그래프의 각 vertex를 방문하는 과정으로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 방법이 있다.
DFS(깊이 우선 탐색)
// 재귀
// Sudo Code
DFS(G, V)
label v as discoverd
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discoverd then
recursively call DFS(G, w)
// Python
def recursive_dfs(v, discovered=[]):
discovered.append(v)
for w in gragh[v]:
if w not in discovered:
discovered = recursive_dfs(w, discovered)
return discovered
// 스택
// Sudo Code
DFS-iterative(G, v)
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
// Python
def iterative_dfs(start_v):
discovered = []
stack = [start_v]
while stack:
v = stack.pop()
if v not in discovered:
discovered.append(v)
for w in graph[v]:
stack.append(w)
return discovered
BFS(너비 우선 탐색)
//큐
// Sudo Code
BFS(G, start_v)
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent := v
Q.enqueue(w)
// Python
def iterative_bfs(start_v):
discovered = [start_v]
queue = [start_v]
while queue:
v = queue.pop(0)
for w in graph[v]:
discovered.append(w)
queue.append(w)
return discovered
BFS는 재귀로 동작하지 않는다.
백트래킹(Backtracking)
해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(backtrack)해 정답을 찾아가는 범용적인 알고리즘으로, 제약 충족 문제에 특히 유용하다.
트리의 가지치기(Pruning)에 해당한다.
제약 충족 문제(CSP)
수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제
✏️ 13장 최단 경로 문제
- 네트워크 딜레이 타임 | 다익스트라 알고리즘, 우선순위 큐
- K 경유지 내 가장 저렴한 항공권 | 다익스트라 알고리즘, 우선순위 큐, 경유지 제한
최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 말한다.
오컴의 면도날(Occam's Razor)
어떤 현상을 설명할 때 필요 이상의 가정과 개념들은 면도날로 베어낼 필요가 있다는 권고로 쓰이는 용어이다. 사고의 절약을 요구하는 이 원리는 과학 분야에서 널리 응용되는 일반적인 지침이다.
// Dijkstra Algorithm Sudo Code
function Dijkstra(Graph, source):
dist[source] <- 0
create vertex priority queue Q
for each vertex v in Graph:
if v != source
dist[v] <- INFINITY
prev[v] <- UNDEFINED
Q.add_with_priority(v, dist[v])
while Q is not empty:
u <- Q.extract_min()
for each neighbor v of u:
alt <- dist[u] + length(u, v)
if alt < dist[v]
dist[v] <- alt
prev[v] <- u
Q.decrease_priority(v, alt)
return dist, prev
✏️ 14장 트리
- 이진 트리의 최대 깊이 | 반복 구조로 BFS 풀이
- 이진 트리의 직경 | 상태값 누적 트리 DFS, 중첩 함수에서 클래스 변수 사용
- 가장 긴 동일 값의 경로 | 상태값 거리 계산 DFS
- 이진 트리 반전 | 재귀 방식, 반복 구조 BFS, 반복 구조 DFS, 반복구조 DFS 후위 순회
- 이진 트리 병합 | 재귀 탐색, 후위 순회
- 이진 트리 직렬화&역직렬화 | 피클링(pickling), BFS 구현
- 균형 이진 트리 | 높이 균형(Height-Balanced)의 중요성, 재귀 호출
- 최소 높이 트리 | 무방향 그래프, 리프 노드 제거 반복
- Convert Sorted Array to Binary Search Tree | 이진 탐색 트리(BST) 변환, 분할 정복 구조
- BST To Greater Sum Tree | 이진 탐색 트리(BST) 중위 순회(In-Order)
- Range Sum of BST | DFS 가지치기, 반복구조 DFS
- 이진 탐색 트리 노드 간 최소 거리 | 중위 순회(In-Order)
- 전위, 중위 순회 결과로 이진 트리 구축 | 중위 순회의 분할 정복(Divide and Conquer)
**트리(Tree)**는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.
서브트리(Subtree)
재귀로 정의된(recursively defined) 자기 참조(self-referential) 자료구조
그래프 vs 트리
트리는 순환 구조(Cyclic)를 갖지 않는 그래프이다.
그래프는 단방향과 양방향 모두 가능하지만, 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다.
트리는 하나의 부모 노드를 갖고, 루트 또한 하나여야 한다.
이진 트리(Binary Tree) : 모든 노드의 차수가 2 이하일 때 (다진 트리에 비해 훨씬 간결하고, 여러 알고리즘 구현을 간단하게 처리할 수 있다.)
정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
포화 이진 트리(Perfect Binary Tree) : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
이진 탐색 트리(BST)
왼쪽과 오른쪽의 값들이 각각 값의 크기에 따라 정렬되어 있는 트리로, 시간 복잡도가 O(log n) 이다.
자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)
삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리로, AVL트리, 레드-블랙 트리 등이 있다.
트리 순회
# 전위 순회
def preorder(node):
if node is None:
return
print(node.val)
preorder(node.left)
preorder(node.right)
# 중위 순회
def inorder(node):
if node is None:
return
inorder(node.left)
print(node.val)
inorder(node.right)
# 후위 순회
def postorder(node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.val)
✏️ 15장 힙
- 이진 힙(Binary Heap) 구현
- 배열의 K번째 큰 요소 | heapq 모듈, heapify(), nlargest(), sorted()
힙(Heap) 은 상/하 관계를 보장하며, 특히 최소 힙에서는 부모가 항상 자식보다 작다. 반면 BST는 좌/우 관계를 보장한다.
BST는 탐색과 삽입 모두 O(log n)에 가능하며, 모든 값이 정렬되어야 할 때 사용한다.
반면 가장 큰 값을 추출하거나(최대 힙) 가장 작은 값을 추출하려면(최소 힙) 이진 힙을 사용해야 한다. 이진 힙은 이 작업이 O(1)에 가능하다.
✏️ 16장 트라이
- 트라이 구현 | TrieNode(), insert(), search(), startsWith()
- 팰린드롬 페어 | Trie 구현, @staticmethod 데코레이터, 세 가지 판별 로직 ⭐⭐⭐
트라이(Trie) 는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조다.
전형적인 다진 트리(m-ary Tree)의 형태를 띤다.
문자열의 길이 만큼만 탐색하면 원하는 결과를 얻어낼 수 있다.
특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다.
✏️ 17장 정렬
- 리스트 정렬 | 병합 정렬, Runner 기법, sort()
- 구간 병합 | 람다 정렬 후 병합, a += b,(콤마 연산자)
- 삽입 정렬 리스트 | 삽입 정렬, 비교 조건 개선 최적화
- 가장 큰 수 | 삽입 정렬, 맨 앞에서부터 자릿수 단위로 비교
- 유효한 애너그램 | 정렬 비교, 파이썬다운 방식
병합 정렬(Merge Sort)
존 폰 노이만이 1945년에 고안한 알고리즘으로, divide and conquer를 이용하여 O(nlogn)의 시간복잡도를 만족하는 안정 정렬 알고리즘이다.
퀵 정렬(Quick Sort)
토니 호어가 1959년에 고안한 알고리즘으로, 피벗(pivot)을 기준으로 좌우로 나누는(partitioning) 특징을 갖는 분할 정보 알고리즘이다.
안정 정렬(Stable Sort)
안정 정렬 알고리즘은 중복된 값을 입력된 순서와 동일하게 정렬한다.
팀소트(Timsort)
파이썬은 병합 정렬과 삽입 정렬을 휴리스틱하게 조합한 팀소트를 사용한다.
3. baekjoon
파이썬으로 백준 알고리즘 문제 풀이
📎 단계별로 풀어보기
| 단계 | 제목 | 설명 | 풀이 |
|---|---|---|---|
| 1 | 입출력과 사칙연산 | 입력, 출력과 사칙연산을 연습해 봅시다. Hello World! | Helloworld / We love kriii / 고양이 / 개 / A+B / 사칙연산 / 나머지 / 곱셈 |
| 2 | if문 | if문을 사용해 봅시다. | 두 수 비교하기 / 시험 성적 / 윤년 / 사분면 고르기 / 알람시계 |
| 3 | for문 | for문을 사용해 봅시다. | / 구구단 / A+B_3 / 합 / 빠른A+B / N찍기 / 기찍N / A+B_7 / A+B_8 / 별찍기1 / 별찍기2 / X보다작은수 |
| 4 | while문 | while문을 사용해 봅시다. | A+B_5 / A+B_4 / 더하기사이클 |
| 5 | 1차원 배열 | 배열을 사용해 봅시다. | 최소, 최대 / 최댓값 / 숫자의 개수 / 나머지 / 평균 / OX퀴즈 / 평균은 넘겠지 |
| 6 | 함수 | 함수를 정의하면 코드가 깔끔해지고 관리하기 쉬워집니다. | 정수 N개의 합 / 셀프 넘버 / 한수 |
| 7 | 문자열 | 문자열을 다루는 문제들을 해결해 봅시다. | 아스키코드 / 숫자의 합 / 알파벳 찾기 / 문자열 반복 / 단어 공부 / 단어의 개수 / 상수 / 다이얼 |
4. LeetCode
리트코드 문제 풀이 챌린지
🏆 Challenge
| Steps | Title | Solutions |
|---|---|---|
| 1 | May LeetCoding Challenge 2021 | Super Palindromes / Valid Number / Find and Replace Pattern |
| 2 | July LeetCoding Challenge 2021 | Isomorphic String / Custom Sort String / Partition Array into Disjoint Intervals |