Python/Algorithm

빅오 표기법 (Big-O)

Big-O 수학에서 빅오란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 표기방법을 말합니다. 컴퓨터과학에서 빅오는 어떤 알고리즘을 수행하는 데 걸리는 시간 또는 공간 복잡도를 표기하는 방법입니다. 그렇다면 왜 컴퓨터과학에서 빅오 표기법이 필요할까요?? 보통 일반 컴퓨터의 경우 1초에 억단위의 연산을 수행하기 때문에 작은 입력에 대해서는 효율적인 알고리즘과 비효율적인 알고리즘의 수행 시간의 차이를 확인하기 어렵습니다. 또한 그래프에서 볼 수 있듯이 작은 값에서는 빨리 동작하는 알고리즘도 충분히 큰 값에서는 매우 느리게 동작할 수도 있기 때문에 보통 알고리즘의 효율성을 나타내는 시간 복잡도를 표기하기 위해 빅오 표기법을 사용합니다. 시간복잡도 대부분의 알고리즘은 아래 시간 복잡도 중 하나에 속합니다. ..

다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍 전체 문제를 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성되는 문제, 즉 최적 부분 구조를 가지는 문제에 대해 적용 가능하다. DP 가정 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. DP, 그리디, 분할정복 참고로 그리디는 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이해 나가는 것이고, 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀어나간다는 차이점이 있다. 또한 분할 정복으로 분류되는 병합 정렬과 퀵 정렬은 중복된 하위 문제들을 푸는 것이 아니기 때문에 다이나믹 프로그래밍으로 분류하지..

투 포인터와 슬라이딩 윈도우

투 포인터 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제풀이 전략 일반적으로 배열이 정렬되어 있을 때 유용하며, 2개의 포인터가 좌우로 자유롭게 움직이면서 문제를 풀이한다. 대표적인 문제로 배열의 구간합과 관련된 문제나 수열의 연속합과 같은 문제에서 사용한다. 예제 배열에서 구간합이 m 이상인 구간의 최소 길이 찾기 n, m = map(int, input().split()) a = list(map(int, input().split())) left, right = 0, 0 ans = n + 1 sum = a[0] while left = m: ans = min(ans, right - left + 1) sum -= a[left] left += 1 if left > right a..

그래프 관련 알고리즘

위상정렬 그래프 이론에서 사용하는 정렬 방식으로 주로 사이클이 없는 방향 그래프에서, 정점들을 방향을 거스르는 간선없이 나열한다. 여러 작업들이 주어질 때 그 중 특정 작업을 마치기 위해 선행되어야 하는 작업들을 모두 정렬하는 테크닉 from collections import deque v, e = map(int, input().split()) # 모든 노드에 대한 진입 차수는 0으로 초기화 indegree = [0] * (v + 1) graph = [[] for _ in range(v + 1)] for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) # 진입차수를 1 증가 indegree[b] += 1 # 알고리즘 수행 결과를 담을..

버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그 다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복한다. 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않고 (제자리 정렬), 중복된 값을 입력 순서와 동일하게 정렬한다. (안정 정렬) 시간 복잡도는 최악, 최선, 평균 모두 O(n^2)으로 비효율적이며, 정렬되지 않은 원소가 정렬됐을 때의 자리로 가기 위해서 스왑 연산이 많이 일어난다. 알고리즘 def bubble_sort(arr): for i in range(len(arr) - 1, 0, -1): for j in range(i): if arr[j] > arr[j - 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] 조금 더 ..

트라이

트라이 (Trie) 각 노드에 문자를 저장하는 트리 기반의 자료구로, 트리를 아래쪽으로 순회하면 단어 하나가 나온다. 트라이는 길이가 K인 문자열이 주어졌을 때 O(K) 시간에 해당 문자열이 유효한 접두사인지 확인할 수 있다. 먄악 트리에서 연관된 접두사를 반복적으로 검색해야 하는 경우, 트리의 현재 노드를 참조값으로 넘긴다면 매번 검색할 때마다 루트에서 시작할 필요없이 자식 여부만 확인하면 된다. 구현 # Node 클래스 # key: 해당 노드의 문자, child: 자식 노드 # data: 문자열이 끝나는 위치를 알려주는 역할 (해당 노드에서 끝나는 문자열이 없으면 None) class Node: def __init__(self, key, data=None): self.key = key self.dat..

힙과 우선순위 큐

힙 (Heap) 힙은 힙의 특성을 만족하는 완전 이진 트리로, 최소 힙 기준으로 각 노드의 원소는 항상 자식 노드의 원소보다 작거나 같아야 한다. 최소 힙의 부모 노드는 항상 자식 노드보다 크거나 같지만, 부모-자식 간의 관계만 정의되어 있을 뿐 좌우 관계에 대한 정의는 하지 않기 때문에 힙은 정렬된 구조는 아니다. 인덱스 완전 이진 트리 형태인 이진 힙은 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산의 편의성을 위해 0번째 인덱스는 비워두고 1번째 인덱스부터 사용한다. i번째 노드에 대해 부모 노드의 인덱스는 i // 2, 왼쪽 자식 노드의 인덱스는 2 * i, 오른쪽 자식 노드의 인덱스는 2 * i + 1로 계산된다. 원소 삽입 (Python) 최소 힙에 원소를 삽입할 때는 언..

트리의 종류와 트리 순회

트리 (Tree) 트리는 사이클을 갖지 않는 하나의 연결 그래프로, 부모-자식의 계층적 관계를 표현하는 자료구조이다. 하나의 루트 노드는 0개 이상의 자식 노드를 가지고, 또 그 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 즉, 트리는 재귀로 정의된 자기 참조 자료구조로 서브트리로 구성된다. 트리는 특수한 형태의 그래프의 일종으로 그래프에 포함되지만, 그래프와 달리 두 노드 간의 경로는 유일하다. 그래프와 트리 모두 비선형 자료구조로 그래프는 단방향과 양방향 모두 표현 가능하지만 트리는 부모 노드에서 자식 노드로의 단방향만 표현 가능하다. 이진 트리 각 노드가 최대 두 개의 자식 노드를 갖는 트리로, 대표적으로 다음과 같은 3가지 유형이 있다. 정 이진 트리 (Full Binary Tree) 모든 ..

최단 경로 알고리즘

최단 경로 문제 최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제이다. 이때 가중치는 거리나 시간과 같은 이동 비용에 해당한다. BFS 간선의 가중치가 모두 1인 두 노드 사이의 최단 경로를 찾는데 사용한다. 인접 리스트로 구현 시 시간 복잡도는 O(V+E)이고, 인접 행렬로 구현 시 시간 복잡도는 O(V^2)이다. 구현 (경로 추적 포함) from collections import deque import sys sys.setrecursionlimit(200000) n, k = map(int, input().split()) time = [-1] * 200001 time[n] = 0 path = [-1] * 200001 path[n] = n q = deque() q.a..