알고리즘 그룹액티비티6

기술1 2025. 6. 2. 12:12

1번

a) 인접 행렬의 경우 n x n의 배열이 필요해서 시간복잡도가 o(n^2) 입니다.

하지만 인접리스트의 경우 각 노드의 연결된 부분만 저장하므로 o(n+m) 입니다. 따라서 간선이 적은 sparce graph의 경우 인접리스트가 더 효율적입니다.

b) 인접행렬의 경우, 각 정점에서 다른 모든 정점을 확인해야 하므로 o(n^2)의 시간이 걸립니다. 인접리스트는 각 노드의 실제 연결된 간선만 확인하믈 o(n+m)의 시간에 탐색이 가능하기에 DFS/BFS 알고리즘의 일반적인 시간복잡도입니다.

c) 인접행렬은 n x n 배열을 재할당해야 하므로 정점 추가가 어렵고 비용이 크지만 인접리스트는 단순히 리스트에 빈 항목을 추가하면 되므로 정점 추가가 간편합니다.

2번

무방향 단순그래프란?

무방향 : 간선에 방향이 없음, 단순 : 자기 자신과 연결되는 간선이 없음, 같은 두 정점 사이에는 하나의 간선이 존재

Degree sequence

그래프의 각 정점 차수를 내림차순으로 정렬한 수열

차수 수열이 단순 그래프에서 가능한 조건

1.항등적으로 차수의 합은 짝수여야 한다.

2. Havel-Hakimi 알고리즘

Havel-Hakimi 알고리즘

1. 모든 0을 제거한다

2. 수열이 비어 있다면, 이 수열은 차수 수열이 될 수 있음

3. 수열을 내림차순으로 정렬한다.

4. 첫 번째 숫자 d를 꺼내고 제거한다. (d는 어떤 정점이 연결되어야 할 다른 정점의 수)

5. 수열의 앞에서부터 d개의 숫자를 1씩 감소시킨다.

6. 음수가 생기면, 이는 불가능한 연결을 의미하므로 수열은 불가능

7. 1~6 다시 반복

3번

무방향 그래프 : 간선에 방향이 없음 -> (u,v) = (v,u)

단순 (simple)

자기 자신과의 간선(루프) 없음
두 정점 사이의 간선은 최대 하나만 존재

가능한 간선 수 : n(n-1)/2

이 수는 단순 무방향 그래프에서 존재할 수 있는 모든 가능한 가넛ㄴ의 개수

각 간선은 존재하거나 존재하지 않을 수 있음(2가지 선택)

따라서 가능한 서로 다른 그래프의 수는

이유 : 간선이 존재하거나 존재하지 않느 두 가지 선택이 있으며, 가능한 간선의 총 개수는 (n 2) 개이기 떄문인비다.

4번

무방향 단순 그래프란?

무방향 : 간선에 방향이 없음 -> (u,v) = (v,u)
단순 : 자기 루프나 중복 간선 없음
간선 하나는 두 정점의 차수를 각각 1씩 증가시킴

차수가 홀수인 정점의 개수는 짝수이다 O

무방향 그래프에서 모든 정점의 차수의합은 항상 짝수입니다. 왜냐하면 각 간선은 두 정점에 동시에 연결되므로 차수를 두 개 증가시키는 셈입니다.

짝수는 홀수 개의 홀수 합으로는 절대 만들 수 없습니다. 홀수 개의 홀수를 더하면 항상 홀수 따라서 전체 차수의 합이 짝수이려면, 홀수 차수를 가진 정점의 개수는 반드시 짝수여야 합니다.

모든 정점의 차수의 합은 짝수이다 O

무방향 그래프에서 하나의 간선은 두 정점에 연결되므로, 총 간선이 m일 때, 차수의 총합은 2m이 되어 항상 짝수입ㄴ디ㅏ.

5번

사이클이 존재하지 않으며 n개의 정점을 가지는 무방향 그래프가 가질 수 있는 간선의 개수의 최대값은?

사이클이 없고 연결된 무방향 그래프는 트리입니다.

트리는 정점 수가 n개일 때, 항상 간선 수가 n-1개

사이클이 없는 그래프의 최대 구조는 결국 트리이므로 사이클이 없고 정점 수가 n개인 무방향 그래프의 최대 간선수는 n-1이 됩니다.

6번

(d)

C에서 G or H로 가지 않고 바로 d로 가는 back tracking 모순

7번

DAG의 정점들을 일렬로 나열한 순서를 위상정렬이라고 하며, 모든 간선에 대해서 정점 u가 v보다 먼저 나오는 순서입니다.

간선 목록

1 -> 2

1 -> 3

2 -> 4

2 -> 5

3 -> 4

3 -> 6

4 -> 5

4 -> 6

진입차수 : 해당 정점을 직접 들어오는 간선의수

진입차수가 0인 노드는 처음엔 1밖에 없습니다. 1을 먼저 출력한 뒤, 그로 인해 진입 차수가 0이 된 노드(2,3)을 선택합니다. 이후 가능한 순서를 계속 따라가며 모든 조합을 나열합니다.

가능한 위상정렬

1. 1 2 3 4 5 6

2. 1 2 3 4 6 5

3. 1 3 2 4 5 6

4. 1 3 2 4 6 5

8번

DFS를 사용하여 무방향 그래프에서 사이클이 존재하는지 검사하는 방법

무방향 그래프에서 사이클이 있는지 DFS를 이용해 판별

DFS 탐색 중에서 이미 방문한 정점을 다시 방문하게 되는 경우, 단 그것이 현재 정점의 부모가 아닐 경우 이는 사이클이 존재한다고 봅니다.

1. 모든 정점을 방문하지 않은 상태로 초기화

2. 각 정점에서 DFS를 시작

3. DFS 중 방문한 적 없는 이웃 노드이면 재귀DFS를 호출, 방문한 적 있는 이웃 노드이면 그 정점이 현재 노드의 부모가 아니라면 사이클 발견한 것

def has_cycle(graph):
    visited = set()

    def dfs(current, parent):
        visited.add(current)
        for neighbor in graph[current]:
            if neighbor not in visited:
                if dfs(neighbor, current):
                    return True
            elif neighbor != parent:
                return True  # 사이클 발견
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, None):
                return True
    return False

9번

방향 그래프에서 DFS를 이용해 사이클이 존재하는지 검사하는 문제입니다.

무방향 그래프와는 사이클 판별 기준이 다릅니다.

어떤 노드를 방문하고 아직 dfs가 끝나기 전에 (방문중일때 gray)

그 노드를 다시 방문하게 되면 사이클 존

방문 전 - white

방문 중 - gray

방문 완료 - black

1. 모든 노드를 방문 전으로 초기화

2. DFS를 시작할 때, 노드를 방문 중으로 표시

3. DFS 도중 :

이웃이 방문 중(GRAY)인 경우 -> 사이클 존재
이웃이 방문 완료(BLACK) -> 무시
이웃이 방문 전(WHITE) -> DFS 재귀 호출

4. DFS가 끝나면 현재 노드를 방문 완료 (BLACK)으로 변경

10번

MST란?

모든 정점을 연결하고
사이클이 없고
총 가중치가 최소인 트리 형태의 부 그래프

kruskal

- 사이클 없이 최소인 것부터 계속

11번

그래프 G는 연결된 무방향 가중치 그래프

모든 간선은 서로 다른 가중치를 가짐

emin = 최소 가중치 간선

emax = 최대 가중치 간선

a) MST 성질 중 하나인 "가장 가중치가 작은 간선은 반드시 MST를 포함해야 한다"는 일반적으로 사이클이 형성되지 않느 한 참입니다. 여기선 간선 가중치가 모두 다르므로, EMIN은 항상 MST에 포함됩니다. 왜냐하면 가장 작은 간선은 Kruskal에서 항상 제일 먼저 선택되기 때문입니다.

b) 만약 emax가 어떤 MST에 포함되어 있다면, 그래프 G에서 Emax를 제거하면 G는 disconnect된다 X

어떤 간선이 MST에 포함되었다고 해서, 그 간선을 제거했을 떄 반드시 그래프 전체가 연결되지 않게 된다는 보장은 없습니다.

MST에 포함된다고 하여, 원래의 전체 그래프에서 그 간선이 cut-edge는 아님

예를들어 emax는 원래 MST에 포함되었지만, G에는 그 외 다른 연결 경로가 존재할 수도 있음

c) 어떤 MST도 emax를 포함하지 않습니다 . x

emax가 반드시 MST를 포함되지 않는다는 보장X, Kruskal 가장 작은 단선 하지만 emax가 MST 구성 마지막 간선일수도

d) G는 유일한 MST를 가진다 ㅇ

조건에 모든 간선이 서로 다른 가중치를 가진다고 말했으니 MST는 항상 유일

12번

연결된 무방향 그래프 G가 있고, 모든 간선들은 서로 다른 가중치를 가집니다.

어떤 사이클 C에 속한 간선들 중에서, 가장 가중치가 작은 간선 e는 반드시 포함됩니다. 맞습니다.

왜냐하면 MST의 이론 중 하나인 사이클 속 최소 간선 포함 정리는 어떤 사이클에서 가장 가중치가 작은 간선은 반드시 MST에 포함된다는 것입니다.

MST는 사이클을 포함하지 않습니다(트리이므로)

사이클 C에서 최소 가중치 간선 e를 제외하고 나머지 간선들만으로 MST 구성 가정한다면

e는 MST가 없는 상태입니다.

그런데 e는 C에서 가장 작으므로, 현재 MST에 포함된 C의 다른 간선보다 작습니다.

이때, MST에 있는 큰 가중치 간선 하나를 e로 대체하면 더 작은 총합의 트리를 만들 수 있으며 이는 MST가 아님에 모순입니다. 따라서 e는 MST에 반드시 포함되어야 합니다.

13번

Dijkstra 알고리즘을 사용할 때, 어떤 경로가 실제로 최단 경로로 선택되는지에 대한 질문입니다.

더 짧은 경우에만 d[v]를 갱신합니다.

dijkstra 알고리즘 사용해서 하면됨

Dijkstra 알고리즘은 가중치가 있는 방향 또는 무방향 그래프에서
하나의 시작 정점 로부터 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.

단, 간선의 가중치는 음수가 없어야 합니다. (w ≥ 0

시작 정점 S에서부터 다른 정점까지의 거리를 하나씩 갱신하면서 탐색
가장 가까운 정점부터 탐색
우선순위 큐(min heap)를 사용해 거리 작은 정점을 먼저 처리

14번

모든 간선의 가중치를 각각 1만큼 증가시도 최단 경로는 바뀌지 않는다 x

🔍 반례:

A —(1)— B —(1)— C \———(3)———/

A → C 의 최단 경로: A-B-C (비용 1+1=2)
가중치 전부 +1 하면:
- A-B-C = 2+2 = 4
- A-C = 4 → 둘 다 동일
동률이면 경로 바뀔 수 있음, 또는
다른 경우에서는 실제로 바뀌기도 함

👉 최단 경로는 절대적 가중치 차이에 민감하

최단 경로는 누적 거리를 기준으로 비교
모든 간선의 가중치가 동일하게 증가하면, 모든 경로의 총 거리도 동일하게 증가
그러므로 가장 짧은경로 자체 바뀌지 않음

모든 간선의 가중치를 각각 1만큼 증가시켜도 MST는 바뀌지 않는다. X => o

MST는 전체 트리에서 가중치가 가장 작은 간선을 우선 선택
간선 가중치의 차이가 중요
모든 간선을 동일하게 증가시키면, 간선 강의 상대적 차이는 보존되지만, MST는 절대 가중치가 아닌 상대적 크기만 비교하므로 구조는 그대로 유지됨

모든 간선의 가중치에 2를 곱해도 최단 경로 바뀌지 X => o

간선 가중치 비율 곱해도 동일 비율

모든 간선의 가중치에 2를 곱해도 MST는 바뀌지 않음 ㅇ

MST는 가중치의 크기 순서만 비교
2배를 곱해도 간선 간의 상대 순서는 유지됨

15번

일반 그래프의 최장 경로는 NP-Hard

DAG는 위상 정렬을 통해 효율적 최장 경로 구할 수 있으며 DP 방식으로 최장 경로 누적 계산

1. 초기화 시작 정점 S의 거리는 0, 나머지 정점은 ㄹ최장 경로가 아직 없음

2. DAG는 사이클이 없기 때문에 위상 정렬이 가능, 위상 정렬 순서는 선행 정점이 항상 멀리 처리됨 보장

3. 최장 경로 계산

현재 정점 u에서 도달 가능한 모든 정점 v에 대해,

기존의 v까지의 거리보다 더 긴 경로가 발견되면 갱신

이 과정을 모든 정점에 대해 위상순서대로 수행

위상 정렬 순서로 진행하면, 모든 정점은 선행 정점이 먼저 처리됨 -> 사이클이 없기 대문에 선형적 순서로만 경로가 생성

따라서 각 정점은 그 이전 정점으로부터 최장 거리만 누적하면 됨

결국 각 정점까지의 최장거리 dist[v]는 시작 정점 s로부터 정점 v까지 가능한 모든 경로 중 최장 경로의 길이

알고리즘이 최장 경로를 정확히 구하는 이유는 DAG의 위상 정렬 순서를 따라 동적프로그래밍 방식으로 모든 정점까지의 최장 누적 경로 길이를 계산하기 때문입니다. 사이클이 없고, 모든 경로는 위상 순서를 따른다는 보장이 있으므로 최장 경로가 올바르게 계싼됩니다.

16번

Floyd-Warshall은 모든 정점 쌍 간의 최단 경로를 구하는 대표적인 동적 프로그래밍 알고리즘입니다.

알고리즘의 핵심은 특정 정점들을 중간 경유지로 사용할 수 있는지 여부를 점진적 고려하여서 최단 경로 갱신해야합니다.

정점 i부터 j로 가는 최단 경로는, 정점 k를 통과하지 않는 기존 경로와 정점 k를 통과하는 경로 중 더 짧은 것을 선택하면 됩니다.

최단 경로는 모든 가능한 경로 중 가중치가 최소인 것으로

우리는 정점 1 ~ k 중 일부만을 중간 경유지로 허용한 경로 집합을 생각하고, 점차적으로 더 많은 정점을 경유 가능하게 허용해갑니다.

기존경로 i -> j

새로운 후보 경로 i -> k -> j

이 둘 중 작은 값을 선택하면 k까지 고려한 최단 경로가 됩니다.

모든 정점 -> 모든 정점 최단 경로 플로이드 와샬

dijkstra는 1차원 배열을 사용했다면 floyd는 2차원 배열을 사용합니다. 모든 정점에서 모든 정점으로 가는 최단 경로를 구하기에 2차원 배열을 사용합니다.

2차원 배열을 계속해서 최단 비용으로 갱신하면서 모든 최종 비용을 다 구하는 것이며 그 반복의 기준이 바로 거쳐가는 정점이라는 특징이 있습니다.

(2->3) 으로 가는 비용이 9였는데 (2->1) + (1->3) 7 무한

이런식으로 2->1->3으로 가는 경우와 2->3의 경우를 비교해서 갱신할 필요가 있는지 없는지 보는 것이 floydwarshall입니다. 어떤 것을 거쳐가는지 보아서 비용을 갱신하는 것입니다.