Data Structure

자료구조 - 그래프

그래프는 지하철 노선도처럼 노드 사이의 연결 관계를 표현할 수 있는 자료구조다. 이에 대해 자세히 알아보자. 그래프의 역사 그래프는 수학자 오일러의 "Konigsberg Bridge Problem - 쾨니히스베르크의 다리 문제"에서 시작했다. 이 문제는 아래 그림과 같이 다리가 연결되어 있는데 임의의 지역에서 모든 다리를 한 번만 건너 출발했던 지역으로 돌아올 수 있는가이다. 오일러는 위 문제를 아래와 같이 간단한 그림으로 표현했으며 토지를 정점, 다리를 간선으로 대체했다. 이것이 그래프(Graph)이다. https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg Seven Bridges of Königsberg - Wikipedia From Wiki..

자료구조 - Stack, Queue, Deque

Stack과 Queue는 여러 알고리듬에 사용되는 간단하면서도 중요한 자료구조이다. 이 둘에 대해 알아보자. Stack Stack은 후입선출(LIFO: Last In First Out) 형태의 자료구조로 데이터 삽입과 삭제가 한쪽에서만 일어난다. 간단하게 용어를 살펴보면 아래와 같다. 실생활의 경우를 예로 들면 웹페이지 뒤로 가기 기능, 쌓아놓은 상자 등이 있다. 메서드를 호출할 때에도 스택이 활용되는데, 아래 코드를 보자. public static void main(String[] args) { System.out.println("main 메서드 시작"); method_1(); System.out.println("main 메서드 종료"); } static void method_1() { System.o..

자료구조 - 전위, 중위, 후위 표기법

전위, 중위, 후위 표기법을 정리해보고자 한다. 전위, 중위, 후위 표기법 위 3가지 표기법의 차이점은 연산자의 위치이다. 전위 표기법(Prefix)은 연산자가 피연산자 앞에, 중위 표기법(Infix)은 연산자가 피연산자 사이에, 후위 표기법(Postfix)은 연산자가 피연산자 뒤에 온다. 1 + 2 * (3 - 4) * 5라는 식을 예로 들었을 때 전위 표기법은 + 1 * * 2 - 3 4 5 후위 표기법은 1 2 3 4 - * 5 * +이다. 이제 어떻게 변환이 되는 것인지 알아보자. 중위 표기법을 전위 표기법 & 후위 표기법으로 중위 표기법을 전위, 후위 표기법으로 바꾸는데 가장 많이 쓰이는 방법은 괄호를 이용하는 것이다. 먼저 전위 표기법의 변경 순서는 다음과 같다. 1. 연산 순서대로 괄호를 묶..

자료구조 - 이진 트리(전위, 중위, 후위, 레벨 순회)

계산기를 구현하던 중 이진 탐색 트리 순회가 필요해져 내용을 정리해보려 한다. 용어 정리 내용에 대해 알아보기 전에 트리와 관련된 용어를 알아보자. 아래와 같은 모양을 가진 트리가 있다고 했을 때, A, B, C, D, ... 각각을 노드(Node)라고 하며 최상위에 있는 A를 루트(Root)라고 한다. 각 노드는 간선(Edge)으로 이어져 있다. 루트 아래의 노드들은 A의 서브트리라고 하는데 예를 들어 노란 상자가 A의 서브트리이며 해당 서브트리의 루트는 B이다. 해당 서브노드에서 B는 D, E, F의 부모노드(Parent Node), D, E, F는 B의 자식노드(Children Node)이다. 층수가 내려갈수록 레벨(Level)이 1씩 증가하는데, 같은 레벨의 노드들을 형제노드 혹은 형제관계에 있다..