이번글은 Minimum cost Spanning Tree 줄여서 MST인 '최소 비용 신장 트리'에 대한 글입니다. 먼저 MST가 무엇인지 알아보기 전에 '경로(Path)'가 무엇인지 알아보도록 하겠습니다. 경로(path) ''경로(path)'란? 특정 그래프에서 정점과 정점을 잇는 간선을 순서대로 나열한 것을 의미합니다. 그리고 동일한 간선(edge)를 중복하여 포함하지 않는 경로를 '단순 경로(simple path)'라고합니다. 이런 그래프가 있을 때 정점 A에서 C까지 이르는 경로는 A-B-C. A-D-C, A-B-D-C, A-D-B-C 정도가 있겠군요. 단순경로가 아닌 경우에는 이를테면 A-D-B-A-B-C 같은 경우가 있습니다. 최소 비용 신장 트리 A-B-D-A의 경우에는 단순경로입니다. 위에..

이번글은 저희같은? 사용자가 C++코드를 작성할 때 왜 헤더파일과 cpp파일로 나누어서 코드를 작성하는 지에 대한 글입니다. 저또한 그냥 아무런 이해없이 남들이 다 그렇게 쓰니까 아무생각없이 썻었는데 inline이나 템플릿을 공부하면서 부터 꼬이기 시작해서 다시 C++의 Build Process부터 공부한뒤 이해한 내용을 정리하였습니다. Build Process C++의 빌드 프로세스는 크게 아래 세가지 단계로 순자적으로 진행이 됩니다. - PreProcess - Compile - Link 우분투 환경에서 main.cpp, hello.cpp만들고 아래와 같이 코드를 작성해주도록 하겠습니다. 요로코롬 나누어서 컴파일 한뒤 실행하면 당연히 컴파일 자체가 안됩니다. 너무나도 당연하게 main.cpp에서 Hel..

이번글은 주기억 장치인 메모리에 프로세스를 연속적으로 공간을 할당하는 방식인 "연속 메모리 할당"을 할경우 고려해야할 사항중 "스와핑"이라는 부분에 대해서 알아보도록 하겠습니다. 스와핑이란? 메모리에 적재된 프로세스들 중에서는 현재 실행중인 프로세스가 있을 수 있고 실행되지 않는 프로세스들이 있을 수 있습니다. 실행되지 않는 것의 예로는 입출력 요구로 대기상태에 빠진 프로세스들이라던지 아니면 오랫동안 사용되지 않은 프로세스들 등등이 여기에 포함됩니다. 이러한 실행되지 않는 프로세스들을 임시로 보조기억장치 일부 영역을 "쫒아내고" 그렇게 해서 생긴 "빈 공간"에 또 다른 프로세스를 적재하여 실행하는 방식을 "스와핑"이라고 합니다. 쫒겨나는 보조기억장치의 일부 영역을 "스왑 영역(swap space)"이라고..

이번글은 BFS에 대한 글입니다! 그래프와 BFS란? 그래프란 정점과 간선으로 이루어진 자료구조입니다. 실생활에서도 많이 쓰이기 때문에 그래프는 중요한 개념입니다. 종류로는 "무방향 그래프", "완전 그래프", "가중치 그래프" 등등 종류가 많습니다. 그래서 탐색하는 방법이 그래프 구현에 따라 달라집니다. 그럼에도 불구하고 그래프의 모든 정점을 탐색하는 그래프가 대표적으로 아래 두가지가 있습니다. - DFS : Depth First Search - BFS : Breadth First Search 이중에서도 BFS를 구현하는 방법을 알려드리도록 하겠습니다. 일단 그래프를 탐색하려면 그래프가 있어야겠죠? 그래프를 구현하는 대표적인 방법두가지를 알려드리도록 하겠습니다. - 인접 리스트를 통한 그래프 구현 =>..

[06-2] 이번글은 메모리의 논리주소와 물리주소에 대한글입니다. 먼저 메모리란 무엇인지에 대해서 알아보도록 하겠습니다! 주기억 장치의 종류로 크게 RAM, ROM가 있습니다. 이중에서도 "메모리"라는 용어는 보통 RAM을 가르키는 단어입니다. 그래서 RAM(메모리)에 대해서 살펴보도록 하겠습니다!!ㅎㅎ 참고로 ROM에 대한 부분은 https://information-factory.tistory.com/270 RAM(램)과 ROM(롬) 차이점 쉽게 이해하기! RAM 이란? ROM 이란? 무엇일까? RAM은 우리가 흔하게 보는 부품입니다. 바로 삼성전자와 SK하이닉스에서 세계에서 제일 잘 만드는 부품으로 "초록색의 긴 막대기 같은 부품"입니다. RAM의 약어는 Random information-factor..

이번글은 프로세스와 스레드에 대해 알아보도록 하겠습니다. CPU와 코어 그전에! CPU를 잠깐 다시살펴보면 "명령어를 실행하는 부품"을 CPU로 설명을 많이 드렸었는데 현대의 CPU는 "명령어를 실행하는 부품"들로 이루어진 부품입니다. 이 명령어를 실행하는 부품을 "코어"라고합니다. 제 CPU의 성능은 이렇습니다. 클럭이 3.35GHz 정도이고 코어가 8개, 논리 프로세서가 16으로 잡히네요... 코어안에는 필수레지스터들(프로그램 카운터)과 ALU L!, L2 캐시 등등 많이 들어있을 텐데 이것들이 총 8개 있다는 말입니다. 그리고 논리 프로세서는 16개로 코어 하나당 하드웨어적 스레드가 2개씩 있다고 보면 되겠습니다. 보통 "스레드"라고 하면은 프로세스 상의 스레드를 떠올리시기 쉬운데 스레드는 뭐냐? ..

AVL 트리란? 이번글은 https://cjbworld.tistory.com/25 의 코드에 기반을 두고 확장하여 작성한 버젼입니다. 기존의 이진 탐색트리에서 탐색의 경우 "로그 시간복잡도를 보장해준다"라고 알고있는데 예외가 존재합니다. 바로 BST애 데이터를 삽입할 때 데이터들을 오름차순으로 삽입할 경우 트리의 모양이 요런식으로 되어 버려 탐색시 로그 시간복잡도가 안나온다는 것입니다... 선형시간 복잡도가 나오겠지용 그래서 이러한 문제점을 해결해주는 도구들이 바로 AVL 트리, 2-3-4트리, B트리, 2-3트리, Red-Black트리 등등이 있습니다. 이중에서도 AVL트리에 대해서 다뤄볼 것인데요. 이 AVL트리에는 위의 그림판 그림처럼 "균형"이 안맞는 상황을 위해 몇가지 개념이 추가가 됩니다. 바..

DX물방울책을 읽으면서 간단하게 정리한 글입니다 :) Vector란? 크기와 방향을 모두 가진 수량을 가르키는 말입니다. 벡터는 힘이나 변위, 속도를 나타내는데 쓰입니다. 벡터에서 "상등"하다는 말은 두 벡터가 있을 때 오직 길이가 같고 같은 방향을 가리킬 때만 두 벡터는 상등하다고 말할 수 있습니다. DX물방울 책 P7을 보면은 "우리가 어떤 벡터를 좌표로 규정하거나 식별할 때 그 좌표는 항상 어떤 기준계에 상대적임을 뜻하기 때문이다" 해당 문장을 이해할려고 유튜브 강의나 여러 블로그를 보았습니다. 저는 위의 문장을 (2차원 평면이라 가정) "어떤 벡터공간의 기저는 유일하지 않다"는 말로 이해를 하였습니다. 여기서 "기저"라는 말이 등장하는데 기저는 "어떤 벡터공간 V의 벡터들이 선형독립이면서 벡터공간..