알고리즘 & 자료구조/개념

트라이(Trie)는 컴퓨터 과학에서 탐색 트리의 일종이다. Trie란? Trie는 문자열을 저장하고 효율적으로 탐색을 수행하기 위한 탐색 트리의 일종입니다. 검색엔진, 자연어 처리와 같은 빠른 문자열 탐색이 필요할 때 주로 쓰이는 자료구조입니다. 트라이는 문자열을 저장할 때 위 그래프처럼 문자 단위로 쪼개어 저장합니다. 위에 보이는 TRIE는 현재 CAT, CUT, CUTE, TO, B를 저장하고 있는데요, CUT과 CUTE의 경우를 보면 두 문자열이 접두사를 공유하고 있음을 알 수 있습니다. 따라서 TRIE는 접두사와 연관된 단어를 띄워주는 연관 검색어 기능에 활용할 수도 있습니다. TRIE의 시간 복잡도 만약 가장 긴 문자열의 길이가 m이라고 한다면 삽입에는 총 O(m)의 시간이 소요됩니다. 그리고 ..

세그먼트 트리는 sum, sub 연산 말고도 min, max, gcd, lcm과 같은 다양한 연산이 가능한 자료구조이다. Segment Tree 주어지는 연속된 데이터에 대한 구간 연산(Update, query)을 O(logn) 시간에 할 수 있는 자료구조이다. 다음과 같은 배열이 있다고 하자. (index는 왼쪽부터 0이다) SUM 연산을 위한 세그먼트 트리는 위 배열을 다음과 같이 표현한다. 표현 방식은 굉장히 간단한데, 각 노드의 자식 노드를 더해서 해당 노드의 값으로 표현한다. 즉 루트 노드는 전체 원소의 합이라고 볼 수 있다. 전체 원소의 합이라는 것은 전체 원소를 cover 한다는 뜻으로 생각하면 된다. 즉, root에서 leaf로 내려갈수록 cover 범위가 줄어든다고 보면 된다. 그리고 루..

https://solved.ac/profile/seaworld0125 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 난이도 및 티어 정보 제공 solved.ac 약 두 달 넘는 기간 동안 백준을 풀었고 오늘 후기를 남기려고 한다. 일단 기록을 보면 알 수 있지만 초반에 중요한 코딩 테스트가 예정되어 있어서 뜻하지 않게 시작되었던 1일 1 백준 도전이었다. 초반에 미친 듯이 알고리즘을 풀었고 하루에 5문제는 기본으로 풀었던 것 같다. 그때쯤 블로그에 알고리즘 개념도 많이 정리해서 포스팅했었다. 그 이후에는 다른 중요한 일정들이 있어서 병행하다 보니 하루에 많은 문제를 풀지는 못했다. 그리고 두 달이 지난 지금 돌아보면 알고리즘 공부는 미친 듯이 하는 게 실력 ..

펜윅 트리는 값이 변경되어도 구간의 합을 빠르게 구할 수 있는 자료구조이다. 기존의 구간 합을 구하는 방법은 값의 변경이 있을 때 매번 O(n)의 시간이 걸리지만 펜윅 트리는 O(logn)의 시간이 걸린다. 어떻게 가능한 걸까? 우선 펜윅 트리의 구조를 먼저 그려보고 살펴보자. 펜윅 트리의 특징은 다음과 같다. 펜윅 트리는 화살표가 가리키는 곳에 각 구간의 합이 저장된다. 조금 헷갈릴 수 있는 부분이 BIT 배열의 인덱스는 0이 아닌 1부터 시작한다. 즉 BIT[1] 에는 원래 배열 arr[0]이 저장된다. BIT[4] 에는 원래 배열 arr[0]~arr[3]의 구간 합이 저장된다. BIT 자료구조를 사용하는 가장 큰 이유는 값의 업데이트와 구간 합을 구하기 위함일 것이다. 값을 어떻게 업데이트하고 합을..

특정 정점을 제거했을 때 트리의 수가 증가한다면, 해당 정점을 단절점이라고 표현한다. 단절점을 구하기 전에 먼저 해야 할 일이 있다. 위와 같은 트리가 주어졌다고 했을 때 우리는 DFS를 수행하면서 방문 순서를 기록해야 한다. 방문 순서를 확인하면 단절점의 특징을 찾을 수 있다. 1번 노드는 루트 노드이고 자식 노드가 두 개 이상이다. 또한 1번 노드는 단절점이다. 2번 노드의 자식 노드들(3, 4)은 2번 노드를 거치지 않고 1번 노드로 갈 수 없다. 또한 2번 노드는 단절점이다. 5번 노드의 자식 노드들(6, 7)은 5번 노드를 거치지 않고 1번 노드로 갈 수 없다. 또한 5번 노드는 단절점이다. 정리해보면 루트 노드는 자식 노드가 둘 이상이면 무조건 단절점이다. 특정 노드의 자식 노드들이 해당 노드..

힙 정렬을 공부하기 전에 힙(Heap)이 무엇인지 알아야 한다. 그리고 힙을 알기 전에는 이진트리(Binary Tree)에 대해서 알고 있을 필요가 있다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드이다. 이진트리로 완전 이진트리를 구성할 수 있는데 별 다른 것은 아니고 이진트리의 노드가 중간에 비어있지 않고 빽빽이 가득 찬 구조를 완전 이진트리라고 한다. 즉 아래도 완전 이진트리라고 할 수 있다. 이제 힙을 알아보자. 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있고 최소 힙은 그 반대이다. 그런데 힙 구조 안에서 특정 노드 때문에 최대 힙 구조가 붕괴..