본문 바로가기

전체 글

 (51)
이진 트리 이번에 다룰 내용은 그래프의 트리 내용의 심화 내용이다. DFS, BFS는 지난 시간에 앞서 간단히 소개하였기 때문에 오늘은 이진 트리에서의 순회에 대하여 집중적으로 알아볼 시간이다. 이진트리란 정점의 자식이 최대 2개인 트리를 뜻한다. 지금까지 우리가 알아본 순회 방식에는 DFS와 BFS가 존재하지만 특별히 이름이 덧붙여진 순회들이 있다. 바로 레벨 순회와 전위/ 중위/후위 순회이다. 이진트리를 집중적으로 알기 전에 우리가 기본적으로 넘겨짚고 가야할 부분들이 있다. 좌측의 트리 그래프와 우측의 이진 트리를 코드에서 표현하는 방식이다. 기존에 사용했던 방식과 동일하게 트리를 큐나 스택에 저장하게 된다면 인접 리스트의 노드가 좌노드인지 우노드인지 판별이 어렵다. 따라서 구별할 수 있는 방식이 두가지가 존재..
트리 트리란 트리는 간선과 정점으로 이루어진 자료구조이다. 트리를 아주 간단하게 요약하자면 다음과 같다... 트리는 꼭대기부터 아래까지 계층을 이루고 있고 루트를 제외하고 나머지 정점들은 나머지 노드와 하나씩으로만 연결이 되어있는 구조를 볼 수 있다. 트리의 구조를 자세히 살펴보면 다음과 같다... 제일 최상단에 존재하는 노드의 정점은 루트라고 부른다. 또한, 간선으로 이루어지는 노드의 정점들을 부모와 자식이라고 부른다. 자식이 없는 정점은 리프( leaf)이다. 따라서, 상단의 그림의 리프는 총 4개이다. Depth는 루트와 노드 사이의 거리를 뜻하며, Depth가 1인경우에는 상단의 자료에 따르면 총 3개가 존재한다는 것을 알 수 있다. 즉, 트리를 간단 명료하게 한번 더 정리를 하면, 무방향이면서 사이클..
Blueprint 와 C++의 차이점 Bluepriont Strengths 블루프린트는 수정이 빠르다 프로그래밍 언어에서 쓰는 복잡한 용어를 외울 필요가 없기 때문에 초보자에게 좋다 프로그램 내에서 제공하는 내장 툴이 있어서 마우스 우클릭으로 원하는 기능을 찾을 수 있다. 언리얼 전용 프로그램이다. 다른 분야와 협업 툴에서 사용하기가 편하다. C++ 간이성이 좋다. 업계 표준 언어로서 쓰는 사람이 많다. 그래서 관련 툴이나 도움을 구할데도많다. 빠른 명령어 처리로 인하여 속도가 빠른 애플리케이션을 잘 만들어낼 수 있다. 모든 영역에 접근이 가능하고, 대형 프로젝트에 적합하다.
순열 next_permutation 순열(permutation)은 서로 다른 n개의 원소에서 r개를 뽑아 한줄로 세우는 경우의 수를 표현할 수 있다 C++ STL을 사용하여 순열을 쉽게 표현할 수 있다. 헤더파일 #include 기본형 bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare com); ● 인자 : 컨테이너(배열)의 시작과 끝 iterator ● true : 다음 순열이 존재하면 컨테이너의 원소들을 해당 순열로 바꾼 뒤 true 반환 ● false : 다음 순열이 존재하지 않는다면 fa..
Pair 클래스 Pair 클래스 Pair 클래스는 사용자가 지정한 2개의 타입의 데이터를 저장하는데 사용합니다. 서로 연관된 2개의 데이터를 한 쌍으로 묶어서 다룰 떄 사용하면 편리합니다. Pair 클래스 이전에는 두개의 데이터를 묶기 위해서, 구조체를 정의했어야 했다. 하지만! Pair 클래스를 이용함으로써 서로 다른 2개의 데이터를 편리하게 관리할 수 있게 되었다. Pair 클래스의 헤더 파일은 #inlcude라는 헤더파일에 존재하는 STL이다. 하지만, 굳이 #include를 이용하지 않고, #include 헤더파일을 포함하게 되면서 주로 vector 헤더파일을 선호한다. #include #inlcude #inlcude Pair 클래스 형태 template struct pair; pair p Pair 클래스의 T1..
BFS(Breadth-First-Search) BFS는 너비 우선 탐색 그래프에서 순회 방법 중 하나이다. 시작 노드에 인접한 노드를 모두 방문하고, 방문한 노드에서 인접 노드를 모두 방문 탐색하는 알고리즘이다. BFS의 동작 과정을 이해하기 위해서는 먼저 그래프 자료구조와 큐 자료구조에 대해 이해할 필요가 있다. BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색하는 점에서, 선입선출의 큐(Queue) 자료구조를 활용한다. 인접한 노드를 순차적으로 큐에 삽입하고 (FIFO) 선입선출에 의해 큐를 꺼내도록 알고리즘을 작성하면 된다. BFS의 장단점 BFS의 장점 1. 답이 되는 경로의 최단경로를 찾는다. 2. 무한으로 길어지는 경로의 해답을 찾을 수 있다. BFS의 단점 1. 경로가 길어짐에 따라 메모리 공간을 많이 차지하게 된다. 2. 해..
Vector 함수(push_back, emplace_back) push_back 함수와 emplace_bark 함수, 모두 Vector의 마지막에 새로운 원소를 추가하기 위해 사용하는 함수이다. 그렇다면, push_back 함수와 emplace_back의 차이점을 알아보자. Push_back push_back의 경우에는 Vector의 마지막에 새로운 원소를 추가하기 전에 임시 객체를 생성한다. 이때, Vector에 push할 값을 임시 객체에 값을 복사한 후, Vector에 삽입하는 과정을 거친다. 삽입이 끝나면 임시 객체 또한 파괴된다. 임시 객체를 생성함으로서, 메모리를 잠시 할당함으로서 메모리 연산 과정에서 생성자와 소멸자가 호출되어 불필요한 연산이 생긴다. 주의해야할 사항은, Push_back 하기 이전에 vector 형에 맞추어 배열의 형태에 맞는 인자의 ..
DFS(Depth First Search) 그래프 순회 방법 중 하나중 하나이다. 그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문한다 DFS는 깊이 우선 탐색 시작 노드에세 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드가 돌아가서, 다시 깊이 우선 탐색을 반복하게 된다. 다음과 같은 상황에서 노드가 존재할 때, 노드에서 깊이 우선 탐색에 의해 0번 -> 1번 -> 3번 -> 4번 -> 2번 순으로 노드를 찾아가며 탐색하는 방법이다. DFS의 장단점 DFS의 장점: 1. DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비하여 메모리 공간을 덜 사용한다. 2. DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 ..

티스토리툴바