뚝딱뚝딱QA

트리는 상위에서 하위 노드로 확장되는 계층구조를 나타내는 비선형 자료구조이다. 아래는 트리 중에서 가장 일반적인 binary tree 구조이다. 이진 트리는 결정트리, 산술식 트리, 탐색 트리 등에 사용된다. term description root 부모 노드가 없는 최초의 노드 ex) A ancestor 자식 노드가 있는 노드 ex) A, B, C, D descendent 부모 노드가 있는 노드 ex) B, C, D, E, F, G, H, I sibling 동일한 부모 노드를 가진 노드 ex) B와 C, D와 E, F와 G, H와 I subtree 루트를 제거했을 때 생기는 하위 트리, 하위 트리의 집합을 forest라고 부른다. internal node 루트를 포함하여, 부모 노드와 자식 노드를 둘 다..

스택은 LIFO, 큐는 FIFO 라는 것만 알아도 다 이해했다해도 무관할 정도로 스택과 큐는 구현도, 사용도 너무나 쉬운 자료구조이다. 그만큼 자주 쓰이기도 하니 꼭 알아두자. 스택은 Last in First out 으로, 후입선출의 구조이다. 아래 그림처럼 먼저 들어간 값이 가장 아래에 쌓이기 때문이다. 이러한 구조는 웹 브라우저의 뒤로가기, 텍스트 에디터의 ctrl+z, JVM의 chain of method call(ex. recursion call) 등에 사용이 된다. 스택을 사용하기 위해서 자바에서 제공해주는 클래스 java.util.stack을 사용하여도 좋다. 스택 클래스에서 제공하는 메소드는 아래와 같다. method description boolean isEmpty() 스택이 비었는지를 확..

선형 자료구조인 리스트는 그 종류가 다양하다. 그 중에서 가장 대표적인 배열리스트(array list), 단순연결리스트(linked list), 이중연결리스트(doubly linked list)에 대해서 정리해보았다. 배열리스트는 배열을 이용한 리스트형 자료구조로, 자바에서 지원해주는 클래스인 import java.util.ArrayList; 를 사용하면 된다. 구현이 매우 간단하며 탐색 시 인덱스를 이용할 수 있어서 탐색속도가 월등하다는 장점이 있다. 따라서 탐색, 정렬을 자주 하는 경우엔 배열리스트를 사용한다. 해당 클래스에는 아래와 같은 메소드들이 저장되어 있다. 참고로 이 메소드들을 이용해서 Deque를 구현할 수 있다. 메소드 설명 int size() 배열의 크기 러틴 boolean isEmpt..