CS/자료구조 (7) 썸네일형 리스트형 [자료구조] Binary Tree Binary Tree 모든 노드가 최대 2개의 자식노드를 가질 수 있는 트리 자료구조 여러 종류의 binary tree에 대해 알아보자 ! Full Binary Tree : 정이진트리 모든 노드가 0개 혹은 2개의 자식노드를 가지고 있는 이진트리 L = B + 1 L = leaf nodes, B = branch(non leaf) nodes Complete Binary Tree : 완전이진트리 왼쪽부터 차례대로 채워져있는 이진트리 모든 자식 노드가 채워질 경우 포화이진트리 가 된다 cf. 부모 노드가 항상 자식 노드보다 작은 형태의 완전 이진 트리가 최소 Heap 이다. Perfect Binary Tree : 포화이진트리 모든 branch node가 2개의 자식노드를 가지고 있고, 모든 leaf 노드가 같.. [자료구조] Hash 해시 함수 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 가장 유명한 함수로는 modular 연산이 있고, 그 외의 여러 함수가 존재한다. h(x) = x mod 13 좋은 해시 함수의 조건 계산이 간단해야 한다. 입력 원소가 테이블 전체에 고루 저장되어야 한다. 하지만 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정에서 충돌이 존재한다. 예를 들어 h(x) = x mod 13 인 해시함수에서, x가 4, 17인경우 h(x), 즉 해시값은 동일하게 4로 매핑되며 이것을 해시 충돌(Hash Collision)이라고 한다. if(h(x1) == h(x2)) collision! 해시 충돌 해결 방법 1. chaning hash table의 각 cell(bucket)을 linked l.. [자료구조] Doubly Linked List Doubly Linked List Singly Linked List가 단방향 연결 리스트로, 다음 노드를 가리키는 포인터를 갖고있다면 Doubly Linked List는 양방향(이중) 연결 리스트로, 다음 노드와 이전 노드를 가리키는 포인터를 갖는 자료구조이다. Java Collection Library 에서 사용가능한 LinkedList는 Doubly Linked List 이다 Singly Linked List와 비교했을 때 다음과 같은 장단점이 있다 장점 탐색이 비교적 빠르다 Singly Linked List는 다음노드의 포인터만을 갖고있어 노드 탐색 시 순방향으로 탐색만이 가능 Doubly Linked List는 이전노드의 포인터를 갖고있어 마지막 노드(tail)부터 역방향 탐색이 가능하다 단점 이.. [자료구조] Singly LinkedList Singly LinkedList Node라는 객체를 단방향으로 하나의 체인처럼 연결한 리스트 Node Node는 사용자가 저장할 data와 다음에 연결할 노드를 가리키는 reference를 담고 있다 위와 같은 노드들이 아래과 같이 여러개 연결되어있는 것을 LinkedList라고 한다 또한 단방향으로 연결되어있을 경우 Singly LinkedList라고 한다 조회 성능이 좋진 않지만 삽입/삭제 시 링크만 바꿔주면 되기 때문에 효율적이다. Singly LinkedList Implement in JAVA Node.java class Node { E data; Node next; Node(E data){ this.data = data; this.next = null; } } List.java add() met.. [자료구조] Stack Stack 말 그대로 쌓는다는 의미로 이름 지어진 자료구조로 한 쪽 끝에서만 자료를 넣거나(push), 뺄 수(pop) 있는 후입선출(LIFO, Last In First Out)의 선형 구조 구조에 맞게 삽입/삭제하는 경우 : O(1) 비어있는 스택에서 원소를 추출 : stack underflow 스택 크기를 초과하여 데이터를 넣는 경우 : stack overflow Stack의 활용 재귀 알고리즘 DFS (깊이우선탐색) 괄호 정합성 판단 웹 브라우저 방문기록 (뒤로가기) reference https://velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue https://ww.. [자료구조] Array vs List Array 연속된 메모리 공간에 순차적으로 저장된 선형 자료구조 논리적 저장순서와 물리적 저장 순서가 일치 따라서 index로 원소에 접근 가능 정의와 동시에 길이 지정 (고정길이) 장점 인덱스를 통한 검색 용이 연속적이여서 메모리 관리 편리 단점 크기 변경 불가 메모리 낭비 (원소 삭제 후 해당 공간이 빈 상태로 유지됨) 시간복잡도 조회 : O(1) 삽입/삭제 : - 맨 앞 혹은 중간 삽입/삭제 시 : O(n) ⟹ 삽입/삭제 O(1) + 위치조정 O(n) - 맨 뒤 삽입/삭제 시 : O(1) List 연결된 노드의 연속으로 이루어진 선형 자료구조 각 노드는 데이터와 다음 노드의 주소를 저장 논리적 저장순서와 물리적 저장 순서가 불일치 장점 포인터를 통해 다음 데이터의 위치를 가리키고 있어 삽입/삭제 용.. [자료구조] 자료구조란? 자료구조란 데이터를 효율적으로 사용할 수 있도록 데이터를 표현하는 방식이다. 크게 선형 구조와 비선형구조로 나누어진다. 어떤 자료구조를 사용하느냐에 따라 프로그램의 효율성과 성능에 큰 영향을 끼치기 때문에 상황에 따라 적절한 자료구조를 선택 후 사용해야한다. 이전 1 다음
