반응형 개발/알고리즘2 DFS, BFS 스터디용 DFS, BFS 정리 DFS, BFS는 그래프에 속하는 알고리즘이다. 코딩테스트에서 경로를 찾는 문제에서 많이 출제가 된다. DFS Root Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack 혹은 재귀함수(Recursion)으로 구현된다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) Java Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 .. 2021. 2. 5. 트라이(Trie)알고리즘 트라이(Trie) 트라이란 문자열 검색을 빠르게 할 수 있는 알고리즘이다. 예를 들어 영어사전이 있을 때 특정 단어가 있는 지 빠르게 찾을 수 있다. 문자열을 특정 키값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있다. 불완전한 해시 테이블의 최악의 검색속도는 모든 데이터를 다 확인하는 것으로 O(N)이지만 트라이를 사용하게 되면 문자열 길이 만큼의 O(M)의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있다. 보통 트라이 알고리즘을 사용할 때 고려해야할 점이 단어의 길이, 그리고 파생되는 노드 child개수다. 위에 영어사전으로 예를 들었는데 영어는 알파벳이 26가지로 child 노드는 26개를 갖고 있을 수 있다. 전화번호 목록같은 경우도 0부터 9가지.. 2020. 4. 7. 이전 1 다음 반응형
