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

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

새 문제강의로 돌아가기

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

1공식과 풀이 방법

그래프 이론

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

방법

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

2연습 문제

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

플로이드-워셜 알고리즘은 무엇을 얼마나 빠르게 계산합니까?

  1. A최소 신장 트리를 O(E log V)에
  2. B모든 정점 쌍 사이의 최단 경로를 O(V³)에
  3. C한 출발 정점에서 다른 모든 정점까지의 최단 경로를 O(V + E)에
  4. D위상 정렬 순서를 O(V²)에
2.알고리즘과 복잡도어려움

정지 문제(halting problem)가 보여 주는 것은 무엇입니까?

  1. A모든 프로그램과 입력에 대해 그것이 정지하는지를 판정할 수 있는 알고리즘은 없다
  2. B모든 프로그램은 결국 정지한다
  3. C일부 프로그램은 더 빠른 컴퓨터에서 더 빨리 실행되므로 정지 여부는 하드웨어에 달려 있다
  4. D루프는 피해야 한다
3.자료구조보통

원형 버퍼(링 버퍼)는 일반적으로 무엇을 구현하는 데 사용됩니까?

  1. A그래프 순회
  2. B고정 크기 큐
  3. C이진 탐색 트리
  4. D해시 함수
4.자료구조어려움

원형 버퍼에서 front == rear는 비어 있음 또는 가득 참을 뜻할 수 있습니다. 둘을 구별하는 일반적인 방법은 무엇입니까?

  1. Afront가 rear와 같을 때마다 항상 버퍼를 비워 상태가 비어 있음이 되게 한다
  2. B버퍼 크기를 2의 거듭제곱으로 만든다
  3. C원소 개수를 따로 유지하거나 항상 칸 하나를 비워 둔다
  4. Dfront와 rear를 같은 변수에 저장한다
5.그래프 이론보통

연결 그래프의 정점이 20개이고 간선이 31개이다. 신장 트리가 남도록 제거해야 하는 간선은 몇 개(k)인가?

|V| = 20|E| = 31
k =
6.그래프 이론어려움
ABCDEF

D에서 출발해 같은 정점으로 돌아오는 길이 2의 닫힌 보행은 몇 개인가? 보행에서는 정점과 간선이 반복될 수 있다. 그 수를 N(이)라 하자.

M = 인접 행렬L = 2
N =

3용액

1.알고리즘과 복잡도

답: B · 모든 정점 쌍 사이의 최단 경로를 O(V³)에

이것이 답인 이유

플로이드-워셜은 각 정점을 차례로 중간 지점으로 허용하는 동적 계획법 알고리즘으로 O(V³) 시간을 사용합니다.

답

B · 모든 정점 쌍 사이의 최단 경로를 O(V³)에
2.알고리즘과 복잡도

답: A · 모든 프로그램과 입력에 대해 그것이 정지하는지를 판정할 수 있는 알고리즘은 없다

이것이 답인 이유

Turing은 정지 문제가 결정 불가능(undecidable)함을 보였습니다. 판정기가 존재한다고 가정하면 그 반대로 동작하는 프로그램과 모순이 생깁니다.

답

A · 모든 프로그램과 입력에 대해 그것이 정지하는지를 판정할 수 있는 알고리즘은 없다
3.자료구조

답: B · 고정 크기 큐

이것이 답인 이유

링 버퍼는 순환하는 head와 tail 인덱스를 사용하여 고정된 메모리에서 O(1) enqueue와 dequeue를 제공합니다.

답

B · 고정 크기 큐
4.자료구조

답: C · 원소 개수를 따로 유지하거나 항상 칸 하나를 비워 둔다

이것이 답인 이유

개수를 쓰면 비어 있음은 count = 0, 가득 참은 count = capacity입니다. 칸 하나를 비워 두면 가득 참은 (rear + 1) mod n == front로 정의됩니다.

답

C · 원소 개수를 따로 유지하거나 항상 칸 하나를 비워 둔다
5.그래프 이론

답: k = 12

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

신장 트리의 간선

20 − 1 = 19

제거할 간선

k = 31 − 19 = 12

답

k = 12
6.그래프 이론

답: N = 2

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

인접 행렬

A: 0 1 1 0 0 0
B: 1 0 1 1 1 0
C: 1 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²)DD = 0·0 + 1·1 + 0·0 + 0·0 + 0·0 + 1·1 = 2

답

N = 2

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