시험범위: 교재 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. clip_image001
  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. 점근적 표기법:한 프로그램의 시간과 공간 복잡도에 대한 의미 있는 진술을 할 수 있는 용어

    clip_image002

  5. 여러 함수들의 크기 관계
    1. clip_image003
  6. 1.6절 점화식의 폐쇄형
    1. clip_image004
  7. 비교기반 정렬 알고리즘 vs 분포에 의한 정렬 알고리즘
    1. clip_image005
    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-완전문제의 종류와 특징

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

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

'방송대 > 알고리즘' 카테고리의 다른 글

[알고리즘]기말정리요약  (0) 2010/06/30
[알고리즘]그래프II  (0) 2010/06/29
[알고리즘]그래프I  (0) 2010/06/29
[알고리즘]11강 기하 알고리즘II  (0) 2010/06/29
[알고리즘]10강 기하 알고리즘1  (0) 2010/06/29
Posted by 때찌1

    그래프II

    학습목표

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

    용어설명

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

    clip_image001

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

    정답:2

    clip_image002

    정답:2

    clip_image003

    정답:3

    clip_image004

    정답:3

    clip_image005

    정답:4

    clip_image006

    정답 : 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|³)

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

'방송대 > 알고리즘' 카테고리의 다른 글

[알고리즘]기말정리요약  (0) 2010/06/30
[알고리즘]그래프II  (0) 2010/06/29
[알고리즘]그래프I  (0) 2010/06/29
[알고리즘]11강 기하 알고리즘II  (0) 2010/06/29
[알고리즘]10강 기하 알고리즘1  (0) 2010/06/29
Posted by 때찌1

    clip_image001

    정답:2

    clip_image002

    정답:2

    clip_image003

    정답:2

    clip_image004

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

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

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

    clip_image005

    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. 다음 그래프에서 접합점과 다리를 모두 구하시오.

    clip_image006

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

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

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

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

'방송대 > 알고리즘' 카테고리의 다른 글

[알고리즘]기말정리요약  (0) 2010/06/30
[알고리즘]그래프II  (0) 2010/06/29
[알고리즘]그래프I  (0) 2010/06/29
[알고리즘]11강 기하 알고리즘II  (0) 2010/06/29
[알고리즘]10강 기하 알고리즘1  (0) 2010/06/29
Posted by 때찌1

clip_image001

정답:4

clip_image001[4]

정답:1

clip_image001[6]

정답:1

clip_image001[8]

정답:1

clip_image001[10]

정답:4

clip_image001[12]

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

 

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

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

검사 방법

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

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

(2) 볼록 껍질 찾기

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

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

그레이엄 알고리즘

단순한 알고리즘

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

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

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

(3) 짐꾸리기 알고리즘

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

방법

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

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

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

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

(4) 그레이엄 알고리즘

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

점 제거 방법

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

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

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

'방송대 > 알고리즘' 카테고리의 다른 글

[알고리즘]기말정리요약  (0) 2010/06/30
[알고리즘]그래프II  (0) 2010/06/29
[알고리즘]그래프I  (0) 2010/06/29
[알고리즘]11강 기하 알고리즘II  (0) 2010/06/29
[알고리즘]10강 기하 알고리즘1  (0) 2010/06/29
Posted by 때찌1

clip_image001[11]

 

clip_image001[13]

 

clip_image001[15]

정답:3

clip_image001[17]

정답:2

clip_image001[19]

정답:1

clip_image001[21]

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

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

'방송대 > 알고리즘' 카테고리의 다른 글

[알고리즘]기말정리요약  (0) 2010/06/30
[알고리즘]그래프II  (0) 2010/06/29
[알고리즘]그래프I  (0) 2010/06/29
[알고리즘]11강 기하 알고리즘II  (0) 2010/06/29
[알고리즘]10강 기하 알고리즘1  (0) 2010/06/29
Posted by 때찌1
2010/06/28 11:50

데이터 모델

데이터 모델의 유형

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

 

관계대수

관계연산

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

 

정규화(55-58)

정규형

  1. 제1정규형
    • 어떤 릴레이션의 모든 속성이 단순영역에서 정의되면 그 릴레이션은 제1정규형이다. 즉, 모든 속성이 원자값(atomic value)을 가지는 것. 모든 속성이 원자 값을 가질 수 있는 형태로 변환된 것.
크리에이티브 커먼즈 라이선스
Creative Commons License

'방송대' 카테고리의 다른 글

데이터베이스  (0) 2010/06/28
기말고사 시험  (0) 2010/06/27
2010 기말고사 알고리즘 관련  (0) 2010/06/25
알고리즘 정리  (0) 2010/04/21
[편지들]플라톤  (0) 2010/04/15
2010년 1학기 중간고사 시험 시간  (0) 2010/04/06
Posted by 때찌1
2010/06/27 02:41

기말시험 컴퓨터 1 유비쿼터스컴퓨팅개론 2010/06/27(일) 02(10:30) - 02(11:40) 분당정보산업고(기말)(24) 
기말시험 컴퓨터 2 객체지향프로그래밍 2010/06/27(일) 01(14:30) - 01(15:40) 분당정보산업고(기말)(20) 
기말시험 컴퓨터 3 동서양고전 2010/07/04(일) 01(09:00) - 01(10:10) 분당정보산업고(기말)(17) 
기말시험 컴퓨터 3 알고리즘 2010/07/04(일) 01(09:00) - 01(10:10) 분당정보산업고(기말)(17) 
기말시험 컴퓨터 3 데이터베이스 2010/07/04(일) 03(12:00) - 03(13:10) 분당정보산업고(기말)(17) 
기말시험 컴퓨터 4 한국사회문제 2010/07/04(일) 01(14:30) - 01(15:40) 분당정보산업고(기말)(15) 
기말시험 컴퓨터 4 웹프로그래밍 2010/07/04(일) 02(16:00) - 02(17:10) 분당정보산업고(기말)(14)
크리에이티브 커먼즈 라이선스
Creative Commons License

'방송대' 카테고리의 다른 글

데이터베이스  (0) 2010/06/28
기말고사 시험  (0) 2010/06/27
2010 기말고사 알고리즘 관련  (0) 2010/06/25
알고리즘 정리  (0) 2010/04/21
[편지들]플라톤  (0) 2010/04/15
2010년 1학기 중간고사 시험 시간  (0) 2010/04/06
Posted by 때찌1

** 시험범위: 교재 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-완전문제의 종류와 특징

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

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

'방송대' 카테고리의 다른 글

데이터베이스  (0) 2010/06/28
기말고사 시험  (0) 2010/06/27
2010 기말고사 알고리즘 관련  (0) 2010/06/25
알고리즘 정리  (0) 2010/04/21
[편지들]플라톤  (0) 2010/04/15
2010년 1학기 중간고사 시험 시간  (0) 2010/04/06
Posted by 때찌1
2010/04/21 17:12

정렬I

(1) 정렬


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


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


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

(2) 선택 정렬


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


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

(3) 버블 정렬


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

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

통하여 정렬하는 방법

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

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

(4) 삽입 정렬


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

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

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

(5) 쉘 정렬


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


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

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

'방송대' 카테고리의 다른 글

기말고사 시험  (0) 2010/06/27
2010 기말고사 알고리즘 관련  (0) 2010/06/25
알고리즘 정리  (0) 2010/04/21
[편지들]플라톤  (0) 2010/04/15
2010년 1학기 중간고사 시험 시간  (0) 2010/04/06
2010년 1학기 중간고사 관련  (0) 2010/04/06
Posted by 때찌1
2010/04/15 17:05

플라톤/편지들/2009/이제이북스/221P~279P
  1. 일곱째 편지에 관하여
    1. 일곱째 편지 개요
      1. 아테네의 정치적 격변과 플라톤의 젊은 시절
        1. 조언의 핵심은 '최선의 법에 다라 살아가는 자유인'이다.
        2. 젊은 시절 아테네의 정치적 변화에 대한 설명을 곁들여 상세히 개진하고 있다.
        3. 철학이 부재한 법률로는 정의로운 사회를 실현할 수 없다는 것을 절감하게 되었다는 것이다.
      2. 플라톤과 디온의 만남. 그리고 디오뉘시오스와의 첫 만남
        1. 뒤오뉘시오스 1세의 죽음 이후 자신의 조카인 디오뉘시오스 2세를 플라톤이 꿈꾸던 '철학자 왕'으로 만들고자 하는 바람으로 이어진다.
        2. 플라톤과 디온의 생각대로 되지 않아 디온은 얼마 후 모함을 받아 추방당하고 플라톤은 플라톤대로 디온에 대한 플라톤의 애정을 시샘하고 플라톤의 친구라는 명성을 탐할뿐 철학에 대해서는 소극적인 디오뉘시오스 2세에게 억류되다시피 지내다, 상황이 좋아지는 대로 다시 오겠다는 약속을 하고서야 겨우 아테네로 돌아갈 수 있었다.
      3. 디온의 추종자들에게 건네는 조언
        1. '최대한 어떻게든 스스로가 자신의 주인이 될 수 있도록, 그리하여 믿을 만한 친구와 동지들을 어을 수 있도록 일상의 삶을 살'것을 조언한다.
      4. 플라톤의 세 번째 시칠리아 방문의 이유
        1. 여러 사정과 더불어 혹시나 디오뉘시오스 2세가 최선의 삶에 대한 사랑에 빠졌을지도 모를 귀중한 가능성을 확인하지 않고 넘겨버리지 않아야 한다는 자기 설득을 통해 세 번째 시라쿠사 방문을 결심한다.
      5. 디오뉘시오스 2세에 대한 시험
        1. 플라톤은 시라쿠사에 도착하여 디오뉘시오스 2세를 만나 그가 철학에 많은 진전을 보였다는 이야기가 사실인지를 검토한다.
        2. 이를 통해 플라톤은 그가 철학이 아니라 헛된 의견에 가측차 있음을 알게 된다.
      6. 철학과 진술 가능성
        1. '철학적 여담(philosophical digression)'이라 불리는 이 부분에 담긴 논증의 목적은 근복적으로 철학의 진정한 대상에 대한 앎은 말이나 글로 옮겨지지 않는다는 것을 증명하는 것이다
        2. 이상의 논변을 기초로 해서 진지한 사람이라면 진지한 대상을 글로 쓰는 일은 정상적인 상태에서는 불가능하다는 결론을 끌어낸다. 이것이 바로 이 논의의 첫 머리에서 '글로 옮기기를 감행하는 자들에 대항하는 참된 논변'의 결론이다.
      7. 결별
        1. 플라톤은 철학의 궁극적인 앎이 말로 전달되는 것이 아니기 때문에 디오뉘시오스 2세가 썼다고 하는 플라톤 철학의 진수에 대한 책은 전혀 플라톤과 상관없는 책이라고 밝힌다. 다만 그것은 플라톤 철학을 아는 체하는 데서 얻을 수 있다고 기대하는 명예와 명성에 대한 욕심일 뿐이라는 것이다.
        2. 디온과 디오뉘시오스 2세 사이에서 상황을 우려하여 떠나지 못하고 어떤 사건을 통해서 결정적으로 멀어지게 되고 플라톤에 대한 잘못된 오해까지 겹쳐 살해의 위협을 받게 되자, 타렌툼에 있던 친구들의 도움을 받아 시라쿠사를 빠져 나간다.
      8. 디온의 죽음과 디온의 의도
        1. 디온은 복수를 선언하여 마침내 시라쿠사에는 내전이 벌어지고 그 와중에 디온은 살해되고 만다.
        2. 플라톤의 마지막 충고는 디온의 의도를 해명하는 것으로 대신한다.
        3. '최소한의 사형과 살인조차 없이 가장 올바르고 가장 훌륭한 정부와 법의 설립이 이루어지기를 추구'했을 것이라고 디온의 의도를 설명한다.
    2. <<일곱째 편지>>와 플라톤 철학
        • 편지를 쓰게 된 이유와 구성에서부터 이 편지의 저자가 스스로 여담이라고 말하는 342a-344d에 담긴 철학적 내용에 대한 논란까지 다양한 논의가 오랫동안 이루어져 왔다. 그 이유는 이 편지에 담긴 내용이 플라톤의 사상을 이해하는 데 중요한 단서들을 제공하기 때문이다.
      1. <<일곱째 편지>>의 집필 의도와 플라톤의 정치 철학
          • 디온의 추종자들에게 정치적 조언을 하고자 하는 목적으로 작성되었다.
        1. 플라톤이 시라쿠사의 정치를 개혁하기 위해 첫 번째로 제안하는 방안은 ‘삶의 방식의 변화’이다.
          • ‘최선의 법에 따르는’ 자유인이라는 점에 플라톤의 정치 철학의 특징이 있다.
        2. 플라톤의 정치관은 강압과 폭력이 아닌 지도자의 솔선수범과 자발적 동의를 통한 개혁이다.
          • 지도자가 솔선수범하여 덕 있는 사람이 되어야 한다고 하는 이유
            1. 정의롭고 용감하며 절제 있고 지혜를 사랑하는 사람이 되어야 지도자 본인이 행복할 수 있으며
            2. 그런 사람에게 비로소 ‘친분 있고 믿을 만한 사람’이 생기기 때문이다.
      2. 말과 글이 갖는 불확정성과 불확실성
        1. 주제’(pragma)가 “다른 학문들처럼 결코 말로 옮길 수 있는 것이 아니라, 주제 자체와 관련하여 이루어진 오랜 교유와 공동생활로부터, 예컨대 튀는 불꽃에서 댕겨진 불빛처럼 갑자기 혼 안에 생겨나서 비로소 자기 자신을 스스로 길러 낸”고 말했다.
        2. 말은 대상의 본질뿐만 아니라 그것의 부수적인 특성(to poion ti)까지 같이 담아내기 때문에 혼란을 야기시키고 정확한 지시를 못한다는 것이다.
      3. 말과 글의 허약함에 대한 다양한 해석들
        1. 플라톤의 대화편에는 두 개의 의미층이 있다.
          1. 마이스너(Meissner)는 “플라톤의 저술들에는 두 층의 로고스가 문제되고 있다고 주장한다. 전면에 드러나는 로고스가 문제이며, 배경에 숨어 있는 로고스가 문제라는 것이다.
        2. 플라톤의 비판은 말과 글의 대립 구도에서 이루어진 것이다.
          1. 독일의 튀빙겐(Tuebingen)학파는 글에 대한 비판에 국한된다는 것이다. <일곱째 편지>에서 플라톤이 자신의 저술은 있지도 않고 앞으로도 없을 것이라고 밝힌 점과 그 주제의 전달은 오랜 교유와 공동생활을 통해 이루어진다고 말한 점에 근거를 둔다.
        3. 플라톤의 비판은 말과 글 모두를 향한 것이다.
          1. 된트(E. Dont), 화이트(N.P. White),  빌란트(W. Wieland), 세이어(K.M. Sayre) 등이 있다.
          2. 플라톤이 문자를 비판하면서 동시에 말에 대해서도 비판하고 있으면 진정한 앎의 전달은 일종의 논리적 비약을 겪는다고 설명하는 듯이 보인다는 점에서 이 해석은 텍스트의 내용 자체에 충실하다는 장점을 갖는다.
        4. 플라톤은 왜 대화편을 썼을까?
          1. 튀빙겐 학파의 입장은 핵심적인 주제는 아카데미에서 구두로 전달했으며, 대화편은 일반 독자들로 하여금 철학적 탐구를 하도록 자극을 주어 말로 하는 대화의 장으로 들어오도록 유도하기 위한 장치였다는 것이다.(슬레작(T.A. Szlezak. 플라톤 읽기, 2001 참고)
          2. 여러 가지 이유에서 부득불 글을 쓰고 말을 해야 했다면, 그것은 대화의 형식이 될 수밖에 없었을 것이다.
        5. 말이나 글로 할 수 없는 철학의 핵심은 무엇인가?
          1. 튀빙겐 학파의 입장은 형상 이론과는 다른 이론을 플라톤의 이론으로 소개했던 것이라고 본다.
          2. 또 다른 해석으로는 당연히 플라톤이 말이나 글로 할 수 없다고 생각한 것은 형상(idea)이라고 보는 해석이다.
          3. 빌란트는 자체만을 중시하고 맹신할 것이 아니라 그것을 상황에 맞게 다룰 수 있는 실천적인 능력이 중요하다는 사실을 강조하기 위한 것이라고 주장한다.
          4. 또한 다른 입장으로는 플라톤이 후기에 강조한 변증술에서 ‘모음’과 ‘나눔’(플라톤 철학에서 ‘나눔’의 의미에 대해서는 박종현, 헬라트 사상의 심층, 208-221 참고)의 방법 중 ‘모음’의 방법이 말이나 글로 전달되지 않는 앎이라고 보는 입장이 있을 수 있다.
  2. 플라톤의 생에
    1. 성장기와 청년기(28세까지):태어나서부터 소크라테스의 죽음까지(기원전 427~399년)
      1. 플라톤은 기원전 427년에 태어나 80년의 생애를 보낸 후 기원전 347년에 서거했다.
      2. 플라톤의 가문은 친가 쪽, 외가 쪽 모두 그야말로 아테네에서 잘 알려진 명문 가문이었다.
      3. 플라톤의 성장기 환경과 관련해서 우리가 주목해야 할 것은 전체 그리스 사회의 몰락의 기운이 그의 성장기 전체를 드리우고 있었다는 점이다.
      4. 이 시절 행적과 관련하여 눈여겨보지 않으면 안 될 것은 그 스스로 고백하고 있는 철학과 정치에 대한 태도이다. 23살의 젊은 시절 다른 아테네 청년과 마찬가지로 정치에 뛰어들려고 마음을 먹고 있었다.
      5. 청년기 말기에 그가 맞이한 아테네 정치 현실에 대한 이와 같은 깊은 좌절과 철학에 대한 새로운 깨달음은 그로 하여금 평생을 통해 오로지 철학을 통한 진리 탐구와 교육에 몸담게 하는 결정적인 전기를 가져다 주었던 것이다.
    2. 장년기(28~40세):소크라테스의 죽음에서부터 첫 번째 시칠리아 방문까지(기원전 399~387년)
      1. 소크라테스가 죽은 후 플라톤은 소크라테스의 다른 제자들과 함께 메가라의 에우클레이데스에게 가 있었다고 말한다.
      2. 이후 수학자 테오도로스를 만나기 위해 퀴레네에 갔고
      3. 피타고라스주의자인 필롤라오스를 보기 위해 이탈리아에
      4. 신관을 만나러 이집트에 갔다고 전하고 있다.
      5. 젊은 시절 서방을 여행하는 플라톤의 흥미를 끌었던 것은 사람보다는 그들의 도시 타렌툼이었을 지도 모른다.
      6. <일곱째 편지>에서 첫 번째 시라쿠사 방문에서 무엇을 했는지 아무런 언급도 하지 않고 있으며 하물며 당시 시라쿠사의 참주였던 디오뉘시오스 1세의 이름조차 거론하지 않고 있다. 이 디오뉘시오스가 참주의 지위에 있을 때 약관 20세의 청년 디온을 운명적으로 만나게 되는데 말련의 플라톤으로 하여금 시라쿠사를 재차 방문하게 만드는 계기가 되면서 말련의 삶에 심대한 영향을 끼치게 된다.
      7. 장년기에 일어난 아주 중요한 일로서 우리가 주목해야 할 것은 <<변명>>,<<크리톤>>,<<라케스>>,<<뤼시스>>,<<에우튀프론>> 등 그의 초기 작품이라고 일컫고 있는 작품들이 이 시기 즈음부터 써지기 시작했다는 점이다.
    3. 중년기(40~60세):아카데미의 창설과 저작활동(기원전 387~367년)
      1. 자신이 평생 힘써야 할 가장 중요한 소임으로서 철학자 양성이라는 원대한 교육 목표를 가지고 시칠리아에서 돌아온 지 대략 2년쯤 후에 마침내 아카데미를 창설하기에 이른다.
      2. 플라톤의 아카데미는 중세시절 공동체 생활을 통해 종교적인 연대와 이상을 공유하던 초기 대학의 모습과 비슷하다.
      3. 아카데미에서 그들이 행한 공동식사(syssitia)는 검박한 음식을 나누며 서로 간에 기억될 만한 이야기를 나누는 자리로 유명하다.
      4. 아카데미의 교육방법의 대부분은 플라톤이 즐겨 사용했던 문답법이었을 것이다. 그러나 그는 강의도 자주 하였을 뿐만 아니라 일반 대중을 상대로 하는 강의도 열었다.
      5. 수학(음악이론과 천문학 이론을 포함해서)과 정치학은 지속적으로 개설되었을 것이다. 플라톤 사상의 특성상 그러한 정밀과학은 선에 이르는 변증술의 예비과정으로 필수적인 것이었을 것이다.
      6. 자연학은 적어도 일정기간 동안 아카데미 입학생들에게 가르쳐졌을 것이다.
      7. 대표적인 저술이라 할 수 있는 <<국가>>를 비롯해 <<향연>>,<<파이돈>>,<<에우튀데모스>>,<<크라튈로스>> 등도 이 시기에 써진 것이고 <<테이아테토스>>와 <<파르메니데스>. 역시 이 중년기에서 만년기에 걸쳐 써진 것으로 여겨진다.
      8. 전문적인 정치가 내지 정치 이론가를 키워 내려는 그의 주된 교육 목표는 잠시도 그의 생각을 떠나지 않았다. 그의 많은 제자들은 권력가들에게 자문하기 위해 아마데미를 떠나야 했다.
      9. 플라톤의 생애와 가르침을 이야기하면서 이소크라테스를 함께 이야기하지 않으면 안된다. 두 사람은 지적 호적수였다.
    4. 노년기(60~80세):두 번째 시칠리아 방문부터 죽음에 이르기까지(기원전 367~347년)
      1. 디온은 플라톤을 불러들여 참주 2세로 하여금 그의 철학을 배우게 하여 플라톤이 평생을 통해 이루려고 했던 철학자 왕정의 체제를 시칠리아 땅에서 구현하기를 원했다.
      2. 플라톤은 참주로 하여금 어떻게든 철학을 배우게 하면 사태가 호전될 수 있을지도 모른다는 일말의 기대를 가지고 최선의 노력을 경주해 보지만 그것도 허사로 돌아간다. 그렇게 돌아온 지 4년 동안 플라톤은 다시 한 번 아카데미에서 교육과 저술에 몰두하게 된다.
      3. 이후 디오뉘시오스의 초청에 세 번째 시라쿠사를 방문하게 된다. 디오뉘시오스에게 철학의 예비적인 공부를 하게 하여 그가 철학공부를 할 수 있을지를 시험한다.
      4. 플라톤의 세 번째 시칠리아 방문이자 마지막 방문은 실패로 막을 내렸다. 그러나 시칠리아와의 인연은 이것으로 끝나지 않았다. 디온은 자신의 부당한 추방과 망명에 맞서 디오뉘시오스에게 복수할 채비를 갖추자고 플라톤에게 도움을 청한다.
      5. 우여곡절 끝에 디온은 시라쿠사를 해방시키게 된다. 그러나 정쟁과정에서 힘을 소진한데다가 이후 마음의 병까지 얻어 급기야 자기 고향으로 돌아온지 4년 째 되는 기원전 354년에 자기가 가장 신뢰하고 있었던 동료 칼리포스에 의해 암살당하고 만다.
      6. 디온이 죽은 후에도 시라쿠사와 플라톤의 인연이 아주 끝나 버린 것은 아니다.
      7. <<일곱째 편지>>는 디온의 친지들의 요청에 대한 답신의 형식으로 디온이 죽은 지 7년 뒤에 써진 것이다.
      8. 시칠리아는 그의 인생 종반기 거의 대부분을 끊임없이 붙어 다니며 흔들어 놓고 있었던 일종의 멍에이자 운명과도 같은 것이었던 것이다.
크리에이티브 커먼즈 라이선스
Creative Commons License

'방송대' 카테고리의 다른 글

2010 기말고사 알고리즘 관련  (0) 2010/06/25
알고리즘 정리  (0) 2010/04/21
[편지들]플라톤  (0) 2010/04/15
2010년 1학기 중간고사 시험 시간  (0) 2010/04/06
2010년 1학기 중간고사 관련  (0) 2010/04/06
내 수강 과목  (0) 2010/03/25
Posted by 때찌1
이전버튼 1 2 3 4 5 ... 9 이전버튼