Search for a command to run...
Articles tagged with #cpp
개요 트리는 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 하위 트리가 존재하고, 그 노드에 또 하위 트리가 존재하는 자료구조 이다. 트리의 맨 위에 있는 루트 노드가 존재한다. 우리가 알아볼 트리는 이진 트리이다. 이진 트리는 자식 노드(부모로부터 아래로 이어진 노드)가 2개 이하인 구조를 말한다. 트리의 사용 사례로는 다음과 같다 계층 적 데이터 저장(파일,폴더) 효율적인 검색 속도 힙 데이터 베이스의 인덱싱 트리에 ...
개요 연결 리스트로 큐를 구현해보고, C++ 클래스로 변환해보자. 연결 리스트는 구현이 매우 쉽다. 일반 배열로 하는 것과 다르게 실제로 데이터를 입력하면 공간을 할당하고 데이터를 출력하면 데이터의 메모리 할당을 해제하면 되어 훨씬 직관적이다. 연결 리스트 큐 구현 Node struct Node { int data; Node* next; }* front = NULL, *rear = NULL; front의 위치를 연결 리스트의 맨...
개요 큐(Queue)는 자료구조의 한 형태로 스택과 다르게 FIFO(First In First Out) 형태의 자료구조이다. FIFO는 말 그대로 선입선출이라는 의미로 먼저 들어간 데이터가 먼저 나온다나는 것이다. 쉽게 생각하여 표를 받기 위해 줄을 서는 것으로 보면 된다. 표를 받기 위해 먼저 줄을 서면 먼저 표를 받는 방식이다. 너비 우선 탐색, 캐시 구현 등의 다양한 곳에 사용된다. 큐의 구조와 큐를 구성하는 메소드 들에 대해 알아보자. ...
개요 전 글에서 공부한 단순 연결 리스트의 구성과 함수를 C++의 클래스로 바꿔 작성해 보았다. 전 글과 함수의 구현 로직은 같기에 코드와 실행 결과만 첨부하고자 한다. 클래스가 되며 바뀐 점 사실 Node에 대한 것은 structure을 사용하나 class를 사용하나 별 차이가 없다. LinkedList에 대해 살펴볼 점은 first의 위치이다. 기존 structure을 사용할 때는 모든 함수에 기본적으로 인자로 first를 줘서 어떤 연결 ...
개요 연결 리스트의 기본이 되는 단순 연결 리스트에 대해 알아보자. 단순 연결 리스트는 다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 가장 마지막 원소를 찾으려면 리스트 끝까지 찾아가야 하기 때문에(O(n)), 마지막 원소를 가리키는 참조를 따로 가지는 형태의 변형도 있다. 또한, 한 번 연결이 끊기거나, 체인이 잘 못된 경우, 모든 뒤의 데이터가 유실되는 단점이 있다. Node구성 struct Node { int...
개요 추상적 자료형인 리스트를 구현한 자료구조로, 일반적인 리스트는 stack 또는 heap에 연속적인 메모리 구조에 데이터를 집어넣는 방식이다. 반면에, 연결 리스트는 리스트의 요소를 담고 있는 데이터 덩어리인 Node를 기준으로, Node를 포인터를 이용해 데이터를 이어서 구현한 리스트이다. Node에는 다음의 요소 Node를 향한 포인터를 담고 있는 것이 큰 특징이다. 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 ...