때찌네

그래프II

학습목표

1. 크루스칼 알고리즘과 프림 알고리즘의 특성을 이해하고, 이를 이용하여 최소 신장 나무를 구할 수 있다.
2. 다익스트라 알고리즘의 특성을 이해하고, 이를 이용하여 단일 출발점 최단 경로를 구할 수 있다.
3. 플로이드 알고리즘의 특성을 이해하고, 이를 이용하여 모든 쌍 최단 경로를 구할 수 있다.

   용어설명

4. 신장나무:주어진 그래프의 모든 노드들을 포함하는 연결된 부분 그래프 중 나무인 것
5. 최소 신장나무:신장 나무 중에서 간선의 가중치의 합이 가장 작은 나무
6. 최단 경로(shortest path):정점 u에서 v까지의 경로 중 간선의 가중치의 합이 가장 작은 경로
7. 다음은 프림(Prim)의 알고리즘으로 최소신장나무를 구하는 과정을 나타낸 것이다. 굵은 선으로 표시된 간선이 이미 선택된 간선들이라면 다음에 선택될 간선은? [2004학년도 기말시험]

   

   1. (c,f)
   2. (b,c)
   3. (a,d)
   4. (d,e)

   정답:2

   

   정답:2

   

   정답:3

   

   정답:3

   

   정답:4

   

   정답 : 13

(1) 최소 신장 나무

▶

최소 신장 나무(MST, minimum spanning tree)란 신장 나무 중에서
간선의 가중치 합이 작은 것

→ 신장 나무: 주어진 그래프의 모든 노드들을 포함하는 나무

▶

크루스칼 방법과 프림의 방법 → 두 방법 모두 욕심쟁이 방법이 적용됨

▶

크루스칼 알고리즘

→ 간선이 하나도 없는 숲에서 시작하여 사이클을 만들지 않는
  최소 간선들을 하나씩 추가해 나가는 방법
→ 알고리즘에서 사이클의 존재 여부를 조사하기 위해 합-찾기 연산이
  사용됨
→ 시간 복잡도 O(|E|lg|E|)

▶

프림 알고리즘

→이미 선택된 정점에 부수된 최소 간선을 추가해 나가는 방법
  = 이미 선택된 정점 집합 S와 V-S를 잇는 최소의 간선을 선택해서
   추가하는 방법
→ 시간 복잡도: 인접행렬 - O(|V|²), 인접리스트 - O((|V|+|E|)lg|V|)

(2) 단일 출발점 최단 경로

▶

음의 가중치를 갖는 간선이 없는 가중 그래프에서 한 출발
정점x에서 다른 모든 정점까지 가중치 합이 최소인 경로를 찾는 문제

▶

다익스트라 알고리즘

→ 욕심쟁이 방법 적용

→ 출발점에서 시작하여 거리가 최소인 정점을 선택해 나감으로
  최단 경로를 구하는 방법

→ 정점 v의 거리 D[v]는 시작 정점 s로부터 현재까지 선택된 정점 집합
  U를 경유하여 정점 v에 이르는 최소 경로의 길이를 의미

→ 적용 방법: ⓐ 미선택 정점 집합 V-U에서 거리 D가 최소인 정점 w를
  선택ⓑ w의 인접 정점들에 대하여 w를 경유하는 거리와 기존 거리
  중에서 작은 것을 새 거리값으로 조정

→ 시간 복잡도: 인접행렬- O(|V|²), 인접 리스트 - O((|E|+|V|)lg|V|)

(3) 모든 쌍 최단 경로

▶

모든 정점쌍 간의 최단 경로를 구하는 문제
(경로의 길이가 음인 사이클이 그래프에 존재하지 않는 것을 가정)

→ 단일 출발점 최단 경로를 구하는 다익스트라 알고리즘을 각 정점을
  출발점으로 하여 반복적으로 적용해서 구할 수도 있다 → O(|V|³)

▶

플로이드 알고리즘

→ 동적 프로그래밍 방법 적용

→: 정점 번호가 k 이하인 정점만을 경유하여 정점 i에서
  정점 j까지의 최단 경로 길이

→ 점화식:

→ O(|V|³)

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

정답:2



정답:2



정답:2



4. 다음 그림은 정점 A로부터 시작하는 그래프의 탐색 과정에서 방문 정점과 그때 사용된 간선으로 구성된 나무이다. 이 때 사용한 탐색

방법에 대한 설명으로 올바른 것은? (단, 실선으로 연결된 아래 정점들은 실제로 방문되는 정점이고, 점선으로 연결된 아래 정점들은

방문시 사용되지 않았음을 나타낸다.) [2006학년도 기말시험]



1. 최근의 방문 정점 중 인접한 주변 정점을 먼저 탐색하는 방법이다.
2. 정점 A에서 시작하여 탐색한 정점의 한 방문순서는 A,B,E,C,F,G,D이다.
3. 탐색 방법은 큐를 이용하여 구현하면 된다.
4. 인접리스트로 표현한 경우 시간복잡도는 O(|V|lg|V|)이다.
1. 합-찾기의 찾기 연산, 즉 find(x)가 행하는 작업은? [2004학년도 기말시험]
   1. x의 값을 찾아낸다.
   2. x의 레코드 위치를 찾아낸다.
   3. 원소 x가 속한 나무의 뿌리를 찾아낸다.
   4. 원소 x가 속한 나무의 부모를 찾아낸다.

   정답:3

2. 다음 그래프에서 접합점과 다리를 모두 구하시오.

   

   정답 : 접합점 → A, C, J, 다리 → (A,B), (C,J)

   해설: 연결된 무방향 그래프에서 접합점이란 제거하게 되면 그래프의 연결이 끊어져서 그래프가 둘 이상의 부분으로 분할되는

   정점을 의미한다. 또한 다리는 그래프가 둘 이상의 부분으로 분할되어 그래프의 연결이 끊어지는 간선이다.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

정답:4

정답:1

정답:1

정답:1

정답:4

정답 : 시계 방향으로 꺾일 때 꼭지점

1) 점과 다각형의 상대 위치 검사

▶

점과 다각형이 주어졌을 때 그 점의 위치가 다각형의 내부인지
외부인지를 결정하는 문제

▶

검사 방법

→ 점에서 임의의 방향으로 그은 반직선이 다각형의 변과 교차하는
   점의 개수를 조사한다. 교점의 개수가 홀수이면 다각형 내부,
   짝수이면 다각형의 외부에 존재하는 것을 판단한다.

→ 검사선(반직선)이 꼭지점 또는 변을 통과하는 경우에는 검사선에
   닿기 직전의 꼭지점과 검사선을 벗어난 직후 처음 만나는 꼭지점이
   검사선을 기준으로 서로 같은 편에 있는 지 조사
   (같은 편 → 다각형의 어느 점도 지나지 않은 것으로 간주,
   다른 편 → 다각형의 한 변을 지난 것(교점이 하나 존재)으로 취급)

(2) 볼록 껍질 찾기

▶

볼록 껍질이란 점집합의 모든 점을 포함하는 최소 면적의 볼록
다각형

▶

볼록 껍질을 찾는 방법: 단순한 방법, 짐꾸리기 알고리즘,

그레이엄 알고리즘

▶

단순한 알고리즘

→ 점을 하나씩 추가해 나가면서 구하는 방법으로, k개의 점에 대한
   볼록 껍질을 구했고 k+1번째 점까지를 포함한 볼록 껍질을 구하는 경우
   새 점이 다각형 내부에 있는 지를 확인하고, 만약 다각형 밖의
   점이라면 해당 점까지 포함하도록 볼록 껍질을 확장해 나가는 방법,
   O(n²)

→ 항상 X좌표가 최소인 점을 선택하면 해당 점이 다각형 내부의 점인지를
   확인할 필요가 없다.

→ 새 점과 현 볼록 껍질의 점들 중에서 최소각의 점과 최대각의
   점을 구하고, 이 두 점 사이의 점들을 제거하고 이 두 점과
   새 점을 연결하여 새로운 볼록 껍질을 구한다.

(3) 짐꾸리기 알고리즘

▶

무한대에서부터 임의의 각도로 직선을 점집합쪽으로 접근시켜서
직선과 처음 만나는 점들로 볼록 껍질을 형성하는 방법, O(n²)

▶

방법

① Y좌표가 최소인 점을 최초의 꼭지점(기준점)으로 선택

② 기준점으로부터 아직 선택이 안 된 모든 점들에 대한 각도를 계산한다.

③ 최소각을 갖는 점을 다음의 볼록 껍질의 꼭지점(기준점)으로 선택한다.

④ 지금 선택한 꼭지점이 최초의 기준점이면 계산을 종료하고, 아니면
   그 점을 기준으로 단계②부터 반복

(4) 그레이엄 알고리즘

▶

주어진 점집합으로부터 우선 단순 폐쇄 경로를 구한 후 볼록 껍질의
꼭지점이 될 수 없는 것을 제거해 나가는 방법, O(nlogn)

▶

점 제거 방법

→ 볼록 다각형의 꼭지점을 어떤 기준점으로부터 반시계 방향으로
   따라가면 항상 반시계 방향으로 꺾인다.

→ 이와 같이 단순 폐쇄 경로를 따라가는 도중에 꺾은선ABC의 방향이
   시계 방향이면 점 B를 제거한다. 왜냐하면 점B는 그때까지 만들어진
   볼록 다각형의 내부에 존재하는 점이기 때문이다.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

정답:3

정답:2

정답:abs(Dy) / (abs(Dx)+abs(Dy))

• 실제 각도가 아닌 상대 각도를 계산하기 위해서는 θA < θB이면 tanθA= dy1/dx1 < tanθB= dy2/dx2가 되고, 이 식으로부터 점의 상대 각도를 구하는 식 T= dy/(dx+dy)를 유도할 수 있다. (교재 209쪽 참조)

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

첨부

[2006학년도 1학기 기말시험] 소프트웨어공학.hwp

[2007학년도 1학기 기말시험] 소프트웨어공학.hwp

[2008학년도 1학기 기말시험] 소프트웨어공학.hwp

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

1. 1
2. 3
3. 4
4. 4
5. 2
6. 3
7. 2
8. 1
9. 4
10. 3
11. 2
12. 4
13. 3
14. 4
15. 1

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.