이즈미르의 프로그래밍

이번에는 우선순위 큐(Priority Queue)에 대해서 알아보자. 우선순위 큐는 큐에서 요소들에게 우선순위가 부여되며 우선순위가 높은 요소가 먼저 출력되는 큐이다. (en.wikipedia.org/wiki/Priority_queue) 여기서 요소란 무엇을 의미할까? 요소는 일반적으로 우선순위를 결정짓는 키(key)와 그 키와 매핑이 되는 값(value)으로 구성된다. 요소의 키는 일반적으로 정수를 사용하며 키 값의 대소 관계로 요소들의 우선순위를 결정짓는다. 요소의 값은 애플리케이션에서 실제로 사용하는 데이터이며 정수, 실수, 문자열 등의 데이터 타입이 될 수 있으며 여러 가지 데이터 타입들로 구성된 복합 데이터 타입(composite data type)이 될 수 있다. (en.wikipedia.or..

정렬 알고리즘 중에 하나인 힙 소트(Heapsort)에 대해 알아보자. 힙 소트는 힙을 이용하여 정렬하는 알고리즘이다. 힙(heap)이란 무엇을 의미할까? C언어를 좀 깊게 파봤다면 메모리 영역 중에 힙 영역이란 말을 들어 봤을 것이다. 하지만 여기서 말하는 힙은 그 힙이 아니다. 여기서 말하는 힙이란 완전 이진트리(complete binary tree)를 기반으로 하는 자료구조로 최댓값 또는 최솟값을 빠르게 찾기 위해 힙 속성이라는 것을 갖고 있다. (출처 : ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)) 완전 이진트리는 en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees..

분할 정복 알고리즘(Divide and conquer algorithm) 중에 하나인 Strassen을 알아보자. 중고등학생 때 행렬의 곱셈에 대해 배웠을 것이다. 행렬 간에 곱셈을 하기 전에 곱셈이 가능한 행과 열로 행렬들이 갖춰졌는지 확인해야 하지만 우리는 정사각 행렬(Square matrix)만 다루기로 하자. 아래와 같이 각 크기가 n인 정사각 행렬 A, B가 있다고 하자. $$ A_{n,n} = \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} ..

저번 문자열 검색 알고리즘 1편에서 Naive, Rabin Karp, KMP를 알아보았었다. 2020/04/16 - [알고리즘] - 문자열 검색 알고리즘 1편 (Naive, Rabin Karp, KMP) 문자열 검색 알고리즘 1편 (String searching algorithm) 이번에 알아볼 알고리즘은 문자열 검색 알고리즘이다. 이름 그대로 본문 문자열(haystack)에서 찾고자 하는 특정 문자열(pattern)의 위치를 찾는 알고리즘이다. 문자열 검색 알고리즘으로 따로 언급할 만큼 많은.. izmirprogramming.tistory.com 이번 시간에는 Boyer Moore 알고리즘을 알아보도록 하자. 실제로 가장 많이 사용되고 있는 문자열 검색 알고리즘이 바로 Boyer Moore 알고리즘이라..

이번에 알아볼 알고리즘은 문자열 검색 알고리즘이다. 이름 그대로 본문 문자열(haystack)에서 찾고자 하는 특정 문자열(pattern)의 위치를 찾는 알고리즘이다. 문자열 검색 알고리즘으로 따로 언급할 만큼 많은 연구가 이뤄지고 있다. 종류는 대표적인 것들로 아래와 같이 4가지가 있다. Naive Rabin Karp KMP (Knuth-Morris-Pratt) Boyer Moore 1~3번 문자열 검색 알고리즘을 1편에서 설명하고 4번 문자열 검색 알고리즘을 2편에서 설명하려고 한다. 먼저 Naive부터 알아보자. 1. Naive Naive 방식은 본문 처음부터 끝까지 문자 하나하나씩 패턴과 비교하여 찾는다. 따로 설명하지 않아도 쉽게 구현할 수 있을 것이다. 코드로 표현하면 아래와 같다. std::..

이번에 알아볼 그래프 알고리즘은 최단 경로 알고리즘(Shortest path algorithms)이다. 최소 신장 트리(Minimum spanning tree)는 모든 노드를 최소한의 비용을 들여 연결한 그래프의 모습이라고 했다. 이와 다르게 그래프의 최단 경로 알고리즘은 한 노드에서 다른 노드로 이동할 때 거치는 간선들의 비용의 총합을 최소한으로 하는 경로를 구한다. 대표적으로 다익스트라(Dijkstra) 알고리즘과 플로이드(Floyd) 알고리즘이 있다. 각 알고리즘을 알아보기에 앞서 그래프와 최단 경로를 어떤 자료구조를 사용할 것인지 정의하자. 그래프를 나타낼 자료구조는 최소 신장 트리에서 소개한 것(weights 변수) 그대로 사용한다. https://izmirprogramming.tistory.c..

이번에는 그래프의 최소 신장 트리(minimum spanning tree)를 알아보자. 최소 신장 트리가 무엇일까? 먼저 그래프는 익히 알고 있을 것이다. 그래프는 노드와 간선으로 구성된다. 지하철 노선도로 비유하자면 지하철 역이 노드이고 지하철 역과 역을 잇는 선이 간선이 될 것이다. 지하철 역처럼 노드는 무엇인가를 나타내기 위해 사용하고 간선은 노드와 노드의 관계를 나타낸다. (어느 역과 어느 역이 연결되어 있는지 등) 간선은 보통 비용을 포함하고 있다. 비용의 종류는 그래프의 용도에 따라 다양하게 결정된다. 거리가 될 수도 있고 금전적인 진짜 비용이 될 수도 있다. 여기서 노드들과 노드들을 제각기 잇는 간선이 있을 때 모든 노드들을 최소의 비용을 들여 연결한 그래프 모습을 최소 신장 트리라고 한다...

이번에는 레드 블랙 트리를 정리해 보도록 하자. 사실 알고리즘보단 자료구조에 가까운 느낌이다. 그래도 C++ stl에서 사용하고 있어서 한 번쯤은 구현해볼 가치가 있다. 이름에서 알 수 있듯이 트리(tree)를 기반으로 한다. 이진트리(binary tree)에서 최악의 구조가 발생하지 않도록 여러 규칙들을 걸어 놓았다. 먼저 규칙들을 살펴보자. (출처는 위키백과 : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties) [규칙 1] Each node is either red or black. (노드는 레드 혹은 블랙 중의 하나이다.) [규칙 2] The root is black. (루트 노드는 블랙이다.) [규칙 3] All leaves (NI..

이번에 정리할 알고리즘은 정렬 알고리즘 중에서 퀵 소트(Quick sort)이다. 정렬 알고리즘은 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort) 등 여럿 있지만 그래도 쓸만한(?) 정렬 알고리즘은 퀵 소트인 것 같다. 그래서 퀵 소트 너로 정했다! 일단 구현 원리는 이렇다. 1. 배열에 정렬되지 않은 숫자들이 있다. 2. 숫자들을 정렬할 범위를 지정하는 배열의 시작 인덱스와 끝 인덱스도 있다. 3. 그 범위 안에서 적당한 피벗(pivot)을 정한다. 4. 피벗 기준으로 작은 숫자들을 왼쪽에, 큰 숫자들을 오른쪽에 이동한다. 5. 피벗 기준으로 왼쪽과 오른쪽에 있는 숫자들을 부분 배열로 취급하여 다시 1번 과정부터 시작한다. 6. 부분 배열의 요소 개수가 1개가 될 때까지 반복..