WEB/자료구조

해시법(체인법, 오픈주소법)

- 해시법(hashing)은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할수 있음- 배열의 키 값(각 요소의 값)을 배열의 요솟수로 나눈 나머지를 표에 정리한 값을 해시 값(hash value)이라고 하며, 이 해시 값은 데이터에 접근할 때 사용 해시 검색과정) 1) 해시 함수가 키 값을 해시 값으로 변환 2) 해시 값을 인덱스로 하는 버킷을 선택 3) 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색. 키 값과 같은 값을 찾으면 검색 성공. 끝까지 스캔하여 찾지 못하면 검색 실패 요소 추가과정) 1) 해시 함수가 키 값을 해시 값으로 변환 2) 해시 값을 인덱스로 하는 버킷을 선택 3) 버킷이 가리키는 연결 리스트를 처음부터 순서대로 ..

트리 / 이진트리 / 완전이진트리 / 이진검색트리

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

커서(cursor)로 연결 리스트 만들기 / 원형 이중 연결 리스트

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. 포인터로 연결 리스트 만들기 데..

브루트-포스법 / KMP법/ Boyer-Moore법

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..