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

공식 모음, 모든 주제의 핵심 풀이 단계, 연습 문제 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.알고리즘과 복잡도보통

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

  1. AO(n log n)
  2. BO(n)
  3. CO(n²)
  4. DO(2ⁿ)
2.알고리즘과 복잡도어려움

어떤 문제가 NP-완전(NP-complete)이려면 어떤 조건을 만족해야 합니까?

  1. A푸는 것이 불가능하다
  2. B다항 시간에 풀 수 있다
  3. CNP에 속하고 모든 NP 문제가 다항 시간에 그 문제로 환원된다
  4. DNP 밖에 있으면서 정지 문제처럼 모든 NP 문제보다 어렵다
3.자료구조보통

알파벳이 고정된 트라이(trie)에서 길이 L인 단어를 탐색하는 데 얼마나 걸립니까?

  1. An이 단어 수일 때 O(log n)
  2. BO(L × n)
  3. C저장된 단어 수와 관계없이 O(L)
  4. Dn이 단어 수일 때 O(n)
4.자료구조어려움

어떤 객체를 해시 맵의 키로 저장한 뒤, 그 해시 함수가 사용하는 필드를 바꿉니다. 예상되는 결과는 무엇입니까?

  1. A객체가 이전 해시의 버킷에 있으므로 조회가 실패할 수 있다
  2. B필드가 바뀌는 순간 맵이 오류를 던진다
  3. C맵이 자동으로 키를 새 버킷으로 옮긴다
  4. D키의 해시는 프로그램이 시작될 때 한 번만 계산되므로 아무것도 바뀌지 않는다
5.그래프 이론보통

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

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

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

M = 인접 행렬L = 2
N =

3용액

1.알고리즘과 복잡도

답: D · O(2ⁿ)

이것이 답인 이유

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

답

D · O(2ⁿ)
2.알고리즘과 복잡도

답: C · NP에 속하고 모든 NP 문제가 다항 시간에 그 문제로 환원된다

이것이 답인 이유

NP-완전 문제는 NP에서 가장 어려운 문제이며, 그중 하나라도 다항 시간 알고리즘이 있으면 NP 전체에 대한 다항 시간 알고리즘이 존재하게 됩니다.

답

C · NP에 속하고 모든 NP 문제가 다항 시간에 그 문제로 환원된다
3.자료구조

답: C · 저장된 단어 수와 관계없이 O(L)

이것이 답인 이유

각 문자가 자식 하나를 선택하므로, 트라이에 단어가 얼마나 있든 조회는 L 단계가 걸립니다.

답

C · 저장된 단어 수와 관계없이 O(L)
4.자료구조

답: A · 객체가 이전 해시의 버킷에 있으므로 조회가 실패할 수 있다

이것이 답인 이유

키의 위치는 이전 해시로 정해졌습니다. 새 해시로는 조회가 잘못된 버킷을 찾으므로 키는 불변이어야 합니다.

답

A · 객체가 이전 해시의 버킷에 있으므로 조회가 실패할 수 있다
5.그래프 이론

답: k = 10

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

신장 트리의 간선

20 − 1 = 19

제거할 간선

k = 29 − 19 = 10

답

k = 10
6.그래프 이론

답: N = 1

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

인접 행렬

A: 0 0 1 0 0
B: 0 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0

공통 이웃

(M²)EA = 0·0 + 1·0 + 1·1 + 1·0 + 0·0 = 1

답

N = 1

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