이진 트리의 구현 - (2)
2023. 2. 24. 16:57
DataStructure/Tree
들어가며 이번엔 연결 리스트를 통해 이진 트리의 구현을 수행한다. 우리가 구현할 연산은 다음과 같다. 원소의 삽입 원소의 삭제 임의의 위치에 존재하는 원소의 삭제 트리의 레벨, 전위, 중위, 후위 순회 임의의 노드의 부모 노드를 반환 트리에 존재하는 모든 노드의 개수 반환 이때 제한 조건 이전에 제시한 조건과 동일하다. 원소의 삽입과 삭제는 complete binary tree의 방식을 따른다. 임의의 위치에 존재하는 원소의 삭제 연산은 해당 원소에 딸려있는 모든 원소들을 삭제해야 한다. 조건해석과 구현 방법 이전에 수행했던 조건과 동일하므로 해석 역시 동일하다. 눈여겨보아야 할 점은 임의의 위치에 존재하는 원소의 삭제 연산이다. 해당 원소에 딸려있는 모든 원소를 삭제해야한다는 것은 해당 원소를 루트로 ..
이진 트리의 구현 - (1)
2023. 2. 24. 15:42
DataStructure/Tree
들어가며 이진 트리는 이전에 말했듯 배열과 연결 리스트로 구현이 가능하다. 이번에는 배열로 이진 트리를 구현하는 것을 해보도록 하겠다. 우리가 구현해야할 기능들은 다음과 같다. 트리에 원소를 추가 트리에 원소를 삭제 트리의 전위, 중위, 후위, 레벨 순회 구현 이때 따라붙는 제한 조건(구체적 조건)은 다음과 같다. 원소를 추가할 때는 complete binary tree의 방식을 따른다. 즉 좌에서 우로 원소를 추가해야한다. 원소를 제거할 때에는 우에서 좌로 원소를 삭제한다. 조건해석과 유의사항 원소를 추가할 때 complete binary tree의 방식을 따르므로 이 트리는 complete binary tree가 된다. 즉 리프 노드간의 높이 차이가 최대 1까지 존재하며, 우측 자식이 존재한다면 반드..
트리의 개념과 용어정리
2023. 2. 23. 21:23
DataStructure/Tree
트리의 정의 트리의 정의는 그래프 이론에서 회로(Cycle)이 존재하지 않는 연결된 그래프로 정의한다. 여기서 회로 또는 사이클 이란 어떤 노드에서 시작하여 그 노드로 다시 되돌아가는 경로를 말한다. 일반적으로 위와 같이 어떠한 계층(hierarchy)을 이루는 구조를 말한다. 이것을 사용하는 가장 대표적인 예시가 조직도, 컴퓨터의 파일 시스템이다. 트리의 용어 설명 트리에서 자주 접할 수 있는 용어들은 루트, 부모, 자식, 레벨, 간선, 차수, 리프노드, 서브트리, 형제 노드가 있다. 루트 또는 루트 노드(root)란 트리의 시작점이 되는 노드를 말한다. 위 그림에서는 A가 루트 노드가 된다. 레벨(level)은 루트 노드부터 노드까지 연결된 간선수의 합으로 정의한다. 루트 노드 자신은 0 level이..
덱(deque)의 정의와 구현
2023. 2. 23. 15:53
DataStructure/List
덱(deque)의 정의 덱 또는 데큐(deque)는 양 방향에서 모두 데이터의 삽입과 삭제가 일어나는 자료구조이다. 양 방향에서 데이터의 삽입 삭제가 발생하기 때문에 데큐는 양방향 연결 리스트로 구현하는 것이 효율이 좋다. 덱(deque)의 연산과 구현 위에도 말했듯 덱은 양방향 연결 리스트로 구현하는 것이 효율적이다. 해당 자료구조는 이미 이전에 큐를 구현하며 같이 구현하였다. 큐에서 데이터의 삽입이 tail에서 이루어졌고 삭제가 head에서 이루어졌다. 덱을 구현하기 위해서는 tail에서의 데이터 삭제와 head에서의 데이터 삽입을 추가적으로 구현하기만 하면 된다. class Node{ int data; Node prev; Node next; Node(int data){ this.data = data..
큐(Queue)의 정의와 구현
2023. 2. 23. 15:25
DataStructure/List
큐의 정의와 구현 Queue는 여러 게임(특히 대표적으로 롤)을 하면서 접할 수 있는 선착순의 개념이 적용된 자료구조이다. 즉 먼저 온 데이터가 먼저 나가는 FIFO(First-In-First-Out)의 구조를 가지고 있다. 이전에 배웠던 Stack이 tail에서 데이터의 삽입과 삭제가 수행되었다면, Queue는 데이터의 삽입은 Tail에서 이루어지고 삭제는 head에서 이루어진다. Queue 역시 배열과 연결 리스트로 구현이 가능하다. 일반적으로 배열보다는 연결 리스트를 더 선호하며 필자도 연결리스트로 구현하려고 한다. 큐의 연산과 그 구현 Queue의 연산들은 다음과 같다. 데이터의 삽입 데이터의 삭제 데이터의 조회(head 부분만) 큐의 상태와 길이 필자는 연결 리스트로 구현하기 때문에 Node 클..
Stack의 구현
2023. 2. 20. 20:55
DataStructure/List
스택의 정의와 연산 스택은 선입후출(FILO) 또는 후입선출(LIFO)의 특징을 가지는 자료구조로 나중에 들어온 데이터가 먼저 나가는 특징이 존재하는 자료구조이다. 이를 다른 말로 하면 한 곳(Tail)에서만 삽입과 삭제 연산이 일어나는 자료구조이다. 일반적으로 들어온 인풋의 역순으로 연산이 진행되어야 하는 경우 스택을 사용할 수 있다. 스택의 연산은 일반적으로 다음과 같이 나열할 수 있다. 데이터의 추가 데이터의 제거 데이터의 조회 스택의 상태(비어있는지) 스택의 구현 방법 스택은 배열과 리스트로 구현할 수 있다. 배열과 리스트의 장 단점은 각각 다른데 배열의 초기 길이를 변경하지 못한다는 크리티컬한 단점으로 인해 일반적으로 연결 리스트를 이용하여 구현하게 된다. 이번에도 Node Pool을 이용한다...
LinkedList의 구현 - Single Linked List
2023. 2. 20. 20:11
DataStructure/List
Single Linked List의 구현 - 계속 이전까지 연결 리스트의 head 또는 tail에 노드를 삽입하는 것을 구현하였다. 이번에는 임의의 위치를 입력받아 그곳에 노드를 삽입하는 연산과 데이터를 입력받아 그 데이터와 동일한 값을 가진 노드를 찾아 삭제하는 연산을 수행할 것이다. 임의의 위치에 노드를 삽입하는 연산 연결 리스트에서 임의의 위치에 노드를 삽입하기 위해서는 먼저 그 위치가 어디인지부터 파악하는 것이 먼저 수행되어야 할 것이다. 이는 연결 리스트의 특성을 생각해 보면 리스트를 순회하며 그 위치를 찾아야 한다. 그렇다면 그 위치에 삽입하면 될 것이다. 여기서 생각을 깊게 하지 못하면 실수가 발생한다. 임의의 두 노드 사이에 노드를 추가하려면 어떤 과정이 수반되어야 하는지 생각해야 한다. ..
LinkedList의 구현 - Single Linked List
2023. 1. 30. 16:15
DataStructure/List
단방향 연결 리스트의 구현 이번에는 단방향 연결 리스트를 Java를 사용하여 구현할 것이다. 문제는 다음과 같다. 각 명령을 문제없이 수행하는 LinkedList클래스를 작성하라 LinkedList 클래스는 다음과 같은 연산을 가진다. 초기화 리스트의 처음에 데이터 삽입 리스트의 마지막에 데이터 삽입 리스트의 임의의 위치에 데이터 삽입 data와 동일한 값을 가진 데이터를 리스트에서 삭제 이때 어떠한 Java 라이브러리도 사용하면 안된다. 데이터는 int형 정수 데이터로 제공되며 메서드 전체의 호출 수는 1만번을 초과하지 않는다고 가정한다. Node의 정의 이전 연결 리스트의 정의와 구조에서 보았듯이 연결 리스트는 Node, head로 구성되며 Node는 데이터를 저장하는 곳과 자신의 다음 Node가 존..
LinkedList의 정의와 구조
2023. 1. 30. 15:19
DataStructure/List
LinkedList의 개념과 종류 LinkedList의 개념을 알아보기 전에 배열에 대해서 먼저 알아보도록 하자. 배열(Array)은 동일한 자료형을 연속적인 메모리 공간에 저장하는 자료구조이다. 연속적인 메모리 공간에 저장되기 때문에 무작위 접근(Random Access)가 가능하다. 대신 초기에 설정해놓은 크기를 조절하기가 불가능하며 데이터의 삽입 삭제 연산 속도가 느리다. 연결 리스트는 배열의 단점을 해결하기 위해 나온 개념으로 연속적인 메모리 공간에 저장하는 것이 아닌 여러 메모리 공간에 저장한다. 그렇다면 이를 어떻게 리스트처럼 연결할까가 문제가 된다. 연결 리스트는 현재 데이터의 다음 데이터가 메모리의 어느 위치에 존재하는지에 대한 데이터 next 를 가지고 있다. 따라서 데이터를 접근할 때 ..
Hash, map의 문제 유형 탐구
2022. 11. 23. 16:56
DataStructure/Hash, map, set
개념탐구 Python에서 Dictionary 자료형에 대한 것을 본 적이 있을 것이다. 해당 자료형은 [key: value]의 쌍으로 묶여있으며 일반적인 배열/리스트 접근방식으로는 접근할 수 없고 해당 key를 사용해야 접근이 가능하다. 가령 다음과 같이 과일의 이름과 그 개수가 담겨있는 Dictionary가 있다고 가정해보자 my_dic = { 'apple': 1, 'banana': 2, 'grape': 3 } 이때, 'apple'은 key라고 정의하고 옆의 숫자 1은 value라고 정의한다. my_dic에서 바나나의 개수를 알고 싶다면, 다음과 같이 접근 할 수 있다. print(my_dic['banana']) # 2 보통 이러한 자료구조를 python에서는 Dictionary라고 하나, 알고리즘에서..