JUNGLE 240401 (W02)

in Study #Jungle

KRAFTON JUNGLE Week 02

1. Keywords

다익스트라 의사코드 (Heap)

function Dijkstra(graph, start):
    // 그래프의 정점 수
    num_vertices = number of vertices in graph
    
    // 최단 거리를 저장하는 리스트. 초기에는 무한대로 설정.
    distances = [infinity] * num_vertices
    
    // 시작 정점의 최단 거리는 0으로 설정.
    distances[start] = 0
    
    // 우선순위 큐를 생성하고 시작 정점을 넣어줍니다.
    pq = priority queue  // (거리, 정점)의 튜플을 저장할 우선순위 큐
    
    pq.push((0, start))  // 시작 정점을 우선순위 큐에 넣습니다.
    
    while pq is not empty:
        // 우선순위 큐에서 가장 거리가 짧은 정점을 선택합니다.
        current_distance, current_vertex = pq.pop()
        
        // 현재 정점에 연결된 모든 정점들에 대해 최단 거리를 갱신합니다.
        for each neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            // 더 짧은 거리를 발견했을 경우 갱신합니다.
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                // 우선순위 큐에 (거리, 정점)을 넣어줍니다.
                pq.push((distance, neighbor))
    
    return distances

B-Tree의 성능

  1. 디스크 I/O 감소: 상대적으로 많은 키와 자식을 가질 수 있음. 이는 디스크 I/O 횟수를 최소화하여 데이터 접근 속도 향상
  2. 높은 효율성: 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)이며, n은 키의 수
  3. 범용성: 다양한 크기의 레코드 처리 가능.
  4. 데이터 정렬 및 범위 탐색: 정렬된 상태를 유지하므로 범위 검색이 빠르고 효율적

2. BOJ Issue

1197. 최소 스패닝 트리

MST의 이론에 대해서는 이해했지만 직접 구현하려니 난감했다..

import sys
input = sys.stdin.readline

V, E = map(int, input().split())

edges = []
for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))
edges.sort(key=lambda x: x[2])

parent = [i for i in range(V + 1)]
  • 정점 A와 B, 가중치 C를 받아온 다음 리스트에 저장한다.
  • 크루스칼 알고리즘을 활용할 것이므로 가중치 순으로 정렬한다.
def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]


def union(x, y):
    x_parent = get_parent(x)
    y_parent = get_parent(y)

    if x < y:
        parent[y_parent] = x_parent
    else:
        parent[x_parent] = y_parent


def same_parent(x, y):
    return get_parent(x) == get_parent(y)
  • get_parent(x): 입력된 원소의 부모 노드를 반환
  • union(x, y): 입력된 두 원소 x와 y가 속한 집합을 합치는 함수
  • same_parent(x, y): 입력된 두 원소가 같은 집합에 속해 있는지 여부를 반환
  • 위의 세 함수를 통해 간선을 연결할 때 사이클 여부를 체크
answer = 0
for a, b, cost in edges:
    if not same_parent(a, b):
        union(a, b)
        answer += cost

print(answer)
  • 부모가 같지 않으면 같은 그룹으로 합치고 비용을 더해준다.

2252. 줄 세우기

위의 문제와 마찬가지로 이론은 알고있지만 직접 구현하는 것이 어려웠다.

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
students = [[] for _ in range(N + 1)]
deg = [0] * (N + 1)
q = deque()
result = []

for _ in range(M):
    a, b = map(int, input().split())
    students[a].append(b)
    deg[b] += 1
  • 진입 차수를 저장할 deg 리스트 초기화
  • 각 간선에 대한 입력을 받을 때 진입 차수를 업데이트 한다.
for i in range(1, N + 1):
    if deg[i] == 0:             # 진입 차수가 0인 정점을 찾아서
        q.append(i)             # 큐에 삽입

while q:
    curr = q.popleft()          # 큐에서 정점을 하나 꺼냄
    result.append(curr)         # 꺼낸 정점을 결과 리스트에 추가

    for i in students[curr]:    # 꺼낸 정점과 연결된 정점들을 체크
        deg[i] -= 1             # 해당 정점의 진입 차수를 1 감소
        if deg[i] == 0:         # 만약 진입 차수가 0이 되면,
            q.appendleft(i)     # 해당 정점을 큐에 추가

print(*result)
  • 진입 차수가 0인 정점을 미리 큐에 삽입
  • 큐가 빌 때까지 현재 정점과 연결된 정점들의 차수를 1씩 감소시키며 차수가 낮은 정점부터 정렬해나간다.