개발 관련/algorithm3 Trie Trie 자료 구조 1. 개요 문자열을 다루는 작업은 정수나 실수 등의 다른 자료형을 다루는 것과는 다르다. 왜냐하면 정수나 실수형 변수는 그 크기가 정해져 있어 비교에 상수 시간이 걸린다고 봐도 되지만, 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조 위와 같은 트리 형태의 구조를 가지며, 공간을 많이 차지하는 대신, 시간 복잡도는 O(M - M은 문자열 길이) 이 되어 엄청 빠르게 검색이 가능하다. 2. 사용되는 곳 일단, 어디에서 사용되는지 알고 배워야 좋지 않을까? 단어 검색 (자동완성으로도 사용이 가능한 것 같다.) 스펠 체크 아이피 라우팅 (아이피를 숫자로 바꿔서 할 줄 알았는데, 문자열 그대로 하나보다..).. 2022. 7. 14. DFS (깊이 우선 탐색) 깊이 우선 탐색 (Depth-First Search) 1. 개요 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점 그렇기 때문에 재귀호출로 구현하는 경우가 많으며, 어떤 노드를 방문했는지 여부를 검사해야 한다. 1을 방문 -> 2를 방문 -> 3을 방문 -> 4를 방문 더이상 갈 곳이 없으므로 3으로 back, 3에서 2로 back, 2에서 1로 back 1에서 인접한 노드인 5로 방문 -> 6을 방문 ..... 2. 의사 코드(pseudocode) void dfs(Node root) { if(root .. 2022. 7. 14. Brute Force Brute Force (무식하게 풀기) 1. 개요 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것 문제를 마주하고 나면 가장 먼저 무식하게 풀 수 있을까 라는 질문을 스스로에게 하자 말 그대로 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 이런 방법을 흔히 완전 탐색 이라고 부르고, 왜 굳이 언급할까 싶지만, 컴퓨터의 장점은 결국 속도가 빠르다는 것이기에 장점을 잘 활용하는 것이기도 하다. 2. 재귀 호출과 완전 탐색 2-1. 재귀 호출(함수) 재귀 호출(함수) 란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킴 // 1부터 n까지의 합을 구하는 반복문과 재귀함.. 2022. 7. 14. 이전 1 다음