1. DFS 탐색이란? DFS 탐색은 그래프의 탐색 방식 중 하나로 깊이 우선 탐색이라고도 불립니다. 이름에서 알 수 있듯이 깊이를 우선으로 탐색하는 탐색 방법입니다. 그래프는 노드에서 다음 노드로 넘어갈 때 분기가 생기곤 합니다. 깊이 우선 탐색은 다음 분기로 넘어가지 않고 해당 분기를 완전히 탐색한 후에 넘어간다는 특징이 있습니다. 2. DFS...

1. 그래프란? 그래프란 연결된 원소들의 관계를 표현한 자료구조입니다. 그래프에 원소는 정점이라 부르며, 정점을 잇는 선은 간선이라고 합니다. 2. 그래프의 종류 2-1. 무방향 그래프 무방향 그래프는 말 그대로 정점을 잇는 간선에 방향이 없는 그래프를 의미합니다. 2-2. 방향 그래프 방향 그래프는 두 정점을 잇는 간선에 방향이 존...

1. 트리란? 트리 자료구조는 노드들이 나뭇가지처럼 연결된 비선형 자료구조입니다. 맨 위에 있는 루트 노드를 기준으로 뻗어나가는 노드들이 각각의 노드를 가지고 있는 계층형 구조이기도 합니다. 컴퓨터의 폴더 구조가 트리와 매우 유사하다는 점이 있습니다. 2. 트리 자료구조에서 사용되는 용어 2-1. 노드 노드는 트리를 구성하고 있는 기본적인 ...

1. 큐란? 큐는 선형 자료구조로 먼저 들어온 데이터가 먼저 처리된다는 특징이 있습니다. 큐는 일상 생활에 비교한다면 줄서기와 비슷하다고 할 수 있습니다. 2. C++에서의 큐 C++에서는 큐를 정규 라이브러리에서 지원하고 있습니다. #include <iostream> #include <queue> using name...

1. 스택이란? 스택은 데이터를 맨 아래에서 차곡차곡 쌓는 형태의 자료구조입니다. 맨 처음에 넣은 데이터는 마지막엔 맨 아래에 깔려있게 되므로 제일 먼저 들어온 데이터가 제일 늦게 나간다는 선입후출의 특징이 있습니다. 3. C++에서의 스택 C++에서는 보통 아래와 같이 스택을 사용합니다. #include <iostream> #i...

1. 연결 리스트란? 연결 리스트는 각각의 데이터가 메모리에 비 연속적으로 저장되는 자료 구조입니다. 연결 리스트 또한 순서를 가지는 선형 자료구조이므로 각각의 데이터는 다음 요소의 메모리 주소를 저장합니다. 2. 연결 리스트의 노드 연결 리스트는 각각의 데이터를 노드에 저장합니다. 노드는 데이터 영역과 포인터 영역을 가지며 포인터 영역은 다...

1. 배열의 특징 배열은 선형 자료구조로 같은 자료형의 데이터들을 메모리에 연속적으로 저장합니다. 배열안에 저장된 각각의 데이터들은 요소라고 불리며, 요소들의 순서를 가르키는 것을 인덱스라고 합니다. 배열은 인덱스로 요소에 접근해 특정 요소를 읽는 시간 복잡도가 굉장히 빠릅니다. O(1) 또한, 배열은 정적 자료구조로 요소를 추가로 더 넣는 작업...

1. 자료구조의 분류 자료구조는 크게 단순한 자료구조 와 복합적인 자료구조 가 있습니다. 1-1. 단순한 자료구조 단순한 자료구조는 기본적인 자료형으로 int, float, double 등을 의미합니다. 1-2. 복합적인 자료구조 복합적인 자료구조 또한 2가지로 분류되며, 선형 자료구조 와 비선형 자료구조 가 있습니다. 2. 선형 자료구...

1. 알고리즘의 효율성 알고리즘은 문제를 해결하였는지 뿐만이 아니라 그 문제를 해결하는 데 걸린 시간도 중요하게 생각한다. 따라서 시간 복잡도는 해당 알고리즘이 어느정도의 효율을 가졌는지를 분류하는 기준이다. 2. 시간 복잡도의 종류 시간 복잡도는 크게 3가지로 나눌 수 있다. Big-O 표기법 Big-Ω 표기법 Big-θ 표기...

1. 자료구조란? 1-1. 자료구조가 필요한 이유 자료구조는 컴퓨터가 복잡한 데이트를 빠르게 처리하기 위해 생겨났습니다. 이로 인해 프로그램의 효율성을 증가시킬 수 있습니다. 자료구조를 이용해 용도에 맞는 자료구조를 알고리즘에 사용한다면 같은 기능을 하는 프로그램일지라도, 자료구조를 사용하지 않은 프로그램보다 빠르게 실행된다는 장점이 있습니다. ...