Effective C++ 3rd Edition. Scott Meyers. C++ 프로그래머의 필독서라고 불리는 Effective C++을 읽고 중요한 내용을 정리한 글 입니다. Item1. C++을 언어들의 연합체로 바라보자. 🔻 C++을 바라보는 관점을 바꾸자 오늘날의 C++은 다중패러다임 프로그래밍 언어라고 불린다. 절차적 프로그래밍을 기본으로하여, 객체 지향, 함수식, 일반화 프로그래밍을 포함하며 메타프로그래밍 개념까지 지원하고 있다. 이렇게 복잡하게 여러가지의 개념이 얽혀있는 C++을 이해하기위한 가장 쉬우면서 정확한 방법은 C++을 단일 언어로 바라보는 눈을 넓혀, 상관관계가 있는 여러 언어들의 연합체로 바라보고 각각의 하위 언어에 관한 규칙을 각개격파 하는 것이다. C++의 하위언어는 네 가지..

여러개의 스레드가 공유자원을 쓰고있을 때, 해당 공유자원이 있는 임계 영역(Critical Section)에 동시에 접근하게 되면, 공유 자원에 대한 접근이 어떤 순서로 이루어졌는지에 따라 실행 결과가 같지 않고 실행할때 마다 달라지는 경쟁 상태(Race Condition)이 발생하게 된다. 따라서 해당 문제를 해결하기 위해 한 스레드가 임계 영역에 접근하면 다른 스레드들은 이 스레드가 이용하는 동안 해당 임계영역에 접근 할 수 없도록, 즉 두 개 이상의 프로세스가 동시에 임계영역에 접근하는 것을 막하야하는데, 이를 상호 배제(Mutual Exclusion)라고 한다. 상호배제는 Lock을 통해 달성할 수 있는데, 이 글에서는 Lock을 구현하는 여러가지 방법중 스핀락(SpinLock)에 대해서 알아보고..

🔻이진 트리(Binary Tree) 먼저 힙에 대해 알아보기전에 이진트리에 대해서 간단히 알아보도록 하겠다. 왜냐하면 힙이 이진 트리로 구현되는 자료구조이기 때문이다. 이진 트리란 한 노드가 최대 두개의 노드를 자식으로 가질 수 있는 트리이다. 그 중에서도, 마지막 레벨을 제외한 모든 레벨에는 노드들이 가득차있고, 마지막 레벨의 노드들도 좌측부터 순서로 들어가있는 형태의 이진 트리를 완전 이진 트리 라고한다. 이 완전이진트리는 이러한 구조적 특징때문에 노드의 개수를 알면 트리의 구조를 특정할 수 있다는 성질이 있다. 또 이러한 성질 때문에 아래와 같은 성질을 가지고 있다. 현재 노드 번호를 i라 할때, ◾ 현재 노드의 perent node의 번호 = (i - 1) / 2 ◾ 현재 노드의 left chil..

🔻트리(Tree) 트리(Tree)는 스택이나 큐와는 달리 비선형 자료구조이다. 노드들의 계층적 관계를 표현한다. 또한 트리안에 서브트리가 있고, 그 서브트리 안에또 서브트리가 있는 재귀적 자료구조이다. 넓게 살펴보면 그래프의 한 종류라고 할 수 있다. 위 그림처럼 노드들이 마치 나무 가지처럼 연결되어 있어서 트리라는 이름이 붙혀진 것 같다. 트리는 활용되는 범위가 무궁무진하다. 추후에 포스팅할 힙(Heap)도 트리를 이용한 자료구조이고, 용도에 맞게 트리에서 파생된 자료구조나 알고리즘이 많다. 기본적인 트리만 보면 굉장히 간단한 자료구조지만 깊게 파고들면 들수록 어려운 자료구조인 것 같다. 따라서 트리의 기본적인 요소들을 정리해보는 시간을 가지면 이후에 나올 자료구조나 알고리즘을 쉽게 익힐 수 있을 것이..

🔻다익스트라 알고리즘(Dijikstra's Algorithm) 다익스트라 알고리즘이란 가중치 그래프에서 한 정점으로부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라의 경우 가중치에 음수가 존재하면 안된다는 제약사항이 존재한다. 🔶다익스트라 알고리즘의 원리 다익스트라 알고리즘의 기본적인 원리는 굉장히 간단하다. 두가지 작업을 모든 정점을 모두 방문할 때까지 반복하는 것이다. 1. 방문하지 않은 정점 중 가장 cost가 작은 정점을 방문한다. 2. 해당 정점과 연결된 정정들 중에서 거리가 이전에 기록한 값보다 작다면 값을 갱신한다 이 두작업을 무한 반복하는 것인데, 글로만 보면 무슨 말인지 이해하기 힘들 수 있으니 그림을 통해 알아보자. 6개의 정점이 있고 각 정점사이의 cost가 그림과 같은 그..

🔻그래프(Graph)란? 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. 즉 정점들 사이의 관계를 나타내는 자료구조이다. G = (V,E)의 형식으로 정의하는데 여기서 V는 정점, E는 간선을 의미한다. 그래프의 대표적인 예시는 지하철 노선도를 들 수 있을 것 이다. 지하철 역과 그 사이의 노선을 표현하는 지하철 노선도는 대표적인 그래프의 예시라고 할 수 있다. 🔸그래프의 종류 무방향 그래프(Undirected graph) 간선에 방향성이 포함되어 있지 않은 그래프이다. 그림에서 A와 B를 연결하는 간선을 (A, B)라고 하면, (A,B)와 (B,A)는 서로 같은 간선이다. 정점이 n개라할때 무방향 그래프가 가질 수 있는 최대의 간선 개수는 n(n-1)/2개 이다. 방향 ..

이번 글에서는 선형적 자료구조 중 스택(Stack)과 큐(Queue)에 대해서 살펴보도록 하겠다. 스택과 큐의 특징에 대해 알아보고, 직접 구현까지 해보도록 하겠다. 🔻스택(Stack) 스택(Stack)은 LIFO(Last-In-First-Out, 후입선출)의 특징을 가진 자료구조이다. LIFO란, 가장 먼저들어온 것이 가장 늦게나가는 방식이다. 위와 같이, 1,2,3순서대로 들어갔지만, 나올때는 3,2,1순서로 나오는 것을 LIFO방식이라고하고, 스택은 이러한 LIFO방식을 사용하는 자료구조이다. 즉, 스택에 가장 나중에 들어온 자료가 가장 먼저 삭제된다. 그러면 이러한 자료구조는 어디에 활용될 수 있을까? 우리가 에디터를 사용하여 글을 쓰다보면 잘못 썻을 때, Ctrl + Z를 사용해서 다시 이전으로..

연결리스트에 대한 자세한 설명은 해당 포스트를 참고해주시기 바랍니다. [자료구조] 배열, 연결리스트 선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하 currygamedev.tistory.com STL에서 제공하는 연결리스트 자료구조인 list의 기능 중 push_back, pop_back을 구현하면서 연결리스트를 간단히 구현해보도록 하겠다. 여기서 노드를 삭제하거나, 삽입하는 기능을 추가하려면 연결리스트는 임의접근이 불가능하므로 iterator를 구현해야하는데 iterator까지 구현하면 볼륨이 너무 커질 것 같아서 생략하였다. 연결리스트는 노드를 다..

동적배열에 대한 자세한 설명은 해당 포스트를 참고해주시기 바랍니다. [자료구조] 배열, 연결리스트 선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하 currygamedev.tistory.com stl에서 제공하는 동적배열 자료구조인 vector의 기능 중 조회, 삽입/삭제, 맨뒤에 삽입, 초기화를 구현해 보았다. 🔻전체코드 template class Vector { public: Vector() { } ~Vector() { if (_data) delete[] _data; } void insert(int pos, const T& data) { if (_s..

선형 자료구조란? 선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하나의 자료가 존재하는 구조이다. 이에 반대되는 개념으로 비선형자료구조가 있는데, 비선형자료구조란 말그래도 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태라고 볼수 있다. 이에 대한 예시로는 트리, 그래프가 대표적이다. 이번 글에서는 선형자료 중, 배열과 연결 리스트에 대해서 알아보도록 하겠다. 정적 배열 (Static array) 맨 처음 선언 시, 해당 배열의 크기를 지정하고, 한번 지정된 크기는 절대 변경할 수 없다 배열에 저장된 자료들은 메모리 상에서 연속적으로 위치한다. 임의 접근(Random A..