춤추는 개발자

✅ 위상정렬이란? : 순서가 정해져있는 작업 을 차례대로 진행해야할 때, 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 사이클이 없는 방향 그래프(DAG)의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미합니다. 그렇다면 순서가 있는 작업의 예시를 통해 정확하게 이해하도록 하겠습니다. 위 그래프의 흐름을 보면 '조건'으로 해석할 수 있습니다. '튀기기'전에 반드시 '닭 손질하기'를 수행해야하고, 양념에 버무리기 전에 '후라이드'와 '양념 만들기' 작업을 수행해야 합니다. 위와 같이 여러 개의 순서가 정해져있을 때, 조건에 부합하는 일직선상의 순서를 찾아보겠습니다. 위상정렬 순서: 닭 손질하기 -> 튀기기 -> 후라이드 -> 양념 만들기 -> 양념에 버무리기 -> 무많이 -> 반..

자료구조 Trie란? 일반적으로 트리의 개념 중 하나로, Radix Tree, Prefix Tree라고도 불립니다. 문자열의 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조입니다. ✅Trie의 형태 각 Trie의 노드는 형태의 Map을 가지고 있습니다. 여기서 Key는 하나의 알파벳이 되고, Value는 Key에 해당하는 자식 노드가 됩니다. K-진 트리 구조를 통해 문자열을 저장하는 방식. 영어 사전의 방식을 그대로 차용함. 만약, game이라는 단어를 찾는다면 사전에서 g부터 a, m, e를 순서대로 찾는 방식을 트리 형태로 구현한 것. 즉, 맨 앞의 접두어(prefix)부터 시작하여 단어 전체를 찾아가는 과정. Trie는 문자열 저장을 위한 공간을 많이 쓰지만, 탐색에는 매우 효..

이번에 다루게 될 알고리즘은 KMP 알고리즘으로 대표적인 문자열 매칭 알고리즘입니다. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 문자열을 점프하는 기법입니다. 접두사는 앞에 있는 문자열, 접미사는 뒤에 있는 문자열로 abacaaba가 있을 때 다음과 같습니다. 접두사 접미사 a b a c a a b c 우리가 구해야 할 것은 위와 같은 접두사와 접미사가 일치하는 최대 길이입니다. 길이 문자열 최대 일치 길이 1 a 0 2 ab 0 3 aba 1 4 abac 0 5 abaca 1 6 abacaa 1 7 abacaab 2 8 abacaaba 3 위의 표처럼 접두사와 접미사가 일치하는 경우를 구하게 되면 KMP 알고리즘의 기반이 됩니다. 이제 위와 같은 접두사와 접미사의 최대 일치 길이를 어떻게 구하..

라빈 카프(Rabin-Karp) 알고리즘 라빈 카프(Rabin-Karp) 알고리즘은 특이한 문자열 매칭 알고리즘입니다. 일반적인 경우, 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이라는 점에서 자주 사용됩니다. 기본적으로 해시(Hash)기법을 사용하며, 해시(Hash)는 긴 데이터를 상징하는 짧은 데이터로 바꾸어주는 기법입니다. 이러한 점에서 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다는 장점이 있습니다. 사실 해시(Hash)만 해도 다양한 종류의 알고리즘이 있을 뿐만 아니라 각기 다르게 구현될 수 있습니다. 하지만 문자열 매칭은 '연속적인 문자열'이라는 특별한 상황에 기반하기 때문에 해시(Hash) 또한 연속적인 경우에 더 빠르게 구할 수 있는 알고리즘을 채택하여 적용한다면 빠르게 ..

문자열 처리 알고리즘 웹 문서, XML, 빅데이터 등 문자열 데이터는 실제로 많이 처리되는 내용 단어별로 정리하여 처리한다 하더라도, 글자 단위로 처리하는 경우가 많이 발생한다. Naive 알고리즘 가장 기본적인 알고리즘으로 두개의 문자열을 처음부터 한 글자씩 비교하는 방법입니다. T[1, n], P[1, m]이 주어졌다면, T의 길이 m인 모든 부분문자열 T[1, m], T[2, m+1], ... , T[n-m+1, n]과 P를 비교 최악의 경우 시간복잡도: O(nm) Hashing 기법 P와 길이 m인 모든 부분문자열 T[1, m], T[2, m+1], ... , T[n-m+1, n]을 직접 비교하는 대신, 두 문자열의 hash값을 구하여 이 둘을 비교 만약 hash값이 다르면? 두 문자열은 100%..

Top-down과 Bottom-up의 공통적인 특징 - 다음 상태를 구하기 위해, 이전 상태를 저장하고 재사용합니다. (Memoization) - 무엇을 어떻게 저장할지 정하는 것이 중요합니다. 만약, 2차원 배열이라고 한다면, x축과 y축, 배열에 저장되는 값 이렇게 3가지를 어떤 대상으로 정의할 것인지 파악해야 합니다. - 이를 위해 정확한 문제 해석과 반복문에서 배열의 인덱스에 어떤 값을 입력해야 하는지 정해야 합니다. 적용 순서 1. 상태 정의: DP배열의 index가 의미하는 것과 문제의 초기상태 정의 2. 점화식 구하기: 다음 상태를 나타내기 위한 표현식 3. 시간복잡도 계산 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 1..

Union-find - Disjoint Set을 표현할 때, 활용하는 알고리즘으로 트리를 이용합니다. - Disjoint Set이란 서로 중복되지 않는 부분 집합들로 이뤄진 원소들의 정보를 저장하는 자료구조로 서로 공통 원소가 없는 부분 집합들을 뜻합니다. - 해당 알고리즘은 기본적으로 3가지 연산을 이용합니다. 1. make-set(x) : '초기화' 메서드로 x를 유일한 원소로 갖는 집합(트리)를 생성합니다. 2. union(x, y) : x가 속한 집합과 y가 속한 집합을 합칩니다.(합집합) 3. find(x) : x가 속한 집합(트리)의 루트값을 반환합니다. www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m..