시험범위: 교재 1-8장, 10장 및 강의 전부

총35문항이 출제되며, 각 장별 출제문항수는 다음과 같습니다.

1장-6문항

2장-12문항

3장-5

4-2

5-1

6-3

7-4

8-1

10-1

각 장별 주요 사항들을 정리하면 다음과 같습니다.

1. 1.1절 알고리즘의 기본개념
   1. 
2. 1.4절(2문항) 최대값/최소값 찾기
   1. 값들을 하나씩 모두 비교해 가면서 최대값을 찾는 방법:n-1번
   2. 토너먼트 방식(둘 씩 해서 이긴팀):n-1번
   3. 뒤섞인 카드에서 K찾기
      1. 순차탐색
3. 알고리즘 설계 기법
   1. 알고리즘의 직선적인 설계 방법은 주어진 문제를 컴퓨터를 사용하지 않고 해결하는 과정을 우선 생각한 후 이를 컴퓨터를 구현하는 것
      1. 욕심쟁이 방법(greedy method)
         1. 각 선택과정마다 그 단계에서 최선이라고 볼 수 있는 선택을 행해나가면서 결과적으로 전체적인 최적 해를 구하는 방법, 욕심쟁이 방법으로 해를 구할 수 없는 문제도 있으나 간단한 알고리즘을 만들 수 있다.
      1. 분할 정복(divide and conquer)
         1. 어떤 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하려는 방법
      1. 동적 프로그래밍
4. 1.5절(2문항) 점근적 표기법의 정의
   1. 점근적 표기법:한 프로그램의 시간과 공간 복잡도에 대한 의미 있는 진술을 할 수 있는 용어

   

5. 여러 함수들의 크기 관계
   1. 
6. 1.6절 점화식의 폐쇄형
   1. 
7. 비교기반 정렬 알고리즘 vs 분포에 의한 정렬 알고리즘
   1. 
   2. 비교 기반 정렬:계수, 기수, 버킷 정렬
8. 제자리 정렬 알고리즘와 안정적 알고리즘의 종류
   1. 안정적(stable) 알고리즘: 정렬 전에 동일한 키를 갖는 레코드 쌍의 상대적인 위치가 정렬 후에도 그대로 유지되는 형태의 알고리즘
   2. 제자리(in-place) 알고리즘: 입력 배열 이외의 별도 메모리에 저장되는 원소의 개수가 상수 개를 넘지 않는 정렬 알고리즘
   3. 제자리 정렬 알고리즘
      1. 선택 정렬
      2. 버블 정렬
      3. 삽입 정렬
      4. 쉘 정렬
      5. 퀵 정렬
      6. 힙 정렬
   1. 안정적 알고리즘
      1. 선택 정렬
      2. 버블 정렬
      3. 삽입 정렬
      4. 합병 정렬
      5. 계수 정렬
      6. 기수 정렬
      7. 버킷 정렬
   1. 불안정적 알고리즘
      1. 선택 정렬
      2. 쉘 정렬
      3. 퀵 정렬
      4. 힙 정렬
9. 정렬 알고리즘들의 시간복잡도 (2문항)

   1. 정렬	시간복잡도	제자리	안정적	불안정	비고
      선택	O(n2)	O	O	O
      버블	O(n2)	O	O
      삽입	O(n2)	O	O
      쉘	O(n1.5)	O		O
      퀵	세타(nlogn)	O		O
      합병	세타(n)	X	O
      힙	O(nlogn)	O		O	평균 퀵보다 느림
      계수		X	O
      기수		X	O
      버킷		X	O

10. 기본적인 정렬 알고리즘들의 처리 과정
11. 쉘 정렬
12. 퀵 정렬의 배열분할함수(Partition) 및 특성
13. 히프 정렬의 두 번째 처리 과정
14. 분포에 의한 정렬 알고리즘의 개념/특징 및 시간복잡도
15. 입력 데이터의 정렬 여부에 따른 정렬 알고리즘의 특징/시간복잡도
16. - 순차탐색
17. - 탐색 기법의 시간복잡도
18. - 2-3-4 나무의 삽입과정
19. - 흑적나무의 개념/특징
20. - 해싱
21. - 직선적 스트링매칭 알고리즘의 특징
22. - 보이어-무어 알고리즘
23. - RLE + 허프만 코딩의 개념/특징
24. - 점의 상대각도 계산
25. - 단순폐쇄경로 찾기
26. - 볼록껍질 알고리즘의 종류와 특징
27. - 그래프 순회(깊이우선탐색, 너비우선탐색)
28. - 7.3.2 이중연결성
29. - 최소신장나무 구하기
30. - 최단경로 알고리즘의 종류와 특징
31. - 동적프로그래밍 알고리즘의 처리과정과 문제의 종류
32. - NP-완전문제의 종류와 특징

    위이 내용 및 기말 시험 자체에 관해서는 질문의 삼가해 주기 바랍니다.

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

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

그래프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 대한민국 라이선스에 따라 이용하실 수 있습니다.

데이터 모델

데이터 모델의 유형

• 개념적 모델
• E-R모델, 이진 모델, 의미 모델, 정보 논리 모델, 함수적 모델
• 물리적 모델
• 프레임 메모리, 연합 모델
• 구현 모델
• 관계형 모델
• 객체 지향 모델
• 객체 관계형 모델
• 망형 모델
• 계층형 모델

관계대수

관계연산

1. 프로젝션(π):어떤 속성들을 선택하고 나머지는 버리는 연산. 즉, 어떤 릴레이션의 일부 속성들에만 관심이 있을 경우에 해당 속성들을 끄집어내는 연산.
2. 셀렉션(δ):조건을 만족하는 투플들의 집합을 선택하는 데 사용
3. 조인(▷◁):투플들을 결합하여 하나의 투플로 만든다.
• 조건 조인(θ):조건을 만족하는 투플
• 자연 조인(*):두 개의 릴레이션에 대해서 공통되는 속성이 있는 경우, 그 공통되는 속성에 대해서 같은 값을 가지는 투플, 중복되는 속성들을 제거한 동등 조인

정규화(55-58)

정규형

1. 제1정규형
• 어떤 릴레이션의 모든 속성이 단순영역에서 정의되면 그 릴레이션은 제1정규형이다. 즉, 모든 속성이 원자값(atomic value)을 가지는 것. 모든 속성이 원자 값을 가질 수 있는 형태로 변환된 것.

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

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

** 시험범위: 교재 1-8장, 10장 및 강의 전부

** 총35문항이 출제되며, 각 장별 출제문항수는 다음과 같습니다.

1장-6문항, 2장-12문항, 3장-5, 4-2, 5-1, 6-3, 7-4, 8-1, 10-1

** 각 장별 주요 사항들을 정리하면 다음과 같습니다.

- 1.1절 알고리즘의 기본개념

- 1.4절(2문항) 최대값/최소값 찾기, 알고리즘 설계 기법

- 1.5절(2문항) 점근적 표기법의 정의, 여러 함수들의 크기 관계

- 1.6절 점근식의 폐쇄형

- 비교기반 정렬 알고리즘 vs 분포에 의한 정렬 알고리즘

- 제자리 정렬 알고리즘와 안정적 알고리즘의 종류

- 정렬 알고리즘들의 시간복잡도 (2문항)

- 기본적인 정렬 알고리즘들의 처리 과정

- 쉘 정렬

- 퀵 정렬의 배열분할함수(Partition) 및 특성

- 히프 정렬의 두 번째 처리 과정

- 분포에 의한 정렬 알고리즘의 개념/특징 및 시간복잡도

- 입력 데이터의 정렬 여부에 따른 정렬 알고리즘의 특징/시간복잡도

- 순차탐색

- 탐색 기법의 시간복잡도

- 2-3-4 나무의 삽입과정

- 흑적나무의 개념/특징

- 해싱

- 직선적 스트링매칭 알고리즘의 특징

- 보이어-무어 알고리즘

- RLE + 허프만 코딩의 개념/특징

- 점의 상대각도 계산

- 단순폐쇄경로 찾기

- 볼록껍질 알고리즘의 종류와 특징

- 그래프 순회(깊이우선탐색, 너비우선탐색)

- 7.3.2 이중연결성

- 최소신장나무 구하기

- 최단경로 알고리즘의 종류와 특징

- 동적프로그래밍 알고리즘의 처리과정과 문제의 종류

- NP-완전문제의 종류와 특징

위이 내용 및 기말 시험 자체에 관해서는 질문의 삼가해 주기 바랍니다.

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

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

정렬I

(1) 정렬

▶
정렬: 여러 원소로 구성된 리스트에 대해서 이 원소들을 크기 순서대로 재배치하는 것

▶
안정적(stable) 알고리즘: 정렬 전에 동일한 키를 갖는 레코드 쌍의
상대적인 위치가 정렬 후에도 그대로 유지되는 형태의 알고리즘

▶
제자리(in-place) 알고리즘: 입력 배열 이외의 별도 메모리에
저장되는 원소의 개수가 상수 개를 넘지 않는 정렬 알고리즘

(2) 선택 정렬

▶
정렬되지 않은 데이터 중에서 가장 작은 것을 선택한 후, 선택된
데이터를 미정렬 데이터의 첫 번째 원소와 교환하는 과정을 반복
하는 정렬 방법

▶
시간복잡도 O(n2), 제자리 정렬 알고리즘, 안정적/불안정적
알고리즘

(3) 버블 정렬

▶
모든 인접한 두 키를 비교한 후 자리바꿈(오름차순으로 정렬하는

경우,왼쪽의 키가 오른쪽의 키보다 더 크면 자리를 바꾼다)을

통하여 정렬하는 방법

▶

주어진 키가 모두 역순으로 정렬되어 있는 경우에 최악의 실행시간을 가짐

▶

시간복잡도 O(n2), 안정적, 제자리 정렬 알고리즘

(4) 삽입 정렬

▶
미정렬 부분의 첫 번째 원소로부터 한 원소씩 꺼내어 정렬된 부분의
제자리에 삽입하는 방법

▶

키 간의 비교 회수가 키들의 원래 순서에 민감하게 반응 (최악의 경우: 키가
역순으로 이미 정렬되어 있는 경우, 최선의 경우: 배열이 제 순서로 정렬된
상태의 경우에는 O(n)을 가짐으로 다른 어떤 정렬 알고리즘보다 효율적)

▶

시간복잡도 O(n2), 안정적, 제자리 정렬 알고리즘

(5) 쉘 정렬

▶
제자리에서 멀리 떨어진 원소가 제자리를 빨리 잡을 수 있도록 하기 위해
멀리 떨어진 원소들에 대하여 삽입 정렬을 수행 → 입력 배열을
부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와
개수를 변화시켜 가면서 여러 번 거치도록 한 것

▶
시간복잡도 O(n1.5), 불안정, 제자리

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

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

미국 ‘빈곤 기준’ 반세기 만에 바뀐다:워싱턴 | 김진호 특파원 jh@kyunghyang.com

관련 댓글

• 지난 100년간 부는 어마어마하게 증가했는데빈곤층은 감소는 커녕 오히려 증가하고 있다그 원인은 자본주의 체제의 속성에 있다무한경쟁과 승자독식 패배자 소외의 구조적 모순은필연적으로 1%재벌의 지배계층이 99%의 가난한 피지배계층을 착취하는 결과를 초래한다 ...

빈곤정책 결정 기구서 진보단체 배제:한겨레|김소연 기자

• 복지부, 중앙생보위 시민몫 보수단체로 교체

• ‘상대적 빈곤’ 도입 등 주요 의제 앞두고 우려

빈곤의 기준은 소득 아닌 지출 돼야:디어다음 / 조혜은 기자, 사진=정재윤 기자

굶주림에 시달리는 세계 인구 비율 (자료: World Food Programme, 2006)

통계청,「경제활동 인구 조사 부가 조사」(2001.8)

보건복지부 생활 보장과의 “보도 자료” 2002.5.30 & 11.28일자

한국 노총. 「최저 임금법 개정에 관한 청원」(2002.8)

naver 백과사전 발췌.(http://100.naver.com/100.nhn?docid=82163)

빈곤의 정의와 규모. 「서울대학교 김대일 교수」2005

KDI정책포럼 제146호, 1999.

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

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

1. 객체지향프로그래밍

   • 2010/04/24(토) (18:10) - (18:55) (12) 

2. 데이터베이스(강의3,4,6,7장)

   • 2010/04/25(일) (11:20) - (12:05) (16) 

3. 알고리즘

   • 2010/04/25(일) (11:20) - (12:05) (16) 

4. 웹프로그래밍

   • 2010/04/25(일) (15:30) - (15:50) 분당정보산업고(중간)(14)

출석수업 대 체

45분 3(4학년 2과목) 15분 15 객 관 식(대체실습(일부))

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

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