하고 싶었던 그리고 하고 싶은 일

힙 (Heap) 힙 (Heap) : 최대값과 최소값을 바르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree) 힙 (Heap) 사용 이유 배열로 최소/최대를 찾으려면 O(n) 으로 걸림 힙 (Heap) 으로 최소/최대를 찾으면 O(logn) 으로 걸림 우선순위 큐와 같이 최소/최대값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 활용됨 구조 최소값을 구하는 힙 (최소 힙, Min Heap) 과 최대값을 구하는 힙 (최대 힙, Max Heap) 으로 분류 힙은 아래 조건을 가지고 있는 자료구조 최대 힙 경우 각 노드의 값이 자식 노드가 가진 값보다 크거나 같음 최소 힙 경우 각 노드의 값이 자식 노드가 가진 값보다 크거나 작음 완전 이진 트리 형태 힙 데이터 삽입 - 기본 힙은 ..

트리와 이진 탐색 트리 - 2 이진 탐색 트리 삭제 삭제는 많이 복잡하지만 로직만 잘 세우면 단순한 것 같음 Leaf Node 삭제 (제일 마지막 노드 삭제) Child Node 가 하나인 Node (중간 노드 삭제) Child Node 가 두개인 Node (중간 노드 삭제) 삭제할 Node 찾기 public boolean delete(int value) { boolean search = false; Node curParentNode = this.head; Node curNode = this.head; // Node 가 하나도 없을 경우 if(this.head == null) { return false; // Node 가 하나만 있고 해당 Node 를 삭제 할 경우 } else { if(this.head..

트리와 이진 탐색 트리 - 1 트리 (Tree) 구조 트리 (Tree) : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 이진 트리 (Binary Tree) 형태의 구조로, 탐색 (검색) 알고리즘 구현을 위해 많이 사용됨 용어 Node : 트리에서 데이터를 저장하는 기본 요소 Root Node : 트리 맨 위에 있는 노드 (Root) Level : 최상위 노드를 Level 0 으로, 하위 노드로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 상위 레벨에 연결된 노드 (부모 노드) Child Node : 어떤 노드의 상위 레벨에 연결된 노드 (자식 노드) Leaf Node (Terminal Node) : Child Node가 없는 노드 Sibling (B..

해쉬 테이블 (HashTable) 키 (Key) 에 데이터(Value) 를 매핑할 수 있는 데이터 구조 키 (Key) 를 통해 주소를 알 수 있으므로, 저장 및 탐색 속도가 빨라짐 용어 해쉬 함수 (Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 해쉬 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해쉬 테이블 구현 public class Hash { public Slot[] hashTable; public Hash(Integer size) { this.hashTable = new Slot[size]; } public class Slot { String value; Slot(String value) { this.value = va..

더블 링크드 리스트(Doubly linked list) 이중 연결 리스트 양방향으로 연결되있어, 탐색이 양쪽으로 가능함 더블 링크드 리스트 구현 public class DoubleLinkedList { public Node head = null; puclic Node tail = null; public class Node { T data; Node prev = null; Node next = null; public Node(T data) { this.data = data; } } /* * 추가 */ public void add(T data) { if(this.head == null) { this.head = new Node(data); thus.tail = this.head; } else { Node n..

링크드 리스트 (Linked List) 연결구조 리스트 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터구조 알아야 할 용어 노드 (Node) : 데이터 저장 단위 (포인터) 로 구성 포인터 (Pointer) : 하나의 노드에서 다음/이전 노드의 연결 정보를 가지고 있는 공간 링크드 리스트 형태 링크드 리스트 장/단점 배열과 다르게 미리 공간 할당을 하지 않아도 됨 연결정보를 담는 공간이 필요, 저장공간 효율이 높지 않음 접근 속도가 느림 중간 데이터 삭제 시 앞뒤 연결을 재구성 해야함 링크드 리스트 구현 (한번쯤은 코드 작성하면서 이해하기) public class SingleLinkedList { puclic Node head = null; public class Node { T data..

스택 (Stack) 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 (LIFO) 운영체제가 사용하는 시스템 스택이 이와 같은 구조 스택 (Stack) 선언 스택은 java.util 패키지에서 Stack 제공 import java.util.Stack; Stack stack = new Stack(); 스택 (Stack) 넣기 // push() 시 해당 value값 리턴함 stack.push(1); // Stack 에 1 추가 stack.push(2); // Stack 에 2 추가 stack.push(3); // Stack 에 3 추가 스택 (Stack) 꺼내기 // 제일 마지막으로 넣은 데이터가 꺼내짐 stack.pop(); 스택 (Stack) ..

큐 (Queue) 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식 프로세스 스케쥴링에 많이 쓰임 큐 (Queue) 선언 큐는 java.util 패키지 LinkedList 를 사용해 선언해야 함 import java.util.LinkedList; import java.util.Queue; Queue queue = new LinkedList(); 큐 (Queue) 추가 /* * 해당 큐 맨 뒤에 값 삽입 * 값 추가 성공 시 true 반환 */ queue.add(1);// 큐가 꽉 찬 경우 IllegalStateException 에러 발생 queue.offer(2);// 값 추가 실패 시 false 반..

배열 (Array) 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 순서 (index)를 가진 데이터의 집합 - 가장 기본적인 자료구조 생성과 동시에 크기가 고정됨 전체 원소가 메모리상 일렬로 저장됨 0 1 2 3 4 5 6 7 8 9 9 4 -3 10 2 0 3 7 8 10 장점 메모리가 연속적이기 때문에 빠른 접근 가능 (인덱스 번호로 접근) 단점 고정 길이라서 데이터 추가/삭제의 어려움 1차원 배열 [ ] 를 통해 선언 각 요소는 { } 내 콤마로 작성 // new 키워드를 사용해서, 배열을 미리 선언하고, 데이터를 넣을 수도 있음 Integer[] data = new Integer[10]; data[0] = 1; // 직접 배열 데이터 선언과 동시에 넣을 수도 있음 Inte..