춤추는 개발자

✅ 위상정렬이란? : 순서가 정해져있는 작업 을 차례대로 진행해야할 때, 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 사이클이 없는 방향 그래프(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..

플로이드 와샬 - '모든 정점'으로부터 다른 '모든 정점'까지 이동하는 최단 경로를 구하는 알고리즘 - 다익스트라와의 차이점은 특정한 하나의 정점이 아닌 '모든 정점'이라는 것입니다. - 해당 알고리즘은 기본적으로 '특정 노드를 거쳐가 다른 노드로 이동'이라는 특징이 있습니다. (k - i - j) - 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것! www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net public static void cal..

벨만-포드 알고리즘 - 앞서 포스팅한 다익스트라와 유사한 최단경로 알고리즘입니다. - 다익스트라와의 차이점은 가중치가 음수가 포함된 상황에서도 적용 가능하다는 특징입니다. - 정점의 개수가 N이라면 시작 노드를 제외한 (N-1)회 반복문을 수행하여 최단 경로를 구할 수 있습니다. www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net public static void checkedTimeMachine() ..

다익스트라 - '최단 경로는 여러 개의 최단경로로 이루어졌다.' - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘, 하나의 정점(Node)에서부터 다른 정점까지로 가는 최단 경로를 알 수 있습니다. (대신, 가중치가 음수인 경우 적용할 수 없습니다.) - 기본적으로 하나의 최단 경로를 구할 때, 이전까지 구한 최단 경로 정보를 그대로 활용한다는 특징이 있습니다. 다익스트라의 작동과정 1. 출발노드 선정 2. 출발노드를 기준으로 연결된 노드마다 최소 비용 저장 3. 방문하지 않은 노드 중 최소 비용의 노드 선택 4. 다른 노드로 이동할 경우, 최소 비용을 갱신하며 이동 5. 3~4번 반복 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 ..