자료구조
-
[자료구조] 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인 이진 트리로 트리의 높이에 모든 자식 노드들이 채워진 트리를 의미편향 이진 트리는 루트 노드를 기준으로 자식 노드가 한쪽 방향에만 존재하는 트리 * 이진 트리..
-
[자료구조] 7강 1-2절 연결리스트의 필요성 ~ 단순 연결 리스트프로그래밍/자료구조 2014. 4. 22. 04:50
연결 리스트의 필요성 순서 리스트는 배열을 이용하여 구현 -> 메모리 사용 측면에서의 비효율적인 문제점이 나타난다.순서리스트에서 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간이 소요되는 점이 가장 큰 부담-> 따라서 순서리스트에서 나타나는 문제점을 개선할 자료표현방법이 필요 순서리스트에서 원소의 삽입과 삭제시 빈번한 자리이동으로 복잡도가 증가하고 부담이 증가.이미 사용중인 크기를 변경하고자 하는 경우에는 연속적인 공간의 여유가 있는 경우에서는 문제가 되지 않지만 사용 중인 공간 이후에 여유 공간이 부족하면 기억공간에서 확장할 크기를 포함하는 기억 공간을 다시 할당 받아야하는 문제가 발생한다.연속적인 자료에 대한 추가,삭제가 빈번하다면 순서 리..