자료구조와 알고리즘: 벼락치기 팩

공식 모음, 모든 주제의 핵심 풀이 단계, 연습 문제 6개가 들어 있으며 전체 풀이는 맨 뒤에 있습니다.

새 문제 강의로 돌아가기

인쇄 창에서 “PDF로 저장”을 선택하면 기기에 사본을 보관할 수 있습니다.

1공식과 풀이 방법

그래프 이론

악수 보조정리: Σ deg(v) = 2|E|
완전그래프: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
정규그래프: |E| = n·k/2
트리와 포리스트: |E| = n − 1, |E| = n − c
트리의 잎: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
오일러: 회로: 모든 차수가 짝수; 경로: 차수가 홀수인 정점이 정확히 2개
K_n의 해밀턴 회로: (n − 1)!/2
다익스트라 갱신: d(v) = min(d(v), d(u) + w(u, v))
길이 L의 보행: (Mᴸ)_ij

방법

모든 정점의 차수를 적으세요. 차수의 합은 간선 수의 두 배입니다.
오일러 문제에서는 그래프가 연결되어 있는지 확인하고 차수가 홀수인 정점의 수를 세세요.
트리에서는 간선이 n − 1개라는 사실과 악수 보조정리를 사용하세요.
다익스트라에서는 임시 거리 표를 만들고, 매 단계마다 확정되지 않은 정점 중 거리가 가장 작은 정점을 확정하세요.
최소 신장 트리는 간선을 가중치 순으로 정렬해 사이클을 만드는 간선을 건너뛰거나(크루스칼), 시작 정점에서 트리 하나를 키워 가세요(프림).

2연습 문제

1.알고리즘과 복잡도보통

점화식 T(n) = 2T(n − 1) + O(1)의 해는 무엇입니까?

AO(2ⁿ)
BO(n)
CO(n log n)
DO(n²)

2.알고리즘과 복잡도어려움

결정 불가능한 문제와 다루기 어려운 문제의 차이는 무엇입니까?

A결정 불가능한 문제는 NP에, 다루기 어려운 문제는 P에 속한다
B둘 다 그 문제에 알고리즘이 전혀 없다는 뜻이다
C결정 불가능한 문제는 모든 입력에 대한 알고리즘이 없고, 다루기 어려운 문제는 알고리즘이 있지만 너무 느리다
D다루기 어려운 문제는 어떤 알고리즘으로도 풀 수 없고, 결정 불가능한 문제는 지수 시간만 있으면 된다

3.자료구조보통

정점 V개, 간선 E개인 그래프에서 인접 리스트는 메모리를 얼마나 사용합니까?

AO(V²)
BO(V × E)
CO(V + E)
DO(E²)

4.자료구조어려움

레드-블랙 트리 규칙은 키가 n개인 트리의 높이에 대해 무엇을 보장합니까?

A높이는 최대 log₂ n + 1이다
B높이는 최대 n / 2이다
C높이는 최대 2 log₂(n + 1)이다
D높이는 정확히 log₂ n이다

5.그래프 이론보통

완전그래프 K₄의 서로 다른 해밀턴 회로는 몇 개(H)인가? 시작 정점이나 방향만 다른 회로는 같은 것으로 센다.

K₄

H =

6.그래프 이론어려움

A에서 C까지 가는 길이 3의 보행은 몇 개인가? 보행에서는 정점과 간선이 반복될 수 있다. 그 수를 N(이)라 하자.

M = 인접 행렬L = 3

N =

3용액

1.알고리즘과 복잡도

답: A · O(2ⁿ)

이것이 답인 이유

호출 수가 단계마다 두 배가 되고 단계가 n개이므로, 하노이의 탑처럼 합계는 약 2ⁿ입니다.

답

A · O(2ⁿ)

2.알고리즘과 복잡도

답: C · 결정 불가능한 문제는 모든 입력에 대한 알고리즘이 없고, 다루기 어려운 문제는 알고리즘이 있지만 너무 느리다

이것이 답인 이유

정지 문제에는 알고리즘이 전혀 없습니다. TSP 같은 NP-hard 문제는 무차별 대입으로 풀 수 있지만, 알려진 다항 시간에는 풀 수 없습니다.

답

C · 결정 불가능한 문제는 모든 입력에 대한 알고리즘이 없고, 다루기 어려운 문제는 알고리즘이 있지만 너무 느리다

3.자료구조

답: C · O(V + E)

이것이 답인 이유

각 정점에 리스트가 있고 각 간선은 한 번(방향 그래프) 또는 두 번(무방향 그래프) 나타나므로 O(V + E)입니다.

답

C · O(V + E)

4.자료구조

답: C · 높이는 최대 2 log₂(n + 1)이다

이것이 답인 이유

모든 경로에 검은 노드 수가 같고 빨간 노드는 이웃할 수 없으므로 가장 긴 경로는 가장 짧은 경로의 최대 두 배이며, 높이는 O(log n)이 됩니다.

답

C · 높이는 최대 2 log₂(n + 1)이다

5.그래프 이론

답: H = 3

오일러, 해밀턴, 트리: 연결 그래프는 모든 정점의 차수가 짝수이면 오일러 회로(모든 간선을 한 번씩 지나 출발점으로 돌아옴)를 가지고, 차수가 홀수인 정점이 정확히 두 개이면 회로가 아닌 오일러 경로를 가집니다. 이 경로는 한 홀수 정점에서 다른 홀수 정점까지 이어집니다. 해밀턴 회로는 모든 정점을 한 번씩 방문하며, K_n에는 (n − 1)!/2개가 있습니다. 정점이 n개인 트리는 간선이 n − 1개이고, 간선이 m개인 연결 그래프는 m − n + 1개의 간선을 제거한 뒤에도 신장 트리를 유지합니다.

세기

H = (4 − 1)!/2 = 6/2 = 3

답

H = 3

6.그래프 이론

답: N = 1

차수: 정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 차수의 합은 간선 수의 두 배입니다: Σ deg(v) = 2|E|(악수 보조정리). 따라서 차수가 홀수인 정점의 수는 짝수입니다. K_n은 간선이 n(n − 1)/2개이고, 정점이 n개인 k-정규그래프는 nk/2개이며, 정점이 n개인 트리는 간선이 n − 1개입니다.

인접 행렬

A: 0 1 0 0 0 0

B: 1 0 1 1 1 0

C: 0 1 0 0 1 0

D: 0 1 0 0 0 1

E: 0 1 1 0 0 1

F: 0 0 0 1 1 0

한 걸음 더

(M³)_AC = 1·0 + 0·1 + 1·0 + 1·0 + 1·1 + 0·0 = 1

답

N = 1

ExamProblems · examproblems.com/courses/data-structures-and-algorithms