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

재귀호출은 반복적으로 자기 자신을 호출하는 것을 말한다. 가장 친근한 예시로는 수학에서 찾아볼 수 있는데, 팩토리얼이나 피보나치가 있다. 재귀호출은 비선형 자료구조에 기반을 둔 알고리즘에 자주 사용이 된다. 예를 들어 tree 또는 graph의 노드 탐색이 있겠다. 재귀의 큰 특징은 종료 조건이 반드시 존재한다는 것이다. base case(최소한계)라고도 부르며 이것이 존재하지 않으면 시스템 스택에서 에러가 발생한다. 이 부분에 대해서는 밑에서 OS 관점에서의 재귀에 대해 설명하면서 다시 언급하겠다. 어쨋든 재귀는 하나의 큰 문제를 여러 개의 작은 문제로 쪼개어 해결한다는 점에서 Divide and Conquer(분할정복)이라 부를 수 있다. 재귀호출은 3가지로 분류된다. 1. Linear Recursi..