스파르타코딩클럽 강의
플로이드-워셜 알고리즘
- 다익스트라: 출발점을 정했을 때 다른 노드에 이르는 최단거리.
- 플로이드-워셜: 모든 지점에서 다른 모든 지점까지 최단거리.
a에서 b로 가는 거리: (a에서 b로 다이렉트로 가는 거리)와 (a에서 k를 거쳐서 b로 가는 거리)
중 최솟값이다.
k: 몇 번 거치는지 (0은 다이렉트)
구현
# 4 # 노드의 갯수
# 7 # 간선의 갯수
# 1 2 4 # 1에서 2로 가는 비용은 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2
INF = int(1e9)
def floyd_warshall(graph):
N = len(graph)
# 전부 무한대로 초기화
dist = [[INF] * (N + 1) for _ in range(N + 1)]
# 자기 자신으로 가는 경우는 0
for idx in range(1, N + 1):
dist[idx][idx] = 0
# 모든 노드의 대해서 각각의 시작점과 인접배열을 잡고
for start, adjs in graph.items():
# 인접배열에 있는 노드와 비용을 잡아서
for adj, d in adjs:
# 시작점의 인접노드들에는 각 비용을 저장
dist[start][adj] = d
# 여기까지 모든 노드의 k = 0인 경우를 초기화
# 위의 플로이드-워셜 점화식 구현 (k, a, b 순서)
for k in range(1, N + 1):
for a in range(1, N + 1):
for b in range(1, N + 1):
# a에서 b로 가는 거리는 다이렉트로 가는 거리와 k를 거쳐서 가는 거리 중 최솟값이다
dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])
return dist
import sys
from collections import defaultdict
from pprint import pprint
from min_cost.floyd_warshall import floyd_warshall
with open('testcase_fw.txt') as f:
sys.stdin = f
input = sys.stdin.readline
N = int(input())
M = int(input())
graph = defaultdict(list)
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
pprint(floyd_warshall(graph))시간복잡도
시간복잡도가 O(V^3)으로 좋은 편은 아니지만 모든 정점(노드)에 대해서 다른 모든 정점(노드)에 이르는 최소 비용을 구할 수 있기 때문에 간간히 쓰임.
예제
화성 탐사 (다익스트라. 최단 경로 구하기)
# 3 => 테스트 케이스 3개
# 3 => 그래프의 사이즈
# 5 5 4
# 3 9 1
# 3 2 7 => 그래프의 값
# 5
# 3 7 2 0 1
# 2 8 0 9 1
# 1 2 1 8 1
# 9 8 9 2 0
# 3 6 5 1 5
# 7
# 9 0 5 1 1 5 3
# 4 1 2 1 6 5 3
# 0 7 6 1 6 8 5
# 1 1 7 8 3 2 3
# 9 4 0 7 6 4 1
# 5 8 3 2 4 8 3
# 7 4 8 4 8 3 4
def mars(graph):
# 상,하,좌,우의 인덱스
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
N = len(graph)
# dist 2차원 배열은 각 노드의 비용이 저장되어있고 이 비용은 방문할 때마다 누적됨. 초기설정은 무한대
dist = [[INF] * N for _ in range(N)]
# 다음 최소비용 노드를 저장하는 큐
q = []
# 첫 값은 시작점이므로 그래프의 첫 번째 값을 저장
dist[0][0] = graph[0][0]
# 그래프의 첫 번째 값과 row, col 값을 묶어서 q에 삽입
heapq.heappush(q, (graph[0][0], 0, 0)) # 누적비용, row, col
# q에 요소가 있는 동안
while q:
# 누적 비용, row, col을 q에서 추출
acc, r, c = heapq.heappop(q)
# 이미 방문한 곳이면 패스
if dist[r][c] < acc:
continue
# 상, 하, 좌, 우의 값을 더해서 비교
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# nr과 nc가 그래프/dist의 범위 내에 있다면
if 0 <= nr < N and 0 <= nc < N:
# 현재 노드까지의 비용과 다음 노드의 비용을 더해서
cost = dist[r][c] + graph[nr][nc]
# 그 더한 값이 dist의 다음 노드의 비용보다 작다면
if cost < dist[nr][nc]:
# 다음 노드의 비용을 새로 구한 값으로 업데이트
dist[nr][nc] = cost
# 비용, 다음 노드의 row, 다음 노드의 col을 묶어서 q에 삽입
heapq.heappush(q, (cost, nr, nc))
# 최종적으로 마지막 요소의 값 반환
return dist[N - 1][N - 1]
import sys
from min_cost.dijkstra import mars
with open('testcase_mars.txt') as f:
sys.stdin = f
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
graph = []
for __ in range(N):
graph.append(list(map(int, input().split())))
print(mars(graph))숨바꼭질 (다익스트라. 최단 경로의 최댓값, 갯수 구하기)
# 6 7 => 노드갯수 간선갯수
# 3 6
# 4 3
# 3 2
# 1 3
# 1 2
# 2 4
# 5 2
def hide(graph):
N = len(graph)
dist = [INF for _ in range(N + 1)] # 1번 ~ N번까지
q = []
dist[0] = dist[1] = 0
heapq.heappush(q, (0, 1))
while q:
acc, cur = heapq.heappop(q)
if dist[cur] < acc:
continue
for adj in graph[cur]:
# 이동을 몇 번 하는지 구하는 것이기 때문에 1만큼 증가시키면 됨
cost = acc + 1
if cost < dist[adj]:
dist[adj] = cost
heapq.heappush(q, (cost, adj))
# 첫 번째부터 셌을 때 최댓값 구하기
max_dist = max(dist[1:])
# dist의 처음부터 끝까지 반복하면서 최댓값일 때만 1을 기록하고 다 더해서 갯수 구하기
cnt = sum([1 for idx in range(1, N + 1) if dist[idx] == max_dist])
# dist.index(max_dist): max_dist가 나온 첫 번째 인덱스
return dist.index(max_dist), max_dist, cnt
import sys
from collections import defaultdict
from min_cost.dijkstra import hide
with open('testcase_hide.txt') as f:
sys.stdin = f
input = sys.stdin.readline
N, M = map(int, input().split())
graph = defaultdict(list)
for _ in range(M):
a, b = map(int, input().split())
# 그래프를 서로 연결
graph[a].append(b)
graph[b].append(a)
# 6 7 => 노드갯수 간선갯수
# [1]: 3, 2
# [2]: 4, 3, 5
# [3]: 6, 2, 4
# [4]: 3, 2
# [5]: 2
# [6]: 3
print(hide(graph)) # (4, 2, 3)플로이드
# 5 # 노드 갯수
# 14 # 간선 갯수
# 1 2 2 # 1에서 2로 가는 비용은 2
# 1 3 3
# 1 4 1
# 1 5 10
# 2 4 2
# 3 4 1
# 3 5 1
# 4 5 3
# 3 5 10
# 3 1 8
# 1 4 2
# 5 1 7
# 3 4 2
# 5 2 4
with open('testcase_floyd.txt') as f:
INF = int(1e9)
sys.stdin = f
input = sys.stdin.readline
N = int(input())
M = int(input())
dist = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
dist[i][i] = 0
# 다이렉트로 연결된 노드들에 한해서 비용 저장
for _ in range(M):
a, b, c = map(int, input().split())
# 비용(c)를 [a][b]에 저장 ([a][b]는 현재 무한대)
if c < dist[a][b]:
dist[a][b] = c
# 중간 기착 지점(k)을 1부터 N까지 반복
for k in range(1, N + 1):
for a in range(1, N + 1):
for b in range(1, N + 1):
# 점화식
dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])
1번째 노드부터 매 줄을 출력
for row in dist[1:]:
# row의 1번째 요소부터 끝까지 돌면서 무한대면 0, 아니면 그 숫자를 문자열로 바꿔서 리스트에 저장 후 리스트의 요소를 띄어쓰기로 나누고 출력
print(' '.join([str(el) if el != INF else '0' for el in row[1:]]))정확한 순위
내 위에 몇 명, 내 아래 몇 명인지 구하는 것.
다른 정점으로 갈 수만 있다면 그 정점들은 내 아래.
다른 정점들이 나한테 올 수 있다면 그 정점들은 내 위.
# 6 6 # 노드개수 간선개수
# 1 5 # 1에서 5로 갈 수 있다 (비용 x)
# 3 4
# 4 2
# 4 6
# 5 2
# 5 4
with open('testcase_rank.txt') as f:
print("*" * 80, f.name)
INF = int(1e9)
sys.stdin = f
input = sys.stdin.readline
N, M = map(int, input().split())
dist = [[INF] * (N + 1) for _ in range(N + 1)]
for idx in range(1, N + 1):
dist[idx][idx] = 0
for _ in range(M):
a, b = map(int, input().split())
# 비용은 1 (갈 수 있다)
dist[a][b] = 1
# 플로이드-워셔 알고리즘
for k in range(1, N + 1):
for a in range(1, N + 1):
for b in range(1, N + 1):
dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])
result = 0
for cur in range(1, N + 1):
cnt = 0
# 현재 노드(cur)를 기준으로,
# 다른 노드(node)로 갈 방법이 있는지 센다.
for node in range(1, N + 1):
if dist[cur][node] != INF or dist[node][cur] != INF:
cnt += 1
# 모든 노드에 대해 갈 수 있다면 순위를 아는 것.
if cnt == N:
result += 1
print(result)페어 프로그래밍
문제풀이
1. 하노이 탑 이동 순서
풀이
n개의 원반을 기둥C으로 옮기려면 (1) n번째 원반을 제외한 원반들을 기둥B로 옮기고, (2) n번째 원반을 기둥C로 옮긴 다음 (3) 기둥B의 원반을 전부 기둥C로 옮긴다.
(1)을 재귀적으로 실행하고 (그림의 파란색, 분홍색 부분)
(2)을 실행 후 (꼭대기)
(3)을 재귀적으로 실행한다. (그림의 초록색 부분)
참고) 얄팍한 코딩사전 - 재귀함수가 뭔가요? (Feat. 하노이의 탑)
전체 코드
N = int(input())
def hanoi(n, start, end):
if n == 0: return
hanoi(n-1, start, 6 - start - end) # (1)
print(start, end) # (2)
hanoi(n-1, 6 - start - end, end) # (3)
print(2 ** N - 1)
hanoi(N, 1, 3)2. 좌표 정렬하기 2
풀이
- x,y를 입력받아 배열에 y,x로 삽입
- 배열 정렬 ([0]번째 인덱스(y) 기준)
- 정렬된 배열을 [1], [0] 순으로 출력
전체 코드
n = int(input())
arr = []
for i in range(n):
x, y = map(int, input().split())
arr.append([y, x])
arr.sort()
for i in arr:
print(i[1], i[0])3. 통계학
풀이
avg: 산술평균
med: 중앙값
mod: 최빈값(중복 시 2번째로 작은 값)
rng: 범위
- N개 만큼 입력받은 값을 배열에 저장
- 배열 정렬
- 정렬된 배열의 산술평균, 중앙값, 최빈값, 범위 계산
3-1. 산술평균: 배열 요소들의 합의 평균 (반올림): round(sum(lst) / N)
3-2. 중앙값: 배열의 중간 위치의 요소: lst[(N-1)//2]
3-3. 최빈값: Counter 클래스의 most_common 함수를 이용해 최빈값 2개까지 계산.
3-4. 범위: 마지막 요소와 첫 번째 요소의 차
- Counter(lst): 딕셔너리 형태로 저장됨 => {배열의 요소 : 배열 내 요소의 횟수}
- Counter(lst).most_common(2): 리스트에 담긴 튜플 형태로 저장됨 => [(가장 많이 나타나는 값, 횟수), (2번째로 많이 나타나는 값, 횟수)].
- most_common의 매개변수는 몇 개의 튜플을 받을 지 지정.
이 때 최빈값이 같다면 자동으로 정렬됨
전체 코드
from collections import Counter
N = int(input())
lst = []
for i in range(N):
lst.append(int(input()))
lst.sort()
avg = round(sum(lst) / N)
med = lst[(N-1)//2]
if N == 1:
mod = lst[0]
else:
duplicates = Counter(lst).most_common(2)
mod = duplicates[1][0] if duplicates[0][1] == duplicates[1][1] else duplicates[0][0]
rng = lst[-1] - lst[0]
print(avg, med, mod, rng, sep='\n')
COYG🔴⚪