분류 전체보기

1. 트리란? - 구성하는 요소는 노드(node)와 가지(edge)로 이루어집니다. - 데이터 사이의 계층 관계를 나타내는 자료구조 루트 : 트리의 가장 윗부분에 위치하는 노드 리프 : 물리적으로 가장 아랫부분에 위치하는 노드, 끝 노드(terminal node) 또는 바깥 노드(external node)라고도 한다. 안쪽노드 : 루트를 포함하여 리프를 제외한 노드를 안쪽 노드, 끝이 아닌 노드(non-terminal node)라고도 한다. 자식 : 어떤 노드로부터 가지로 연결된 아래쪽 노드를 자식(child)이라고 한다, 리프는 자식을 가질 수 없다. 부모 : 어떤 노드에서 가지로 연결된 위쪽 노드를 부모(parent)라고 한다, 루트는 부모를 가질 수 없다. 형제 : 같은 부모를 가지는 노드를 형제(..

1. 커서(cursor)로 연결 리스트 만들기 연결 리스트는 '노드의 삽입, 삭제를 데이터 이동 없이 수행한다'라는 특징이 있었지만 삽입, 삭제를 할때마다 노드용 객체를 메모리 영역을 만들고 해체하는 과정이 필요했습니다. 이 과정에 소모되는 비용은 결코 무시할수 없습니다. 그러므로 데이터 수가 크게 바뀌지 않고 데이터 수의 최대값을 미리 알수 있다면 아래와 같이 효율적인 연결 리스트를 운용할수 있습니다. 프리 리스트)이 프로그램에서 삭제한 여러 레코드를 관리하기 위해 사용하는 것이 그 순서를 넣어두는 연결 리스트인 프리 리스트(free list)입니다. - 프리 리스트 + 커서 연결리스트 코드- AryLinkedList : - AryLinkedListTester : 2. 원형 이중 연결 리스트 - 더미노..

1. 선형리스트(linear list)란? - 리스트는 데이터를 순서대로 나열해 놓은 자료구조 - 리스트의 데이터는 노드(node) 또는 요소(element)라고 하며 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있음. - 연결 리스트(linked list)라고도 부름. - 처음과 끝에 있는 노드는 각각 머리노드(head node), 꼬리 노드(tail node)라고 함. - 앞에있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고함. 선형 리스트의 문제점 1) 쌓이는 데이터의 크기를 미리 알야아함 2) 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 못함.2. 포인터로 연결 리스트 만들기 데..

1. 브루트-포스법(brute force method)텍스트 "ABACDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용해 검색할수 있습니다. 브루트-포스법은 선형 검색을 확장한 알고리즘이므로 단순법, 소박법이라고도 부릅니다. - 코드 String.indexOf 메서드로 이용이 가능합니다.https://docs.oracle.com/javase/8/docs/api/java/lang/String.html Modifier and TypeMethod and DescriptionintlastIndexOf(int ch)Returns the index within this string of the last occurrence of the specified character.intlastIndexOf(int ch..

1. 힙정렬이란?힙정렬(heap sort)은 힙(heap)을 사용하여 정렬하는 알고리즘.힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리이때 부모의 값이 자식보다 항상 작아도 힙이라고 합니다. (부모와 자식 요소의 관계만 일정하면 됨) 힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립합니다. 1) 부모는 a[(i-1)/2] 2) 왼쪽 자식은 a[i*2+1] 3) 오른쪽 자식은 a[i*2+2] 이제 힙정렬 해보겠습니다. 이런방법으로 계속 진행됩니다. 이제는 정렬되지 않은 배열을 힙으로 만들어보겠습니다.bottom-up 방식) - 힙 정렬의 시간 복잡도힙정렬은 선택정렬을 응용한 알고리즘입니다. 힙정렬에서는 첫 요소를 꺼내는 것만으로 가장 큰 값이 구..