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