1. 트라이(Trie)트라이(Trie)는 어떤 문자열이 특정 문자열에 해당되는지 알아낼 때 효율적으로 사용할 수 있는 자료구조이다.트라이는 문자열 집합 내에서 중복되는 접두사들에 대응되는 노드들이 서로 연결된 트리이다.  루트는 빈 문자열로 시작하여, 리프 노드는 문자열이 된다. 만약 위와 같은 트라이에서 'ten'이라는 단어를 찾을 때, 루트 노드에서 시작하여 t를 찾는다. 그 후 자식 노드들 중 e를 찾고, 또 n을 찾는다.리프 노드까지 도달했다면, 해당 문자열이 우리가 찾던 문자열이 되고 탐색이 완료된다. 트라이는 모든 문자열을 O(log n)으로 탐색이 가능하여 문자열 탐색이 굉장히 빠르다는 장점이 있다.하지만, 알파벳은 총 26개이므로 문자열을 포함하는 각 노드는 26개의 자식 노드 포인터를 가..

1. 최소 신장 트리란? 신장 트리(Spanning Tree)란 그래프의 모든 노드가 사이클 없이 연결된 부분 그래프를 의미한다. 신장 트리는 여러 개가 존재할 수 있으며, 이 중 모든 노드가 최소 간선의 합으로 연결되었을 때를 최소 신장 트리(MST, Minimum Spanning Tree)라고 한다. 최소 신장 트리를 찾을 수 있는 대표적인 알고리즘 2가지가 있는데, 크루스칼 알고리즘과 프림 알고리즘이다. 크루스칼은 간선 중심, 프림은 정점 중심 알고리즘이다. 정점 대비 간선이 적으면(Sparsh Graph) 크루스칼을, 많으면(Dense Graph) 프림을 사용하는 것이 좋다. 크루스칼 알고리즘의 시간복잡도: O(ElogE) 프림 알고리즘의 시간복잡도: O(VlogV+ElogV) 둘 다 음의 간선이..

1. 부분 수열과 증가하는 부분 수열이란? 부분 수열 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열을 의미한다. 만약 { 3, 2, 5, 2, 3, 1, 4 } 라는 수열이 있다면 {3}, {2}, {2, 5}, {3, 5, 3, 1} 등이 해당 수열의 부분 수열이 되며, 수열 자체도 자기 자신의 부분 수열에 포함된다. 증가하는 부분 수열 증가하는 부분 수열은 부분 수열들 중에서도 그 수가 오름차순으로 증가하는 부분 수열을 의미한다. 위에 있던 수열의 증가하는 부분 수열은 {2, 5}, {2, 3, 4} 등이 있고, 원소가 하나일 때도 증가하는 부분 수열에 포함된다. 이번 포스트에서 소개할 가장 긴 증가하는 부분 수열은 그 중에서도 가장 길이가 긴 것을 의미한다. 가장..

1. 최단거리 알고리즘이란? 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 주로 그래프를 이용하여 표현하며 각 지점은 노드, 지점 간 연결선은 간선으로 표현한다. 이번 포스트에서는 대표적인 최단거리 알고리즘인 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대해 소개하겠다. 2. 다익스트라 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 음의 간선이 없을 때 정상적으로 동작하며, 매번 가장 비용이 적은 노드를 선택하기 때문에 그리디 알고리즘으로 분류된다. 음의 간선 - 0보다 작은 값을 구하는 간선 음의 간선이 포함되었을 경우에는 벨만 포드 알고리즘을 사용해야 한다. 다익스트라 알고리즘의 구현 🍥 각 노드에 대해 현재까..

1. 세그먼트 트리란? 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등 ...)을 구하는데 사용하는 자료 구조이다. 트리 종류 중 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. → O(logN) 세그먼트 트리는 이진 트리 중에서도 전 이진트리(Full Binary Tree)에 해당한다. 전 이진 트리: 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리 2. 세그먼트 트리의 구성 먼저 이진 트리를 구성할 때 루트 노드는 1부터 시작한다. (0부터 시작하면 인덱스 관리가 어렵다) 그 아래부터는 부모 노드의 인덱스를 i라고 할 때 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1이 된다. 아래는 A={ 1, 2, 3, 4, 5 }라는 ..

1️⃣ 그리디 Greedy는 '탐욕스러운, 욕심 많은'이라는 뜻으로 각 단계마다 지역적 최적해가 궁극적으로 전역 최적해가 되는 것이다. (선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달한다) 그리디 알고리즘으로 문제를 풀기 위해서는 아래 두 가지 조건을 충족해야 한다. 최적 부분 구조 - 현재 상태에서의 최적해가 전역적인 최적해로 이어져야 한다. 탐욕적 속성(앞의 선택이 이후의 선택에 영향을 주지 않음)이 증명되어야 한다 귀류, 귀납, 대우증명을 사용할 수 있으며, 귀류법을 보통 자주 사용 귀류법 - 어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을 증명하는 방법 코테에서 그리디를 풀기 위해 증명까지 해야 하는가?! 💡 무식하게 풀기 → DP → 그리디 ..