고양이 두 잔

목차 Tree Traversals 특정 목적을 가지고 모든 노드를 한 번씩 방문하는 것을 트리 순회라 한다. 순회 방법은 크게 네 가지가 있으며, 공통적으로 왼쪽에서 오른쪽으로 진행한다. 이진트리는 그 정의상 서브 트리 역시 이진트리이기 때문에, 재귀 함수를 적용하기 편하다. 먼저 루트와 좌 우 서브트리 순서에 따른 분류를 보자. 전위 순회(Preorder Traversal)는 VLR의 순서로 방문한다. 아래와 같다. 참고로 이 방식은 그래프 순회의 깊이 우선 탐색(DFS)과 동일한 방법이다. 이어서 중위 순회(Preorder Traversal) 순회는 LVR이다. 아래와 같다. 마지막으로 후위 순회(Postorder Traversal) 순회는 LRV이다. 아래와 같다. 추가로 VRL 분류와 별개로 레벨..

목차 Stack Stack은 더미, 쌓다 등의 의미를 지니고 있다. 하나의 입출력 방향만을 가진 구조에 데이터를 넣는 것으로 생각할 수 있는데, 때문에 가장 큰 특징은 후입 선출 구조라는 점이다. 추가로 데이터를 한 번에 하나씩만 넣고 뺄 수 있다는 특성도 존재한다. 주로 브라우저의 앞으로 가기나 뒤로 가기, 실행 취소(컨트롤+z), 혹은 함수의 호출이나 재귀 함수 역시 스택에 기반을 두고 있다. 보통 고정된 크기를 가지기 때문에 다 사용하면 넘치게 되며, 이를 스택 오버플로우라고 부른다. Queue 이에 반해 큐는 입력과 출력의 방향이 따로 정해진, 선입선출 구조를 지니고 있다. 스택과의 공통점은 데이터를 한 번에 하나씩만 넣거나 뺄 수 있다는 점이 있으며 프린터의 출력 알고리즘 같은 작업/데이터의 순..

이전에 자료구조에 대한 글을 올리면서 트리에 대해 다룬 적이 있다. 2022.07.26 - [Development/Java] - [Java]자료구조 - Tree [Java]자료구조 - Tree Tree 자료구조 Tree(트리)는 주로 계층적인 구조를 표현하기 위해 사용한다. /Users/username 토너먼트 경기의 대진표 조직도 트리구조는 루트(Root)라는 최상위 노드에서 시작해 각 데이터를 간선(Edge, gnidinger.tistory.com 그리고 최근 우선순위 큐에 대해 다루면서 내부적으로 O(log N)의 힙(Heap)을 사용한다고 언급했었는데, 2022.09.23 - [Development/Java] - [Java]우선순위 큐(Priority Queue) 튜토리얼 [Java]우선순위 큐(..

이전에 자료구조에 대해 얕게 공부하면서 큐(Queue)에 대한 글을 올린 적이 있다. 2022.07.25 - [Development/Java] - [Java]자료구조 - Queue [Java]자료구조 - Queue Queue는 (대기)줄이라는 의미를 가지고 있다. 위 그림에서 보는 것처럼 데이터의 입력과 출력 방향이 따로 정해져 있으며, 먼저 들어간 데이터가 먼저 나오는 선입 선출(FIFO - First In First Out) 구조 gnidinger.tistory.com 먼저 큐에 대해 복습하자. 큐는 대기줄이라는 의미를 가지고 있다. 위 그림처럼 데이터의 입력과 출력 방향이 따로 정해져 있으며, 먼저 들어간 데이터가 먼저 나오는 선입선출(FIFO - First In First Out) 구조로 이루어져..

그래프의 탐색은 모든 정점을 한 번씩 방문하는데 그 목적이 있다. 지도 애플리케이션에서 두 지점 사이의 경로를 검색할 경우를 생각 해보면, 최소 시간이나 최소 환승 등 여러 가지 검색 기준이 있다. 이와 비슷하게 그래프의 모든 정점을 방문하는 방법에도 크게 두 종류가 있는데, BFS(Breadth-First Search) - 너비 우선 탐색과 DFS(Depth-First Search) - 깊이 우선 탐색이 그것이다. BFS(Breadth First Search) 너비 우선 탐색(BFS)은 시작 정점부터 가장 가까운 순서대로 정점을 방문하는 방법이다. 최초 시작 정점과 인접한 정점을 모두 방문한 뒤, 각 순회된 정점부터 시작하여 인접한 정점을 방문하는 방식을 반복한다. 출처: https://minhamin..

Graph(그래프)는 노드 사이의 연결 관계를 표현할 수 있는 자료구조이다. 앞서 보았던 트리구조 역시 사실은 그래프의 일종인데, 두 구조의 차이는 아래와 같다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 단방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능 순환 불가능 자기 자신을 연결하는 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 루트의 개념이 있거나 없을 수 있음 하나의 루트 노드 존재 모델 네트워크 모델 계층 ..

Tree 자료구조 Tree(트리)는 주로 계층적인 구조를 표현하기 위해 사용한다. /Users/username 토너먼트 경기의 대진표 조직도 트리구조는 루트(Root)라는 최상위 노드에서 시작해 각 데이터를 간선(Edge, Link, Branch)으로 연결한다. 두 개의 노드가 상하관계를 가질 때 위의 노드를 부모 노드(Parent Node), 아래의 노드를 자식 노드(Child Node)라 부른다. 자식 노드가 없는 노드를 리프 노드(Leaf Node)라고 하며, 리프 노드를 제외한 노드를 인터널 노드(Internal Node)라 부른다. 또한 트리구조는 깊이와 레벨, 높이를 측정할 수 있는데 그 정의는 아래와 같다. 깊이(Depth) - 루트로부터 특정 노드까지의 간선 개수. 위 Animal의 경우 ..

Queue는 (대기)줄이라는 의미를 가지고 있다. 위 그림에서 보는 것처럼 데이터의 입력과 출력 방향이 따로 정해져 있으며, 먼저 들어간 데이터가 먼저 나오는 선입 선출(FIFO - First In First Out) 구조를 가지고 있다. 또한 스택의 경우와 마찬가지로 데이터의 입출력을 하나씩만 할 수 있다는 특징도 가지고 있다. 추가로 큐에 데이터를 집어넣는 동작을 'enqueue'라고 하며, 데이터를 빼는 동작을 'dequeue'라고 부른다. 주로 프린터의 출력 순서 알고리즘과 같이 이벤트의 실행 순서를 규칙적으로 만들기 위해 사용되는 큐는 태생적으로 LinkedList와 함께 사용된다. import java.util.LinkedList;//import import java.util.Queue;//i..

Stack은 더미, 퇴적, 쌓다 등의 의미를 지니고 있다. 하노이의 탑 퍼즐에서 기둥에 원판을 꽂듯이 데이터를 쌓는 구조라고 할 수 있는데, Stack(스택)의 가장 큰 특징은 바로 이 퍼즐과 같이 후입 선출(LIFO - Last In First Out)로 동작한다는 것이다. 설명을 추가로 덧붙이자면 스택 자료구조는 반드시 데이터를 하나씩만 넣고 뺄 수 있고, 그림에서 보이는 것과 같이 단 하나의 입출력 방향을 가지고 있다. 브라우저의 앞으로 가기나 뒤로 가기 기능을 구현할 때 사용되는 스택 자료구조는 간단하게 사용 가능하다. import java.util.Stack; // import Stack stack = new Stack(); // Integer형 스택 선언 위와 같이 먼저 Stack 클래스를 i..

재귀 함수는 위 그림처럼 정의 단계에서 자기 자신을 다시 호출하는 함수를 말한다. 수학으로 봤을 땐 점화식이라고 생각하면 편하다. f(n) = f(n - 1) + n // 점화식 재귀 함수를 활용하면 반복적인 작업을 해야 하는 문제를 간결하게 풀 수 있는 경우가 있다. 반면 코드에 대한 직관적인 이해가 어렵고, 메모리를 많이 사용하게 된다는 단점도 존재한다. 재귀 함수에 익숙해지기 위해선 문제를 작게 쪼개는 연습을 하는 게 중요한데, 가장 간단한 예 중 하나인 팩토리얼로 예를 들어보자. 먼저 팩토리얼은 다음과 같이 계산한다. n! = n * (n - 1) * (n - 2) * ... * 2 * 1 0! = 1 1부터 n까지의 모든 자연수를 곱하는 계산이라고 생각하면 된다. 먼저 이 계산을 반복문을 통해 ..