본문 바로가기

독학사 컴퓨터과학과18

자료구조(18) - 이진트리의 순회, 응용 - 중위 순회 : 왼쪽의 서브트리, 루트 노드, 오른쪽의 서브트리 순으로 방문한다. : 각각의 서브트리에서는 다시 왼쪽의 서브트리, 루트 노드, 오른쪽의 서브트리를 반복 적으로 순환하여 순회하게 된다. : 상기의 트리를 중위 순회하면 A + B * C / D 가 된다. - 후위 순회 : 왼쪽 서브트리, 오른쪽 서브 트리와 루트노드 순으로 방문한다. - 전위 순회 : 자기 자신 노드, 왼쪽 자식노드, 오른쪽 자식 노드 순으로 방문 - 이진 트리에 의한 정렬 : 입력데이터의 첫번째 원소를 루트노드, 다음 원소부터 각 노드와 비교해 정렬할 원소가 작으면 왼쪽 자식노드, 크면 오른쪽 자식 노드로 삽입한다. 이를 중위 순회를 하게되면 주어진 리스트가 오름차순으로 정렬된다. - 명제 논리 : 변수 x1, x2, x.. 2021. 4. 20.
자료구조(17) - 이진 트리 - 이진트리 : 모든 노드가 정확하게 두 서브 트리를 가질 수 있는 트리 : 왼쪽 서브트리와 오른쪽 서브트리를 분명하게 구별할 수 있는 트리 : 이진트리에서 2개의 서브 트리가 모두 공백인 리프 노드들은 D, H, F, I이고 E, G는 공백이 아닌 서브 트리를 하나씩 가지고 있다. : 노드 E는 공백 왼쪽 서브트리와 오른쪽 서브트리 G를 가지고 있으며, 노드 G는 왼쪽 서브트리와 오른쪽 공백 서브트리를 가지고 있다. : 왼쪽 서브트리와 오른쪽 서브트리를 확실하게 구분한다고 하였다. 공백과 서브트리의 위치가 다른점은 다르기 때문에 둘은 구분지어 진다. - 편향 이진트리 : 편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에, 왼편으로 편향돼 있거나 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로.. 2021. 4. 19.
자료구조(16) - 트리 ( Tree ) - 트리 ( Tree ) : 그래프 중에서 사이클을 포함하지 않는 연결 그래프로서 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 것. ( 계층적인 구조로 상위에서 하위로만 가는 구조인듯 하다. 안그러면 그림이 설명이 되지 않는다. ) : 노드중에는 단 하나의 루트 노드가 존재( / )하고 루트 노드에서 다른 하위 노드들이 간선으로 연결된 비선형 구조의 계층 구조이다. : 트리의 종류로는 : 이진 트리, 포화 이진 트리, 완전 이진 트리, 방향(편향) 트리 등이 있다. : 트리의 응용 분야로는 : 계층적인 조직이나 디렉토리 구조 및 인공지능에서 인간의 의사결정 구조를 표현하는 결정 트리를 표현하는 데 이용된다. - 용어 : 트리 ( Tree ) : 상기의 전체를 트리라 한다. : 노드 ( node .. 2021. 4. 19.
자료구조(15) - 연결리스트의 종류와 특성 - 순서 리스트 :자료의 논리적인 순서와 물리적인 순서가 일치하는 구조 : 배열을 이용하여 구현. : 삽입, 삭제 연산후에 연속적인 물리주소를 유지하기위해 원소들을 이동시키는 추가적인 작업과 시간이 소요 : 시간복잡도 O(n) - 단순 연결 리스트 : 노드로 구성 : 데이터 부분 + 링크 부분 : 데이터 부분 : 저장되는 원소, 원소의 형태에 따라 하나 이상의 필드 : 링크 부분 : 다음 노드의 위치를 가리키는 포인터 값 저장. : 다음 노드가 없는 마지막 값의 경우 null 값. : 원소의 삽입과 삭제시 각각의 링크 부분의 포인터 값만을 변경하면 된다. : 시간복잡도 O(1) : 연속적인 기억공간이 없어도 저장이 가능하다. : 순서리스트나 배열보다 링크부분이 추가되므로, 기억공간이 많이 필요하다. : .. 2021. 4. 19.
자료구조(14) - 비사용 기억 공간 - 순차 가용 공간에서의 노드 획득 : 기억 공간의 상황이 이렇다 가정하자. 리스트 B에서 원소가 추가된다면, 전체 기억공간에 사용 가능한 공간이 남아있더라도, 순차적인 공간이 없어 오버플로우가 발생하게 일어나게 된다. 이러한 문제점 때문에 리스트에서 사용되는 기억 공간의 관리 방식으로는 사용하기 전의 메모리나 사용이 끝난 후의 메모리를 관리의 용이성을 위해 노드로 구성하여 연결한 리스트를 자유 공간 리스트 또는 순차 가용공간이라고 하며, 연결 리스트 구현에서 메모리의 효율적인 사용을 위하여 쓰인다 ( 책에 있는 글인데 되게 문장이 깔끔하지 못한 것 같다. 심지어 줄 바꿈도 없다. ) 기억공간의 관리 방식으로, 사용이 끝난 후 혹은 사용 전의 메모리를 노드로 구성하여 연결한다. 이를 자유공간 리스트 또는.. 2021. 4. 18.
자료구조(13) - 단순 연결 리스트 - 단순 연결 리스트 : 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조 : 순서 리스트는 논리적인 순서와 물리적인 순서가 일치함 : 단순 연결 리스트는 순서 리스트 운영에서의 문제점을 보완하기 위해 만들어진 구조로서 각 원소들을 저장 공간의 위치에 상과없이 유연하게 처리하기 위해서 리스트에 포인터를 포함시킨 표현방법을 사용한다. : 데이터 부분에는 저장되는 원소가 있고, 링크 부분에는 다음 노드의 위치를 가리키는 포인터 값을 저장한다. 만약 다음 데이터가 없는 마지막 값일 경우에는 null 값으로 표현된다. : 이런 방식으로 원소가 추가되거나 삭제되었을때 리스트 전체의 순서를 바꿀필요가 없어지게 된다. -> 원소의 삭제, 삽입에 대해 시간복잡도는 상수 시간인 O(1)이 된다. : 또한 노드를 생.. 2021. 4. 18.
자료구조(12) - 데크 - 데크 : 양 쪽에서 데이터의 삽입과 삭제가 모두 이루어지는 자료구조이다. : 데크는 스택과 큐를 혼합한 구조로 하나의 배열을 선언한 수 2개의 포인터로 양쪽 끝을 가리킴으로 양쪽에서 삽입, 삭제가 이루어지는 구조이다. : 데크를 표현하는 방법에는 1차원 배열 형태인 스택을 이용하는 방법과, 단순 연결 리스트나 이중 연결 리스트를 이용하여 표현하는 방법이 있다. : 하지만 연결 리스트를 이용한 구현은 연결 구조를 위한 포인터 기억 공간을 더 요구하게되는 문제점이 있다. : 데크는 양쪽 끝에서 삽입과 삭제가 일어나므로 항상 2개의 포인터를 필요로 한다. 데크는 양쪽 끝에서 원소들의 삽입과 삭제에 제한을 두어 리스트의 어느 한쪽 끝에서 삽입과 삭제가 가능하도록 할 수 있다. - 스크롤, 입력제한데크 : 입.. 2021. 4. 17.
자료구조(11) - 원형 큐 ( Queue ) - 원형 큐( Queue ) : 책의 설명보다는 이해한바로 전달하도록 하겠다. 책의 표현이 너무 복잡해서 한참을 읽어보았다. : 전체 크기가 5인 큐( Queue )가 있다. : 우선 원소 5개를 enQueue 했다고 하자, rear는 4가 되었다. -> 4개의 원소를 deQueue를 하자. -> rear = 4, front = 3이 되었다. -> 실제 들어간 원소는 1개, -> rear는 최대치까지 올랐기때문에 더이상 들어갈 자리가 없다. -> 입/출력이 서로 다르며, 유기적인 변화가 없기때문에 1회용 저장공간이 된 것이다. -> 이를 잘못 인식된 포화상태라고 표현하며 이름 해결하기위해 원형 큐( Queue )를 구성하게된다. 까지 확인했었다. : 원형 큐를 문자화하려면 %연산자가 필요하다. 상기의 내.. 2021. 4. 16.
자료구조(10) - 큐 - 큐 : 큐는 리스트의 한쪽 끝에서 원소를 삽입, 반대쪽 끝에서 원소의 삭제가 일어나는 구조이다. : 먼저 삽입된 원소가 가장 먼저 삭제된다. : FIFO ( First In First Out ) : 일상생활의 한줄서기와 같다. : 큐의 포인터는 REAR과 FRONT 두개이다. : REAR는 삽입 : FRONT는 삭제가 이뤄진다. : 큐에서의 원소삽입 : enQueue ( rear ) : 큐에서의 원소삭제 : deQueue ( front ) : 방식은 삽입하는 길과 삭제하는 길이 다르다는 것을 제외하면, 스텍과 동일하다. : 큐에서 원소를 삽입하기위해 rear 포인터를 1증가 시키고 원소를 삽입하게 된다. : 계속해 rear포인터를 증가시키면 상한값에 도달하면 더 이상 원소를 삽입할 수 없다. : 큐에.. 2021. 4. 16.
자료구조(9) - 스택 - 스택이란 : 스택은 자료구조의 한 종류 : 원소의 삽입과 삭제가 리스트의 한 쪽 끝에서만 이루어지는 구조. : 구조적 특징과 내부에 순서가 있음으로 : 후입선출 ( LIFO : Last In First Out ) : 선입후출 ( FILO : First In Last Out ) 특징을 갖는다. : 그림이 사실 스택의 거의 모든 걸 담고있다. : 삽입과 삭제가 되는 곳이 한 곳( TOP POINTER )이기 때문에, 많은 표현이 TOP POINTER를 통해 이루어지게 된다. 예를들면 TOP POINTER = 0 일 경우, 스택은 비어있는 상태를 의미한다. TOP POINTER >= n ( 단, n은 스택의 크기 ) 일 경우, 스택이 가득차 있는 상태이다. TOP POINTER는 포인터이므로 원소가 추가될.. 2021. 4. 16.

티스토리툴바