GCD / LCM - 유클리드 호제법
최대공약수(GCD)와 최소공배수(LCM)를 구하는 알고리즘
def gcd(a, b): # a = min(a, b) / b = max(a, b)
if b == 0:
return b
if a % b == 0:
return b
else:
return gcd(b, a % b)
def lcm(a, b): # a = min(a, b) / b = max(a, b)
return int(a * b / gcd(a, b))
소수 찾기- 에라토스테네스의 체
임의의 자연수 n에 대해 그 이하의 소수를 가장 간단하고 빠르게 찾는 알고리즘
- 핵심 : n의 제곱근 까지만 확인
def eratosthenes(n, arr):
for i in range(2, int(n ** 0.5) + 1):
if arr[i]:
j = 2
while i * j <= n:
arr[i * j] = False
j += 1
# arr의 인덱스가 True이면 해당 인덱스의 수는 소수임
arr = [True for _ in range(n + 1)]
정렬
선택 정렬
'''
선택 정렬 : 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘
- 가장 윈시적이고 기초적인 방법이며 비효율적임
시간 복잡도 : O(N^2)
'''
# 스왑 메소드
def swap(a, b):
temp = a
a = b
b = temp
return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("선택 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 선택 정렬
index = 0
for i in range(0, n):
min = 9999
for j in range(i, n):
if min > list[j]:
min = list[j]
index = j
list[i], list[index] = swap(list[i], list[index])
# 정렬된 리스트 출력
for i in list:
print(i, end=' ')
버블정렬
'''
버블 정렬 : 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 알고리즘
(앞에서 부터 큰 값을 뒤로 보내는 것과 같음)
- 구현이 가장 쉽지만 가장 비효율적인 알고리즘 : 매번 스왑을 해야하기 때문
시간 복잡도 : O(N^2)
'''
# 스왑 메소드
def swap(a, b):
temp = a
a = b
b = temp
return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("버블 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 버블 정렬
for i in range(0, n):
for j in range(1, n-i):
if list[j-1] > list[j]:
list[j - 1], list[j] = swap(list[j-1], list[j])
# 정렬된 리스트 출력
for i in list:
print(i, end=' ')
삽입정렬
'''
삽입 정렬 : 각 숫자를 적절한 위치에 삽입하는 알고리즘
(뒤로 가면서 앞의 숫자 크기를 보고 그 사이에 적절히 삽입)
- 선택, 버블 정렬에 비해 필요한 경우에만 위치를 바꿔 좀 더 효율적임
- 미리 어느정도 정렬이 되어 있다면 아주 빠르게 끝낼 수 있음
시간 복잡도 : O(N^2) (최악의 경우)
'''
# 스왑 메소드
def swap(a, b):
temp = a
a = b
b = temp
return (a, b)
# 정렬할 리스트 입력
list = list(map(int, input("삽입 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 삽입 정렬
# while 문
for i in range(1, n):
key = list[i] # key : 정렬할 원소
j = i - 1
while j >= 0 and list[j] > key:
list[j+1] = list[j]
j = j - 1
list[j+1] = key
# for 문
'''for i in range(0, n-1):
#for j in range(0, i+1):
# print(list[j], end=' ')
for j in range(0, i+1):
if list[i-j] > list[i-j + 1]:
list[i-j], list[i-j + 1] = swap(list[i-j], list[i-j + 1])
#print("")'''
# 정렬된 리스트 출력
for i in list:
print(i, end=' ')
퀵정렬
'''
퀵 정렬 : 대표적인 '분할 정복' 알고리즘(Divide and conquer algorithm)으로,
특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 것을 반복 하는 알고리즘.
[규칙]
- 기준 값인 피벗(Pivot)이 필요 (보통 첫 번째 원소를 피벗으로 사용함)
- 기준 값보다 큰 값을 배열의 왼쪽부터, 작은 값을 오른쪽부터 찾음.
- 작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환.
- 작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환.
- 위 과정을 기준 값의 좌우측에 반복
시간 복잡도: O(N * logN) (평균)
O(N^2) (최악) -> 피벗값에 따라 최악의 경우가 생길 수 있음 [ex) 이미 정렬된 배열]
'''
# 스왑 메소드
def swap(a, b):
temp = a
a = b
b = temp
return (a, b)
# 재귀를 이용하여 퀵 정렬 수행
def quickSort(start, end):
if start>=end: # 원소가 1개인 경우 그대로 둠
return
pivot = start # 피벗은 첫번째 원소
i = start + 1
j = end
while i <= j: # 엇갈릴 때까지 반복
while(i <= end and list[i] <= list[pivot]): #끝에 도달하거나 피벗보다 큰 값을 찾을 때까지 반복
i = i + 1
while(j > start and list[j] >= list[pivot]): #피벗에 도달하거나 피벗보다 작은 값을 찾을 때까지 반복
j = j - 1
if(i > j): # 엇갈린 상태(작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환)
list[pivot], list[j] = swap(list[pivot], list[j])
else: # 엇갈리지 않은 상태 (작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환)
list[i], list[j] = swap(list[i], list[j])
quickSort(start, j - 1); # 피벗보다 작은 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
quickSort(j + 1, end); # 피벗보다 큰 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
# 정렬할 리스트 입력
list = list(map(int, input("퀵 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 퀵 정렬
quickSort(0, n-1)
# 정렬된 리스트 출력
for i in list:
print(i, end=' ')
병합정렬
'''
병합 정렬 : 퀵 정렬과 같은 분할 정복 알고리즘을 사용하는 정렬 알고리즘.
일단 반으로 나누고 나중에 정렬하는 방식
- 퀵 정렬과 다르게 피벗 값에 상관없이 정확히 반을 나누어 정렬하므로 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장한다.
[방법]
- 다 쪼개진 원소들을 합치면서 정렬을 수행
- 합쳐진 배열은 정렬이 됨
- 최종적으로 합쳐지면 정렬이된 전체 배열을 얻음
시간 복잡도 : O(N * logN)
'''
# 스왑 메소드
def swap(a, b):
temp = a
a = b
b = temp
return (a, b)
# 재귀를 이용하여 퀵 정렬 수행
def mergeSort(list):
if len(list) < 2:
return list
mid = len(list) // 2
low_arr = mergeSort(list[:mid])
high_arr = mergeSort(list[mid:])
mergedList = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
mergedList.append(low_arr[l])
l += 1
else:
mergedList.append(high_arr[h])
h += 1
mergedList += low_arr[l:]
mergedList += high_arr[h:]
return mergedList
# 정렬할 리스트 입력
list = list(map(int, input("병합 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' ')))
n = len(list)
# 병합 정렬
print()
list = mergeSort(list)
# 정렬된 리스트 출력
for i in list:
print(i, end=' ')
계수정렬
count = [0] * (max(arr) + 1)
for num in arr:
count[num] += 1
DFS
def dfs(graph, node, visited):
visited[node] = True
#print(node, end=' ')
for v in graph[node]:
if not visited[v]:
dfs(graph, v, visited)
BFS
from collections import deque
def bfs(graph, start, visited):
q = deque()
q.append(start)
visited[start] = True
while q:
node = q.popleft()
# print(node, end=' ')
for v in graph[node]:
if not visited[v]:
visited[v] = True
q.append(v)
이진 탐색
기본
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
파라메트릭 서치 - 떡볶이 떡 만들기 예
- 이진 탐색을 이용한 최적화 (타겟에 가까운 값 구하기)
최단 경로 - 다익스트라
import heapq
INF = int(1e9) #무한을 의미하는 상수
# 노드의 개수 n, 간선의 개수 m
n, m = map(int, input().split())
# 시작 노드 번호 start
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for _ in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트 만들기
# visited = [False] * (n + 1) # 우선순위 큐를 통해 확인 가능해 졌으므로 제거
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
def dijkstra(graph, start, distance):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = distance[now] + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
최단 경로 - 플로이드 워셜
INF = int(1e9) # 무한을 의미하는 상수
# 노드의 개수 및 간선의 개수 입력
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
graph[a][a] = 0
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
def floyd_warshall(graph, n):
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
최소 신장 트리 - 크루스칼
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 모든 간선에 대한 정보를 입력
for _ in range(e):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
# 간선을 하나씩 확인하며
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
위상 정렬
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) # 정점 A에서 B로 이동 가능
# 진입차수를 1 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
for i in graph[now]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
추가
최장 증가 부분 수열 (LIS)
# 시간복잡도: O(n^2)
def lis(p):
n = len(p)
dp_length = [1] * n
for i in range(n):
for j in range(i + 1, n):
if p[i] < p[j]:
dp_length[i] = max(dp_length[j], dp_length[i] + 1)
return max(dp_length) # 가장 긴 값 반환
# 시간복잡도: O(n log n) -> 2진 탐색 활용
def binary_search(arr, target, start, end):
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
end = mid - 1
else:
start = mid + 1
return start
def lis(p):
dp = []
for i in p:
idx = binary_search(dp, i, 0, len(dp) - 1)
if idx == len(dp):
dp.append(i)
else:
dp[idx] = i
return len(dp)
# bisect 모듈의 bisect_left 함수를 사용 => binary_search함수 대신 사용
from bisect import bisect_left
idx = bisect_left(dp, i)
