[코딩테스트] 이것이 취업을 위한 코딩테스트다 3

GGG·2022년 8월 15일
코딩테스트
0

이것이 취업을 위한 코딩테스트다

목록 보기
3/3
post-thumbnail

최단 경로

Dijkstra Algorithm - 한 노드에서 다른 노드까지 최단 거리

음의 간선(edge)가 없을 때 정상적으로 동작

  1. 출발 노드 설정
  2. 최단 거리 테이블 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 (우선순위 큐)
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  5. 위 과정에서 3, 4를 반복

우선순위 큐를 사용한 경우 O(E⋅logV)O(E\cdot log V)

  • code
    import sys
import heapq
INF = int(1e9)

n, m = map(int, input().split())
start = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    # node a to node b, cost = c
    graph[a].append((b, c))
    # adjacent list

def dijkstra(start):
    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 = 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):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

Floyd-Warshall Algorithm - 모든 지점에서 다른 모든 지점까지의 거리

Dab=min(Dab,Dak+Dkb)D_{ab} = min(D_{ab}, D_{ak} + D_{kb})

  • code
    import sys
INF = float('inf')
n, m = map(int, sys.stdin.readline().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
    graph[a][a] = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = c
		# adjacent matrix

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 i in range(1, n+1):
    print(*graph[i][1:])

문제

  • 미래 도시
    import sys

def solution(n, m, x, k, graph):
    for l_ in range(n+1):
        for a in range(n+1):
            for b in range(n+1):
                graph[a][b] = min(graph[a][b], graph[a][l_] + graph[l_][b])
    return graph[1][k] + graph[k][x] if graph[1][k] + graph[k][x] < int(1e9) else -1

if __name__ == "__main__":
    INF = int(1e9)
    n, m = map(int, sys.stdin.readline().split())
    graph = [[INF] * (n+1) for _ in range(n+1)]
    for a in range(n+1):
        graph[a][a] = 0
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a][b] = 1
        graph[b][a] = 1
    x, k = map(int, sys.stdin.readline().split())
    print(solution(n, m, x, k, graph))
  • 전보
    import sys
import heapq

def solution(n, m, c, adj_list):
    INF = int(1e9)
    distance = [INF] * (n+1)
    distance = dijkstra(adj_list, distance, c)

    dist_eff = [x for x in distance if x != INF and x != 0]
    return len(dist_eff), max(dist_eff)

def dijkstra(adj_list, distance, start):
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, now = heapq.heappop(q)
        if cost > distance[now]:
            continue
        distance[now] = cost

        for i in adj_list[now]:
            if cost + i[1] < distance[i[0]]:
                distance[i[0]] = cost + i[1]
                heapq.heappush(q, (distance[i[0]], i[0]))

    return distance

if __name__ == "__main__":
    n, m, c = map(int, sys.stdin.readline().split())
    adj_list = [[] for _ in range(n+1)]
    for _ in range(m):
        x, y, z = map(int, sys.stdin.readline().split())
        adj_list[x].append((y, z))
    print(*solution(n, m, c, adj_list))

그래프 알고리즘

Adjacent matrix: V2V^2 메모리 - 다익스트라. 노드가 비교적 많은 경우에도 사용 가능.

Adjacent list: E2E^2 메모리 - 플로이드 워셜. 노드가 적은 경우 사용 가능.

서로소 집합 - 공통원소가 없는 두 집합

union(합집합) → 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

find(찾기) → 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

  • 코드
    import sys

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
				# return 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

# num of vertex: v, num of edge: e
v, e = map(int, sys.stdin.readline().split())
parent = list(range(v+1))

for i in range(e):
    a, b = map(int, sys.stdin.readline().split())
    union_parent(parent, a, b)

print('각 원소가 속한 집합: ', end='')
for i in range(1, v+1):
    print(find_parent(parent, i), end='')
print()

print('parent table: ')
print(*parent)

트리 자료구조 사용. 노드의 개수가 V, V-1 개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축 방법을 적용한 시간 복잡도 O(V+M(1+log2−M/VV))O(V+M(1+log_{2-M/V}V))

무방향 그래프 내에서 사이클 여부를 판단할 때 사용 할 수 있음.

  • 사이클 여부 판단 코드
    import sys

def find_parent(parent, x):
    if parent[x] != x:
        # root node finding
        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

# num of vertex: v, num of edge: e
v, e = map(int, sys.stdin.readline().split())
parent = list(range(v+1))

for i in range(e):
    a, b = map(int, sys.stdin.readline().split())
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

if cycle:
    print("cycle")
else:
    print("none")

신장트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

최종적으로 신장트리에 포함되는 간선의 개수는 노드의 개수 -1개이다.

크루스칼 알고리즘 - O(E⋅logE)O(E \cdot logE)

  1. 간선 데이터를 비용에 따라 오름차순으로 정렬
  2. 간선을 하나씩 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
    1. 사이클 발생하지 않는 경우 최소 신장 트리에 포함
    2. 발생하는 경우 포함시키지 않음
  3. 모든 간선에 대해 2의 과정 반복
  • 코드
    import sys

def find_parent(parent, x):
    if parent[x] != x:
        # root node finding
        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

# num of vertex: v, num of edge: e
v, e = map(int, sys.stdin.readline().split())
parent = list(range(v+1))

edges = []
result = 0

for i in range(e):
    a, b, cost = map(int, sys.stdin.readline().split())
    edges.append((cost, a, b))

# 1 sort
edges.sort()

# 2
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)

위상 정렬 - O(V+E)O(V+E)

방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

Indegree: 특정한 노드로 들어오는 간선의 개수

  1. 진입 차수(Indegree)가 0인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정 반복
    1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
  • 코드
    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)
    indegree[b] += 1

def topology_sort():
    result = []
    q = 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)

    print(*result)

topology_sort()

문제

  • 팀 결성
    import sys

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(a, b, parent):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, sys.stdin.readline().split())
parent = list(range(n+1))

for _ in range(m):
    o, a, b = map(int, sys.stdin.readline().split())
    if o:
        union_parent(a, b, parent)
    else:
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")
  • 도시 분할 계획
    import sys

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

v, e = map(int, sys.stdin.readline().split())
parent = list(range(v+1))

edges = []
result = 0

for _ in range(e):
    a, b, cost = map(int, sys.stdin.readline().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
        last = cost

print(result - last)
  • 커리큘럼
    import sys
import copy
from collections import deque

v = int(sys.stdin.readline())
indegree = [0] * (v+1)
graph = [[] for _ in range(v+1)]
time = [0] * (v+1)

for i in range(1, v+1):
    data = list(map(int, sys.stdin.readline().split()))
    time[i] = data[0]
    for x in data[1:-1]:
        indegree[i] += 1

def topology_sort():
    result = copy.deepcopy(time)
    q = deque([])
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        for i in graph[now]:
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    print(*(result[1:]))

topology_sort()
profile
GGG
GGG
이전 포스트

[코딩테스트] 이것이 취업을 위한 코딩테스트다 2

0개의 댓글