전체 글

[알고리즘] MST 알고리즘 (1) - 그래프 분할 (cut property)

1. MST (Minimum Spanning Tree) 란? MST는 "최소 신장 트리"라고 한다. 우리는 알고리즘에서 Minimum이 무엇을 뜻하는 지는 잘 안다. 그렇다면 Spanning Tree 무엇일까? Spanning Tree 그래프의 모든 노드들을 연결하는 "트리" 이다. 즉 N개의 노드를 N - 1개의 링크(edge)를 통해 모두 연결한 트리이다. 완성된 Spanning Tree에는 당연히 사이클과 같은 트리에 없는 특성은 존재하지 않는다. 여기서 Minimum이 붙으면, edge들에 있는 가중치를 고려하여 최소 비용의 Spanning Tree를 선택한다는 것을 뜻한다. 만약 모든 edge들의 가중치가 같다면, Minimum을 찾을 이유는 없을 것이다. MST를 정의하자면 다음과 같다. 그래..

6월 13일

오늘 원래 쓰려던 생각이 없었는데 쓸까 말까 하다가 쓴다. 갑자기 잊고 있던 오늘 까지가 마감인 과제가 생각나서 아침부터 정신이 없었다. 저녁 8시까지 마감인데, 맥북에 미리알람을 맞춰 놓지 않았으면 놓칠 뻔 했다. 과제를 하면서 오늘 클러스터를 갈까 말까 고민했었는데 결국 점심 먹고 출발했다. 독문과 과제인데, 솔직히 너무 하기가 싫다... 클러스터에 막상 오니 더 하기 싫어져서 어제 듣다가 만 알고리즘 수업을 마저 듣었다. 최소 4시부터는 다시 과제를 시작해야 맞춰서 낼 수 있을 듯 하다. 독일의 문화 항목 16개를 조사해야하고, 또 이번 강의를 듣고 느낀 점을 2페이지로 적어야 한다ㅋㅋㅋ 진짜 인문학과에 오면 여기서 인문학을 배우는지 소설 쓰는 법을 배우는지 모르겠다. 독문과 마지막 수업 인걸 다행..

[알고리즘] LSD vs MSD in Radix sort (기수 정렬) / C++ 구현

Radix sort를 이해하려면, 먼저 Radix가 무엇인지를 알아야 한다. 이전 글의 Radix와 Key 부분까지는 알아야, Radix sort를 이해할 수 있다. 2021.06.12 - [분류 전체보기] - [알고리즘] LSD vs MSD in Radix sort (기수 정렬) / C++ 구현 Radix sort를 구현하는 방식은 몇가지가 있는데, 블로그에서는 LSD 와 MSD에 대해서 다루어 보려고 한다. Radix sort는 여러자리의 수나 문자를 다룰 수 있기 때문에, 숫자 뿐만 아니라 string의 크기 또한 비교 가능하다. LSD는 Last Significant Digit의 약자로, 가장 낮은 수부터 정렬하는 정렬방식을 말한다. 반면에, MSD 는 Most Significant Digit의 ..

[알고리즘] 계수 정렬 (key-indexed counting sort) / C++ 구현

0. 계수 정렬 소개 계수 정렬은 O(n)의 시간복잡도를 가지고 있는, 매우 빠른 정렬 방식이다. 또한 숫자가 중복되거나 말거나 상관 없이 같은 속도로 정렬이 가능하다. 하지만, 정렬하고자 하는 배열 외에 (1)문자의 개수를 셀 때 사용하는 배열, (2)새롭게 정렬해야 하는 배열, 이렇게 두개의 배열의 메모리가 더 필요하다. 즉, 매우 큰 수를 정렬하고자 할 때, 그 만큼 큰 용량의 메모리가 필요하다. 이렇게 설명하면 알기 쉽지 않다. 기초부터 한번 알아보자. 1. Key와 Radix 계수 정렬을 이해하기 위해서는 Radix라는 개념을 알아야 한다. 다음 표를 보자. Binary(2진수), Decimal(10진수), Upper/Lower case(대소문자), ascii코드 등, 익숙한 문자들이 많이 보일..

[알고리즘] DFS (Depth-First Search) / C++ 구현

1. DFS란? DFS는 Depth-First Search 의 줄임말로 “깊이 우선 탐색"이라고 부른다. DFS의 가장 큰 특징은 해당 노드가 더 이상 edge를 가지지 않을 때까지 따라 가다가, leaf Node에서 Back Track 하는 방식을 사용하여 탐색한다는 것이다. 즉, 중요한 것은 더 이상 edge가 없는 Node를 만났을 때, Back Track을 수행한다는 것이다. DFS 순회는 다음과 같다. end end end end end 리스트로 구현한 DFS에서 N이 모든 Node의 개수이고, M은 Node를 모두 탐색하기 위한 Edge의 개수 일 때, 단지 Node들과 필요한 Edge를 한번씩 방문하면 되기 때문에 시간 복잡도는 BFS와 마찬가지로 다음과 같다. O(|V| + |E|) 2. ..

[알고리즘] BFS ( Breadth-First Search) / C++ 구현

1. BFS란? BFS는 Breadth-First Search 의 줄임말로 “너비 우선 탐색"이라고 부른다. BFS의 가장 큰 특징은 layer의 순서대로 탐색한다는 것이다. 즉, 탐색을 시작하는 지점인 root node에서 가까운 순서대로 탐색을 수행한다. 예시로 든 다음 트리에서 1층 레이어에 10, 2층 레이어에 4와 9, 3층 레이어에 3과 1과 2와 7, 마지막 4층 레이어에 5와 6으로 이루어져 있는 것을 볼 수 있다. BFS는 이 레이어의 층 수 대로 한 층씩 내려오면서 탐색하는 방법을 뜻한다. 결국 위 트리의 BFS 순회는 다음과 같다. layer-1 layer-2 layer-3 layer-4 Queue를 이용한 리스트로 구현한 BFS에서 N이 모든 Node의 개수이고, M은 Node를 모..

[자료구조 ] Tree(트리) 필수 개념, 트리 순회

트리란? 트리는 Node 로 이루어진 자료구조 이다. 하지만 Node로 이루어져있다고 다 트리라고 부를 수 있을까? 아니다. 트리는 그래프와 구별되며 다음과 같은 특징을 가지고 있다. 트리는 최소 연결 트리라고 불린다. 두 Node 사이에 반드시 1가지의 경로만을 가진다. (ex, A에서 F로 가는 경로는 한가지이다.) 트리는 오직 한개의 Root Node를 가진다. 트리에는 loop, circuit, self-loop가 존재하지 않는다. (사이클이 없는 방향 그래프(DAG)) 트리의 순회는 Pre-Order, Inorder, Post-order로 이루어진다. Edge는 항상 Node의 개수 - 1 의 개수이다. 이진트리(Binary Tree)에 대해서 우리가 보통 BT 라고 부르는 Binary Tree..

[알고리즘] Run-Length Encoding (런-렝스 부호화) 쉽게 이해하기

Run-Length부호화는, 문자열의 "중복"에 따라 압축하는 비교적 간단한 알고리즘이다. 이 인코딩 방식은 사진, 아이콘 등과 같이 "연속된 값"이 많은 데이터에 효과적이고, 애니메이션 처럼 특정 배경이 반복해서 등장하는 영상에 이용하기에 효율적이다. 이러한 인코딩 방식을 사용하는 대표적 파일 형식은 PCX, BMP, ILBM 이 있다. Run-Length Encoding 이해하기. 쉽게 이야기하면 텍스트 파일의 내용이 "AAABBCDDDDDD"로 되어 있다고 하면, A3B2CD6으로 중복되는 문자를 치환하는 것이다. (A가 3개, B가 2개 ...) 하지만 우리가 사용하는 이진파일에서는 0과 1만 사용되기 때문에 갯수로만 표현할 수 있다. 변환된 값이 232이고 시작이 0이라면, 0011100이다. ..

쓰레드를 헤는 밤

클러스터에서 쓰레드를 공부하면서 밤을 새는 중이다. 곧 해야 할 프로젝트를 위해 빨리 자바 스크립트를 공부해야 하니깐, 하던 과제를 얼른 넘어가기 위해 집에 가지 않고 있다. 2시가 되어가니 좀 피곤하다. 동료 두명과 편의점 가서 커피를 사와서 마셨다. 2+1 행사를 하길래 한명이 전부 계산하는 사다리타기를 했는데 나는 얻어마시는 두명 중 한 명이 될 수 있었다ㅎㅎ 오늘 거의 반나절을 씨름한 문제는 다음과 같다. 조만간 따로 블로그에 기술을 해야할 것 같다. 쓰레드... 비동기... 지금까지 했던 동기와 많이 다르지 않을 거라고 생각했는데, 생각보다 신경써야 할 게 많다. 정말 시간이 생명이다!라는 말이 어울린다. 확실히 빨라질 것 같기는 한데... 성능충인 나에게는 재밌기는 하다. 다음에 앱 만들 때 ..