💎 개요
다시 일주일만의 이코테 정리하기 게시글이다. 곧 벌써 8월이 다가오고 코딩테스트를 준비해야하는 기간이 얼마 남지 않은 것 같다. 이코테 정리를 최대한 마무리하고 문제 풀이 양을 늘리면서 알고리즘에 좀더 익숙해지고 파이썬을 활용한 코테 준비에 박차를 가해보고자 한다!!
이코테에 남은 유튜브 영상 내용들을 정리하고 앞으로는 velog에 개발, 알고리즘 관련 지식과 함께 기획적인 부분들(PM)을 정리하여 게시해보고자 노력할 예정이다.
참고 강의 링크! 👉 https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
💎 알고리즘
🍫 최단 경로 알고리즘
최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘
문제 상황
- 한 지점에서 다른 한 지점까지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로
각 지점은 그래포에서 노드로 표현 하고 연결된 도로는 간선으로 표현
다익스트라 : 특정한 노드에서 출발해서 다른 모든 노드로 가는 최단 경로
→ 음의 간선이 없을 때 정상적 동작(그리디 알고리즘으로 분류)
→ 매 상황에서 가장 비용이 적은 노드를 선택함!!
다익스트라 동작 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문 하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 3, 4번 과정을 반복
다익스트라 특징
- 그리디 알고리즘
- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 바뀌지 않음(한 단계당 하나의 노드에 대한 최단 거리 확실히 찾음)
- 테이블에 각 노드까지의 최단 거리 정보가 저장됨
- O(V)번 걸쳐서 최단거리 탐색
- O(v^2)의 시간 복잡도 → 개선 필요
- 우선순위 큐를 이용하여 개선
우선 순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
힙 : 최소 힙과 최대 힙
→ 삽입 시간과 삭제 시간이 O(logN)
import heapq
# 최소 힙 (오름차순)
def minheapsort(iterable):
h = []
result = []
for value in iterable:
heapq.heappush(h, value)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
# 최대 힙 (내림차순)
def maxheapsort(iterable):
h = []
result = []
for value in iterable:
heapq.heappush(h, -value)
for i in range(len(h)):
result.append(-heapq.heappop(h))
return result(다익스트라에서는 최소힙을 사용하여 구현한다!!)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
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 = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])힙 자료구조를 이용하는 다익스트라 알고리즘 시간 복잡도는 O(ElogV)
노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V이상의 횟수로는 처리되지 않음
결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대 간선의 개수(E)만큼 연산 수행
플로이드 워셜 : 모든 노드에서 다른 모든 노드까지의 최단 경로 모두 계산
- 거쳐가는 노드를 기준으로 알고리즘 수행
- 2차원 테이블에 최단 거리 정보 저장
- 다이나믹 프로그래밍 유형 속함
- 특정 노드 k를 거쳐가는 경우를 확인
- Dab = min(Dab, Dak + Dkb)
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
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):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == 1e9:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()- 알고리즘을 N번의 단계로 수행하고 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로 고려 따라서 시간 복잡도는 O(N^3) → 노드의 갯수가 약 500개 정도일때에만 적절하게 고려 가능함
🍫 기타 그래프 이론
서로소 집합 : 공통 원소가 없는 두 집합
ex) {1, 2} {3, 4}
서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 합집합 : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- 찾기 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- 합치기 찾기 자료구조라고 불리기도 함(Union Find)
- 루트 노드에 즉시 접근할 수 없어서 부모 테이블을 계속해서 확인하며 거슬러 올라가야함
- 합집합 연산이 편향되게 이루어지면 찾기 함수가 비효율적으로 작동함.
- 따라서 경로 압축 기법을 이용하여 찾기 함수를 재귀적으로 호출하고 부모 테이블 값에 바로 갱신해봄.
# 특정 원소가 속한 집합을 찾기
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) # 부모 테이블 초기화하기
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# Union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
print(find_parent(parent, i), end=' ')
print()
# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
print(parent[i], end=' ')서로소 집합을 활용한 사이클 판별 : 무방향 그래프 내에서의 사이클을 판별할 수 있음
- 각 간선을 하나씩 확인하며 두 노드의 루트 노드 확인
- 루트 노드가 서로 다르면 두 노드에 대하여 합집합 연산 수행
- 루트 노드가 같으면 사이클 발생한 것
- 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정 반복
# 특정 원소가 속한 집합을 찾기
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) # 부모 테이블 초기화하기
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else:
union_parent(parent, a, b)
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")신장 트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분그래프 의미
→ 모든 노드가 포함되어 서로 연결되어 사이클이 존재하지 않는 것은 트리의 조건이기도 함!!
최소 신장 트리 : 최소한의 비용으로 구성되는 신장트리(전체 노드가 서로 연결되게 하게 그 간선의 크기가 최소가 될 수 있도록)
크루스칼 알고리즘
- 그리디 알고리즘
- 동작 방식
- 간선 데이터 비용에 따라 오름차순 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는 경우는 최소 신장트리에 포함
- 사이클이 발생하면 최소 신장트리에 포함시키지 않음
- 모든 간선에 대하여 2번 과정 반복 수행
- 간선이 E개 일 때 시간 복잡도 O(ElogE) 시간 복잡도
- 간선을 정렬하는 부분에서 가장 많은 시간 요구됨
# 특정 원소가 속한 집합을 찾기
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)위상 정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 의미
진입 차수 : 특정한 노드로 들어오는 간서의 개수
진출 차수 : 특정한 노드에서 나가는 간선의 개수
위상정렬
- 큐를 이용하는 위상 정렬 알고리즘
- 진입차수가 0인 모든 노드를 큐에 넣는다
- 큐가 빌 때까지 다음의 과정을 반복함
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
- 새롭게 진입차수가 0이 된 노드를 큐에 넣음
- 여러가지 답이 존재할 수 있음
- 모든 원소 방문 전에 큐가 비면 사이클이 존재한다고 볼 수 있음
- 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있음
- O(V + E)의 시간 복잡도
from collections import deque
# 노드의 개수와 간선의 개수를 입력 받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i 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 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상 정렬을 수행한 결과 출력
for i in result:
print(i, end=' ')
topology_sort()🍫 기타 알고리즘
소수 : 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수
→ 자연수가 소수인지 아닌지 판별하는 문제가 자주 출제됨
기본적인 알고리즘은 모든 자연수에 대해 연산을 수행해야 하므로 시간 복잡도는 O(X)임
약수의 성질을 이용하면 시간 단축 가능!
→ 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 성질 이용
import math
def is_prime_number(x):
for i in range(2, int(math,sqrt(x)) + 1):
if x % i == 0:
return False
return True
이렇게 하면 시간 복잡도 O(N^1/2)
다수의 소수 판별하는 방법은 → 에라토스테네스의 체 알고리즘 이용
- 2부터 N까지의 모든 자연수를 나열
- 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
- 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거x)
- 더이상 반복하지 못할 때까지 2,3번 과정을 반복
import math
n = 1000
array [True for i in range(n + 1)]
for i in range(2, int(math.sqrt(n) + 1):
if array[i] == True
j = 2
while i * j <= n:
array[i * j] = False
j += 1
for i in range(2, n + 1)
if array[i]:
print(i, end=' ')- 시간복잡도는 O(NloglogN) 선형 시간에 가까울 정도로 매우 빠름
- 각 자연수에 대한 소수 여부를 저장해야하므로 메모리가 굉장히 많이 필요
투 포인터 알고리즘 : 리스트에 순차적으로 접근해야할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘
- 시작점과 끝점 두개 이용
- 특정한 합을 가지는 부분 연속 수열같은 문제에 이용
- 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 함
- 현재 부분 합이 M과 같다면 카운트
- 현재부분합이 M보다 작다면 end 1증가
- 현재 부분 합이 M보다 크거나 같다면 start 1증가
- 모든 경우를 확인할 때까지 2번부터 4번까지의 과정 반복
n = 5
m = 5
data = [1, 2, 3, 2, 5]
count = 0
interval_sum = 0
end = 0
for start in range(n):
while interval_sum < m && end < n:
interval_sum += data[end]
end += 1
if interval_sum == m:
count += 1
interval_sum -= data[start]
print(count)구간 합 : 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 구하는 문제
- N개의 정수로 구성된 수열
- M개의 쿼리 정보
- 각 쿼리는 left right구성
- 각 쿼리에 대하여 [Left, Right] 구간에 포함된 데이터들의 합을 출력해야함
- 수행시간 제한은 O(N + M)
접두사 합 이용하기 → 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓는 것
- n개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장
- P[Right] - P[Left - 1]
n = 5
data = [10, 20, 30, 40, 50]
sum_value = 0
prefix_sum = [0]
for i in data:
sum_value += 1
prefix_sum.append(sum_value)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])🍫 개발형 코딩 테스트
정해진 목적에 따라서 동작하는 완성된 프로그램을 개발하는 것을 요구하는 코딩 테스트 유형
- 완성도 높은 하나의 프로그램 개발
- 모듈을 적절히 조절하는 능력 요구
- 분야에 따라 상세 요구하는 사항이 다를 수 있음!
서버 클라이언트 : 클라이언트가 요청(request)를 보내면 서버가 응답
클라이언트 = 고객
- 서버로 요청을 보내고 응답 도착할 때까지 기다림
- 서버로부터 응답을 받은 뒤에는 서버의 응답을 화면에 출력
- 웹브라우저 : 서버로부터 받은 HTML, CSS코드를 화면에 적절한 형태로 출력
- 게임앱 : 서버로부터 받은 경험치, 친구 귓속말 정보 등을 화면에 적절한 형태로 출력
서버 = 서비스 제공자
- 클라이언트로부터 받은 요청을 처리해 응답을 전송
- 웹 서버 : 로그인 요청을 받아 아이디와 비밀번호가 정확한지 검사하고 그 결과를 전송
HTTP : 웹상에서 데이터를 주고받기 위한 프로토콜을 의미
- 보통은 웹문서를 주고받는 데 사용
- 클라이언트는 요청의 목적에 따라서 HTTP 메서드를 이용해 통신을 진행
- HTTP 메서드
- GET : 특정한 데이터의 조회 - 특정 페이지 접속, 정보 검색
- POST : 특정한 데이터의 생성 요청 - 회원가입, 글쓰기
- PUT : 특정한 데이터의 수정 요청- 회원 정보 수정
- DELETE : 특정한 데이터의 삭제 요청 - 회원 정보 삭제
HTTP는 GET, POST, PUT, DELETE 등의 다양한 HTTP 메서드를 지원한다
근데 저마다 다른 방식으로 개발하면 문제가 되서 기준이 되는 아키텍처 필요
→ REST의 등장 배경!!
REST는 각 자원에 대하여 자원의 상태에 대한 정보를 주고받는 개발 방식 의미
- 자원 : URI를 이용
- 행위: HTTP 메서드 이용
- 표현 : 페이로드 이용
API(Application Programming Interface) : 프로그램이 상호 작용하기 위한 인터페이스 의미
REST API : REST 아키텍처를 따르는 API 의미
REST API 호출 : REST 방식을 따르고 있는 서버에 특정한 요청을 전송하는 것을 의미
JSON : 데이터를 주고받는데 사용하는 경량의 데이터 형식(키와 값의 쌍으로 이루어진 데이터 객체 저장)
🍫 주요 코딩테스트 알고리즘
💡 우선순위 큐와 힙
우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
→ 우선순위에 따라 처리하고 싶을 때 사용!!
구현 방법
1. 단순히 리스트를 이용하여 구현
2. 힙을 이용하여 구현
| 우선순위 큐 구현 방식 | 삽입시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하여 → 시간 복잡도 O(NlogN)
힙의 특징
- 완전 이진 트리 자료구조
- 항상 루트노드를 제거
- 최소 힙
- 루트 노드가 가장 작은 값을 가짐
- 따라서 값이 작은 데이터가 우선적으로 제거됨
- 최대 힙
- 루트 노드가 가장 큰 값을 가짐
- 따라서 값이 큰 데이터가 우선적으로 제거됨
완전 이진 트리 : 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리
최소 힙 구성 함수 : Min-Heapify()
원소가 제거될 때 O(logN)의 시간 복잡도로 힙 성질을 유지하고 루트 노드에서부터 하향식으로 Heapify()를 진행
💡 트리
트리 : 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
- 루트 노드 : 부모가 없는 최상위 노드
- 단말 노드 : 자식이 없는 노드
- 크기 : 트리에 포함된 모든 노드의 개수
- 깊이 : 루트 노드부터의 거리
- 높이 : 깊이 중 최댓값
- 차수 : 각 노드의 자식방향 간선 개수
기본적으로 트리의 크기가 N이면 전체 간선의 개순는 N - 1개
이진 탐색 트리 : 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
- 부모 노드보다 왼쪽 자식 노드가 작음
- 부모 노드보다 오른쪽 자식 노드가 큼
트리의 순회 : 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법 의미
→ 트리의 정보를 시각적으로 확인
- 전위 순회 : 루트 먼저 방문
- 중위 순회 : 왼쪽 자식 → 루트 방문
- 후위 순회 : 오른쪽 자식 → 루트 방문
💡 벨만 포드 알고리즘
음수 간선이 포함된 상황에서의 최단 거리 문제에 적용
→ 음수 간선의 순환이 포함되어 있으면 음의 무한인 노드가 발생할 수 있음!!
- 모든 간선이 양수인 경우
- 음수 간선이 있는 경우
- 음수 간선 순환은 없는 경우
- 음수 간선 순환이 있는 경우
벨만 포드 최단경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있음
- 음수 간선의 순환을 감지할 수 있음
- 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘 보다 좀 느림
- 출발 노드를 설정
- 최단 거리 테이블을 초기화함
- 다음 과정 N - 1번 반복
- 전체 간선 E개를 하나씩 확인
- 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
음수 간선 순환이 발생하는지 체크하고 싶으면 3번 과정 한번 더 수행하기.
→ 이 때 최단 거리 테이블이 갱신되면 음수 간선 순환이 존재하는 것.
다익스트라는 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
→ 음수 간선이 없다면 최적의 해 찾음
벨만 포드는 매번 모든 간선 전부 확인
→ 다익스트라 알고리즘에서 최적의 해를 항상 포함
→ 좀 시간이 걸려도 음수 간선 순환을 탐지할 수 있음
import sys
input = sys.stdin.readline
INF = int(1e9)
def bf(strat):
dist[start] = 0
for i in range(n):
for j in range(m):
cur = edges[j][1]
next_node = edges[j][1]
cost = edges[j][2]
if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
dist[next_node] = dist[cur] + cost
if i == n - 1:
return True
return False
n, m = map(int, input().split())
edges = []
dist = [INF] * (n + 1)
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a,b,c))
negative_cycle = bf(1)
if negative_cycle:
print("-1")
else :
for i in range(2, n + 1):
if dist[i] == INF:
print("-1")
else:
print(dist[i])💡 바이너리 인덱스 트리
바이너리 인덱스 트리(펜윅 트리) : 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결
- 정수에 따른 2진수로 표기
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
edges.append((a, b, c))
def bf(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
# 전체 n - 1번의 라운드(round)를 반복
for i in range(n):
# 매 반복마다 "모든 간선"을 확인하며
for j in range(m):
cur_node = edges[j][0]
next_node = edges[j][1]
edge_cost = edges[j][2]
# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
distance[next_node] = distance[cur_node] + edge_cost
# n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
if i == n - 1:
return True
return False
# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드
if negative_cycle:
print("-1")
else:
# 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
for i in range(2, n + 1):
# 도달할 수 없는 경우, -1을 출력
if distance[i] == INF:
print("-1")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])💡 최소 공통 조상 알고리즘
- 모든 노드에 대한 깊이 계산
- 최소 공통 조상을 찾을 두 노드 확인
- 먼저 두 노드의 깊이가 동일하도록 거슬러 올라감
- 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감
- 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복
깊이 계산 → DFS이용
매 쿼리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도 요구됨
→ 따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(NM)임
2의 제곱 형태로 거슬러 올라가도록 하면 O(logN)의 시간 복잡도를 보장할 수 있음
→ 메모리를 조금 더 사용하여 각 노드에 대하여 2^i 번 째 부모에 대한 정보를 기록
import sys
input = sys.stdin.readline # 시간 초과를 피하기 위한 빠른 입력 함수
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정
LOG = 21 # 2^20 = 1,000,000
n = int(input())
parent = [[0] * LOG for _ in range(n + 1)] # 부모 노드 정보
d = [0] * (n + 1) # 각 노드까지의 깊이
c = [0] * (n + 1) # 각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)] # 그래프(graph) 정보
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
c[x] = True
d[x] = depth
for y in graph[x]:
if c[y]: # 이미 깊이를 구했다면 넘기기
continue
parent[y][0] = x
dfs(y, depth + 1)
# 전체 부모 관계를 설정하는 함수
def set_parent():
dfs(1, 0) # 루트 노드는 1번 노드
for i in range(1, LOG):
for j in range(1, n + 1):
parent[j][i] = parent[parent[j][i - 1]][i - 1]
# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
# b가 더 깊도록 설정
if d[a] > d[b]:
a, b = b, a
# 먼저 깊이(depth)가 동일하도록
for i in range(LOG - 1, -1, -1):
if d[b] - d[a] >= (1 << i):
b = parent[b][i]
# 부모가 같아지도록
if a == b:
return a;
for i in range(LOG - 1, -1, -1):
# 조상을 향해 거슬러 올라가기
if parent[a][i] != parent[b][i]:
a = parent[a][i]
b = parent[b][i]
# 이후에 부모가 찾고자 하는 조상
return parent[a][0]
set_parent()
m = int(input())
for i in range(m):
a, b = map(int, input().split())
print(lca(a, b))💎 정리
이렇게 이코테 내용들을 다 정리해보았다. 문제를 같이 병행하면서 제대로 풀지 못해서 정리를 마치고 각 내용들을 돌려가면서 풀어볼 예정이다. 여행을 다녀오면서 좀 생각이 많았는데, 조급해하지 않아도 내가 앞으로 뭘 할지를 감을 잡기가 굉장히 힘들었던 것 같다. 분명히 여러가지를 병행하면서 하고 있는데 내가 앞으로 뭘 하고 싶은지 딱 정하기가 힘든 느낌,,,?
암튼 현재 내가 하고 있는게 코테준비, 피그마 디자인, 기획, 여러 프로젝트 운영을 하고 있는데 방학내에 마무리할 수 있는게 있다면 최대한 마무리해보도록 하고 요새 좀 소홀했던 개발 공부도 다시 시작해볼 예정이다.
앞으로 남은 방학 일정들을 소화해볼려면 개발도 손놓지 않으면서도 이것저것 자소서랑 포트폴리오도 채워보도록 하자!!
아참 영어 회화는 제때제때 하자... 방학안에는 오픽 해치웠으니 토스 꼭 해두자!!
화팅~!
