알고리즘, 자료구조15 Trie 자료구조 [Python / 파이썬] 1. Trie 자료구조란? ※ 입력되는 문자열을 Tree 형식으로 만들어 진행되어 보다 빠르게 문자열 검색이 가능한 자료구조이다. 보통 list에서 문자열이 존재하는지 확인하기 위해서는 O(n) (n은 list의 길이)이라는 시간이 걸리는데 Trie 알고리즘을 사용하면 O(m) (m은 문자열의 길이) 이라는 짧은 시간이 소요되기 때문에 엄청 효율적이라고 할 수 있다. 2. 어떤 경우에 적합한가? ※문자열을 검색하는 문제에서 입력되는 문자열이 많을 경우 자주 사용된다. 빠른 시간복잡도 덕분에 검색엔진 사이트에서 제공하는 자동 완성 및 검색어 추천 기능에서 Trie 자료구조를 사용한다. 3. Trie 자료구조의 형태 1. Trie 알고리즘은 노드를 이용한 Tree 형태로 이루어져 있다. 2. 문자열의 끝을 .. 2022. 1. 3. 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 깊이 우선 탐색 DFS(Depth First Search)와 너비 우선 탐색 BFS(Breadth First Search)은 그래프를 탐색할 때 사용되는 알고리즘이다. 📌그래프란, vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, dege는 정점과 정점을 연결하는 간선이다. 1. 깊이 우선 탐색(DFS) 시작 정점으로부터 최대한 깊이 탐색한 뒤, 더이상 탐색 할 곳이 없을 경우 옆으로 이동 💡깊이 우선 탐색은 루트 노드(혹은 다른 임의의노드)에서 시작해 다음 분기(branch)로 넘어 가기 전에 해당 분기를 완변하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 .. 2021. 11. 12. 그리디 알고리즘(Greedy Algorithm) 1. 그리디 알고리즘이란? 그리디 알고리즘 : "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. 예를 들어 위 그림에서 0부터 시작해 아래로 내려가며 요소의 수를 더해 가장 큰 결과를 만들어야 하는 문제가 있다고 할 때 그리디 알고리즘은 순간마다 최적의 해답을 찾기 때문에 처음 시작인 0에서 1보다 9가 큰수이기 때문에 9를 선택한다. 이후 9인 지점에서 12와 16중에 큰수인 16을 선택하여 최종 결과는 9+16으로 25가 된다. 하지만 실제 가장 큰 수를 만들수 있는 경로는 1을 거쳐 99로 가는 것이다. 이처럼 문제해결에서 그리디 알고리즘으로 해결 할 수 없는 문제에 그리디 알고리즘을 적용한 경우에는 최적해를 보장해주지 못한.. 2021. 11. 3. 이전 1 2 3 4 다음
