알고리즘

[알고리즘] P, NP

P와 NP는 "문제"를 구분하는 기준이다. 어떤 문제가 Polynomial Time Algorithm이 존재하면 그 문제는 P인 것이고, 어떤 문제를 해결할 때 Non-Deterministic Polynomial Time Algorithm이 존재하면 그 문제는 NP인 것이다. 쉽게 말하면 어떤 문제가 다항시간 안에 결정론적 튜링머신으로 답을 찾을 수 있는지 비 결정론적 튜링머신으로 답을 찾을 수 있는지를 구분한 것이다. 결정론적 튜링머신 - 정해진 명령을 수행하는 가상의 기계비결정론적 튜링 머신 - 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우, 즉 입력 값이 주어진 문제의 해답인지를 검사하는 장치이다. **"시간"으로 구분한 것이다 아니다. P NP 모두 다항시간에서 판단이..

[알고리즘] 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를 정의하자면 다음과 같다. 그래..

[알고리즘] 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이다. ..