프로그래밍/자료구조
-
[시스템프로그래밍] 11강 DBMS, 문서 편집기, 디버거프로그래밍/자료구조 2014. 4. 28. 01:28
* DBMS(Database Management System)데이터 관리 시스템이라 부르며 다수의 컴퓨터 사용자들이 데이터 베이스 안에 데이터를 기록하거나 접근할 수 있도록 해주는 프로그램이다.무결성, 보안성을 제공해야한다표준화된 언어를 SQL이라고 한다대표적인 DBMS로는 마이크로소프트 액세스와 SQL 서버가 있다이외에는 DB2, 인포믹스, 오라클등이 있다데이터베이스 언어를 크게 데이터 정의어(DDL)와 데이터 조작어(DML)로 구분가능하다. 데이터 정의어(data definition language)데이터와 데이터 간의 관계를 정의하는 데 사용되는 언어데이터베읏 내에서 데이터 구조를 만드는데 사용주요 데이터베이스 관리 시스템은 모두 SQL 데이터 정의 언어를 사용 2. 데이터 조작 언어(Data Ma..
-
[자료구조] 15강 탐색, 정렬프로그래밍/자료구조 2014. 4. 24. 02:41
* 탐색 리스트에서 원하는 키를 찾고자 하는 방법을 탐색이라 하고 탐색 방법의 효율은 리스트에서 레코드들의 배열 순서에 대한 가정에 따라 달라진다.레코드들이 키 필드 값의 순서로 배열되어 있을 경우에는 리스트를 효율적으로 탐색할 수 있다.레코드들이 키 필드 값에 관계없이 임의 순서로 배열되어 있을 경우에는 리스트의 한쪽 끝에서 탐색을 시작해서 원하는 키를 찾거나 리스트의 다른 쪽 끝에 닿을 때까지 각 레코드를 조사해야한다.주어진 리스트에서 원하는 키를 찾는 탐색으로 순차 탐색, 이진 탐색, 피보나치 탐색등이 있다. 1.순차 탐색주어진 리스트에서 탐색키와 같은 레코드를 검색하는 방법으로 리스트에서 순차적으로 킷값을 탐색키와 비교하여 원하는 레코드를 찾는 방법레코드들을 순차적으로 조사해서 순차 탐색(sequ..
-
[자료구조] 14강 그래프의 순회, 최소 비용 신장 트리, 그래프의 응용프로그래밍/자료구조 2014. 4. 23. 04:23
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 그래프 순회라고 한다. 그래프 순회는 순회하는 방향에 따라서 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)로 나뉜다. 1.깊이 우선 탐색(DFS)깊이 우선 탐색 방법(DFS:Depth-first search)방법은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하게 된다.깊이 우선 탐색은 탐색했던 마지막 정점으로 다시 되돌아가야하기 때문에 후입선출 구조의 스텍을 사용한다. 2.너비 우선 탐색너비 우선 탐색 방법(BFS:Breadth-first ..
-
[자료구조] 13강 그래프, 그래프 표현 방법프로그래밍/자료구조 2014. 4. 23. 02:51
1.그래프의 정의그래프는 정점(vertex), 간선(edge)들의 집합으로 구성되는 비선형 자료구조V(G)와 E(G)는 그래프 G의 정점들의 집합과 간선들의 집합을 나타내며 G=(V,E)로 표기그래프 G에서 정점(vertex)는 V(G)로 표기하고 노드라고 부르기도 한다.간선(edge)는 정점들 간의 관계를 표현하는 방법으로 E(G)로 표기하고 링크(link)라고 부르기도 한다 2.그래프의 용어그래프는 간선들 간의 방향성이 있는지와 간선의 가중치가 있는지 및 간선의 수에 따라 여러 가지 그래프의 종류로 구분 (1) 무방향 그래프무방향 그래프는 정점들 간에 순서가 없는 그래프로서 간선을 의미한다.(2) 방향 그래프방향 그래프는 정점들 간의 순서가 의미 있는 그래프로 다른 간선을 의미(3) 완전 그래프완전 ..
-
[자료구조] 12강 이진 탐색 트리, 선택 트리, 포리스트, 이진 트리의 개수 계산프로그래밍/자료구조 2014. 4. 22. 17:57
* 이진 탐색 트리 1.소개이진 탐색 트리는 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조로 모든 연산은 킷값을 기초로 실행된다.이진 탐색 트리는 이진 트리이며 공백이 아니면 모든 원소는 상이한 키를 갖는다.왼쪽 서브 트리 원소들의 키가 루트의 키보다 작고 오른쪽 서브 트리 원소들의 키는 루트의 키보다 큰 값들을 가진다. 2.이진 탐색 트리의 탐색이진 탐색 트리에서 킷값이 X인 원소를 탐색하는 방법은 루트 노드를 시작으로 탐색이진 탐색 트리가 공백이면 탐색은 종료탐색하는 노드가 탐색키와 동일한 경우에는 탐색이 성공하고 해당되는 포인터 값을 반환, 반면에 킷값이 동일하지 않으면 현재 노드의 킷값과 탐색 킷값을 비교하여 탐색키가 크면 오른쪽 서브 트리를 탐색하고 탐색키가 작으면 왼쪽 서..
-
[자료구조] 11강 히프프로그래밍/자료구조 2014. 4. 22. 17:00
히프 추상 데이터 타입히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조이다.최대히프는 킷값이 가장 큰 노드를 찾기 위한 완전이진 트리이며 부모 노드의 킷값은 자식 노드의 킷값보다 항상 크거나 같다. 따라서 루트노드는 킷값들 중 가장 큰 노드가 된다.최소히프는 킷값이 가장 작은 도르르 찾기 위한 완전이진 트리로 부모 노드의 킷값이 자식 노드의 킷값보다 항상 작거나 같다. 따라서 루트노드는 킷값들 중 가장 작은 노드가 된다. ADT HEAP데이터 : n개의 원소로 구성된 완전 이진트리로서 각 노드의 킷값은 그의 자식 노드의 킷값보다 크거나 같다. (부모 노드의 킷값>=자식 노드의 킷값) createHeap() : 공백 히트를 생성하는 연산isEmpty(he..
-
[자료구조] 10강 트리, 이진트리, 순회, 응용, 스레드 이진트리, 이진 변환프로그래밍/자료구조 2014. 4. 22. 05:27
* 이진 트리 이진 트리는 모든 노드가 정확하게 두 서브 트리를 가지고 있는 트리로 왼쪽 서브 트리와 오른쪽 서브 트리를 분명하게 구별할 수 있는 트리이다.종류에는 완전이진트리, 포화이진트리, 편향이진트리 등이 있다.이진트리의 주요 성질은 레벨 I의 최대 노드 수는 2i+1개 이고 높이가 h인 이진 트리의 최대 노드 수는 2h+1-1개이다. 완전 이진 트리는 높이가 h이고 노드 수가 n인 이진 트리에서 노드의 레벨 순서 번호들의 각 위치가 포화 이진 트리 번호 1에서 n까지 모두 일치하는 트리포화 이진 트리는 높이가 h이고 노드 수가 2h+1-1인 이진 트리로 트리의 높이에 모든 자식 노드들이 채워진 트리를 의미편향 이진 트리는 루트 노드를 기준으로 자식 노드가 한쪽 방향에만 존재하는 트리 * 이진 트리..
-
[자료구조] 9강 트리프로그래밍/자료구조 2014. 4. 22. 04:52
정의- 그래프 중에서 사이클을 포함하지 않는 연결 그래프로서의 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 것을 트리라한다.트리는 계층적인 자료구조로 노드와 각 노드를 연결하는 간선들로 구성노드 중에서 단 하나의 루트 노드가 존재하고 루트 노드에서 다른 하위노드들이 간선들로 연결된 비선형 구조의 계층 구조트리의 종류에는 이진트리, 전 이진 트리, 포화 이진 트리, 사향 트리들이 있다.트리의 응용 분야는 계층적인 조직, 디택토리 구조, 인공지능에서 의사결정 구조등을 표현하는 결정 트리를 표현하는데 사용된다. 2. 용어노드와 차수 : 밑으로 나뉘는 개수 (한 노드가 가지고 있는 서브 트리의 수)단말 노드와 비단말 노드 : 단말 노드는 차수가 0인 노드를 말한다., 리프,노드 또는 터미널 노드라고도 ..