study/Data structure9 Heaps Heap is a binary tree. Heap can have duplicates. max heap min heap max heap, min heap이 있다. binary tree 형태를 가지고 있다. 중복값이 있을 수 있다. 부모노드들 중 하나보다 작기만 해도 됨. 힙을 어레이구조로 저장한다고 하면 맨 위 노드가 index 1, 2번째 줄 왼쪽노드 index 2, 오른쪽 노드 index 3 … 이런식으로 순차적으로 저장된다. - 이 상황에서 노드의 자식들을 구하려면 leftChild = 2 * parentIndex rightChild = 2 * parentIndex + 1 결과 값은 계산에 적용된 부모노드의 왼쪽노드 오른쪽 노드의 인덱스 값이다. - 반대로 노드의 부모노드를 찾기 위해서는 2로 나누.. 2023. 9. 10. Graph 그래프에서 한 노드를 vertex라고 부름 연결을 connection 또는 edge라고 부름 하나의 vertex는 여러 vertex와 연결될 수 있다. 양방향 연결되어 있다. adjacency Matrix 양방향으로 연결되어 있는 경우에만 대조되는 모습을 보인다. adjacency List 리스트로 표현하면{ "A"= ["B","E"], "B"= ["A","C"], "C"= ["B","D"], "D"= ["C","E"], "E"= ["A","D"] } Big Oadd vertexadjacency Matrix방법으로 표기할 경우하나의 vertex를 추가하려면 원래 있는 vertex의 수 + 1의 제곱만큼의 칸을 만들어야 한다. ⇒ 0(n^2)반면 adjacency list의 방법의 경우 빈 리스트를 추가하.. 2023. 9. 3. HashTable 인덱스 찾기hash라는 메서드로 노드의 인덱스를 정한다. hash method 특징 one way 키로 주소(인덱스)를 알아낼 수는 있는데 인덱스로 키를 알아내지는 못함 Deterministic 주소고정 how to deal with collision 순서보장 안됨 같은 주소에 여러개 저장 - separate chaining 이미 다른게 저장되어있으면 빈거 찾을때까지 다음으로 - Linear Probing (open addressing) 우리가 할 것은 seperate chaining. big Ohash method = 0(1) set = 0(1) get = 0(1) - seperate chaining 일때. 2023. 8. 27. Trees binary search tree 트리(Tree)는 계층적인 구조를 나타내는 자료구조이다. linked list 도 tree 의 일부분으로 볼수도 있다. 분기가 나눠지지 않은 트리는 링크드 리스트와 똑같이 생겼을 것이다. tree 에는 2개의 포인터가 있다. left and right 해당 노드의 값보다 작으면 left에 붙이고 크면 right에 붙인다. 결과적으로 부모노드의 오른쪽에 있는 노드들은 부모노드의 값보다 큰 값을 가지고 있는 노드들이 오게되고 왼쪽에는 부모노드보다 작은 노드들이 오게된다. 트리 자료구조의 구성요소 parent child leaf - 더이상 차일드가 없는 노드 tree에는 3가지 상태가 있는데, full tree, perfect tree, complete tree 가 있다. f.. 2023. 8. 17. stack and queue Stacks선입후출 LIFO 구현 예시는 웹브라우저의 뒤로가기. 뒤로가기를 누르면 우리가 마지막으로 접속했던 페이지가나오고, 마지막 전에 방문한 페이지에 가려면 뒤로가기를 2번 눌러야함. 보통 arraylist를 사용. 마지막에 넣고 빼고 하는것은 나머지 요소들의 인덱스를 조정할 필요가 없기때문에 0(1) 나머지 prepend, push sth back같은것들은 0(n) linked list로도 구현 가능 linked list 로 stack을 구현할거면 맨밑에 노드가 null을 가리키게하는게 좋다. 왜냐면 그렇게 하는게 stack에서 선입선출을 할때 시간복잡도가 떨어지기 때문이다. 맨 위의 노드가 마지막 노드가 되게하면 맨마지막노드의 전 노드를 tail로 지정하기위해 찾아야하는데 인덱스가 따로 없어 반복.. 2023. 8. 11. Doubly linked list linked list와 다른점 하나. node에 이전 노드를 가리키는 포인터가 추가되었다. 포인트 2개 삽입 및 삭제가 용이. 삽입 또는 삭제 연산을 수행할 때, 해당 노드의 이전 노드와 다음 노드를 적절하게 연결하면 됨. 노드를 삽입하거나 삭제하는 작업이 단일 연결 리스트보다 간단하게 처리가능. 단일 연결 리스트에 비해 메모리 공간이 더 많이 사용됨. 각 노드마다 이전 노드와 다음 노드를 가리키는 두 개의 포인터가 추가로 필요하기 때문이다. append 0(1) public void append(int value){ Node newNode = new Node(value); if(length == 0){ head = newNode; tail = newNode; }else{ //link new node t.. 2023. 8. 4. 이전 1 2 다음 728x90
