알고리즘/알고리즘 공부 정리
[알고리즘에서 유용]Python TeamNote 정리
정찡이
2021. 9. 24. 17:07
728x90
1. 정렬
1-1. 정렬 라이브러리
"""
1. sorted 함수 사용
"""
array = [7, 5, 9, 0, 1, 6, 2, 4, 8]
result = sorted(array)
print(result) # [0, 1, 2, 4, 5, 6, 7, 8, 9]
"""
2. sort 메소드 사용 - 리스트 변수
"""
array = [7, 5, 9, 0, 1, 6, 2, 4, 8]
array.sort()
print(array) # # [0, 1, 2, 4, 5, 6, 7, 8, 9]
"""
3. sort함수 - 람다
"""
data = [(25, 'Na'), (20, 'Kim'), (23, 'Seo'), (28, 'Park'), (20, 'Ahn')]
data.sort(key=lambda x: x[0]) # Stable Sort (When using a key)
print(data)
"""
4. 정렬 여러개하는 경우
"""
data = [(25, 'Na'), (20, 'Kim'), (23, 'Seo'), (28, 'Park'), (20, 'Ahn')]
s = sorted(data, key=lambda x: (x[1], x[2]))
2. BFS / DFS
2-1. bfs
2-1-1. 인접 리스트
from collections import deque
def bfs(graph, visited, start):
dq = deque([start])
visited[start] = True
while dq:
now = dq.popleft()
print(now, end=" ")
for next in graph[now]:
if not visited[next]:
dq.append(next)
visited[next] = True
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * len(graph)
bfs(graph, visited, 1)2-1-2. 인접 행렬
- 섬의 수 구하기
from collections import deque
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = 4, 3 # 세로, 가로
graph = [
[1, 1, 1],
[0, 0, 0],
[1, 1, 1],
[1, 1, 0]
]
visited = [[False] * m for _ in range(n)] # 방문 유무
count = 0 # 섬의 수
dq = deque()
for i in range(n):
for j in range(m):
if not visited[i][j] and graph[i][j] == 1:
count += 1
dq.append((i, j))
visited[i][j] = True
while dq:
x, y = dq.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if visited[nx][ny] or graph[nx][ny] != 1:
continue
dq.append((nx, ny))
visited[nx][ny] = True
print(count)- 최단 거리 구하기
"""
시작 (0,0) 위치에서 (n, m) 출구까지 이동한 거리
"""
from collections import deque
n, m = 5, 6
graph = [[1, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
result = 0
dq = deque()
dq.append((0, 0))
while dq:
x, y = dq.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
dq.append((nx, ny))
print(graph[n - 1][m - 1])2-2. dfs
2-2-1. 인접 리스트
def dfs(graph, visited, start):
visited[start] = True
print(start, end=" ")
for next in graph[start]:
if not visited[next]:
dfs(graph, visited, next)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * len(graph)
dfs(graph, visited, 1)2-2-2. 인접 행렬
n, m = 4, 3 # 세로, 가로
graph = [
[1, 1, 1],
[0, 0, 0],
[1, 1, 1],
[1, 1, 0]
]
visited = [[False] * m for _ in range(n)] # 방문 유무
def dfs(i, j):
if i < 0 or j < 0 or i >= n or j >= m:
return False
if graph[i][j] == 0:
return False
graph[i][j] = 0
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
return True
count = 0 # 독립된 노드 수
for i in range(n):
for j in range(m):
if dfs(i, j):
count += 1
print(count)
3. 이진 탐색
3-1. 이진 탐색 구현
def binary_search(array, target):
left = 0
right = len(array) - 1
while left <= right:
mid = (left + right) // 2
if array[mid] < target:
left = mid + 1
elif array[mid] > target:
right = mid - 1
elif array[mid] == target:
return mid
return None
array=[-1, 0, 3, 5, 9, 12] # 정렬된 리스트!
result = binary_search(array=array, target=2)
print(result)3-2. 이진탐색 모듈 사용(bisect)
import bisect
def binary_search(array=list(), target=int()):
index = bisect.bisect_left(array, target)
if index < len(array) and array[index] == target:
return index
return None
array=[-1, 0 , 3, 5, 9, 12] # 정렬된 리스트!
result = binary_search(array=array, target=5)
print(result)3-3. 이진탐색 모듈 사용하여 범위 구하기 (bisect)
import bisect
def count_by_range(a, left_val, right_val):
right_val = bisect.bisect_right(a, right_val)
left_val = bisect.bisect_left(a, left_val)
return right_val - left_val
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
print(count_by_range(a, 4, 4))
print(count_by_range(a, -1, 3))
4. Graph
- 다익스트라, 플로이드 와샬: 가중치가 있는 노드 거리 구하기
- 크루스칼: 가장 적은 비용으로 모든 노드를 연결
- 위상 정렬: 순서가 정해진 작업을 차례대로 수행할 때 사용
4-1. 다익스트라 - 한점 ~ 모든 노드 거리 구하기
import sys
import heapq
INF = int(1e9)
def dijkstra(start):
"""
1. 시작 노드 최단 테이블 0 설정 & q에 삽입
2. 방문하지 않은 노드 중 가장 짧은 노드를 선택 > heapq 사용(최소힙)
3. 해당 노드를 거쳐가는 다른 노드를 계산하여 작은 경우는 갱신 & 큐에 넣기
4. 2~3 반복
:param start:
:return:
"""
q = []
# 1. 최단 거리 테이블 초기화
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist > distance[now]: # 이미 방문함
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
n, m = map(int, sys.stdin.readline().split()) # 노드, 간선
start = int(sys.stdin.readline().split()[0])
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().split()) # a -> b, c 비용
graph[a].append((b, c))
dijkstra(start)
for i in range(1, n + 1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
'''
[Input Example 1]
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
[Output Example 1]
0
2
3
7
INFINITY
'''4-2. 플로이드 와샬 - 모든 노드
import sys
INF = int(1e9)
n = int(sys.stdin.readline().split()[0]) # 노드 수
m = int(sys.stdin.readline().split()[0]) # 간선 수
# 1. 2차원 배열 - 모든 값을 초기화: 모든 거리 무한, 자신으로 가는 거리 0
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 모든 최단 거리를 저장
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j:
graph[i][j] = 0
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
# 2. 다이나믹 프로그래밍
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])
for a in range(1, n + 1):
for b in range(1, n + 1):
if graph[a][b] == INF:
print("inf")
else:
print(graph[a][b], end=" ")
print()
"""
[Input Example 1]
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
[Output Example 1]
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0
"""4-3. 크루스칼 - 모든 노드 연결
import sys
def find_parent(parent, x):
"""
자기가 속한 최종 부모 찾기
:param parent:
:param x:
:return:
"""
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
"""
두 원소 합치기 - 부모 동일
:param parent:
:param a:
:param b:
:return:
"""
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, sys.stdin.readline().split()) # 노드 개수, 간선 개수
parent = [0] * (v + 1)
edges = []
result = 0
# 1. 부모 저장 테이블 - 자기 자신으로 세팅
for i in range(1, v + 1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, sys.stdin.readline().split())
edges.append((cost, a, b))
# 2. 간선 그래프를 비용에 따른 오름차순으로 설정. 그리디 - 정렬 필요
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) # 연결된 노드 최종 비용
"""
크루스칼 알고리즘
[Input Example 1]
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25
[Output Example 1]
159
"""4-4. 위상정렬 - 순서
from collections import deque
import sys
v, e = map(int, sys.stdin.readline().split()) # 노드 수, 간선 수
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
for _ in range(e):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b) # a > b
indegree[b] += 1 # 진입 차수
def topology_sort():
result = []
q = deque()
# 1. 진입차수가 0인 모든 노드를 큐에 넣는다.
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]:
# 2. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
indegree[i] -= 1
# 3. 새롭게 진입차수가 0이된 노드를 큐에 넣기
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
topology_sort()
"""
위상 정렬 알고리즘
[Input Example 1]
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
[Output Example 1]
1 2 5 3 6 4 7
"""