dfs21 [leetcode][988] Smallest String Starting From Leaf 문제 : https://leetcode.com/problems/smallest-string-starting-from-leaf/ DFS로 완전탐색해서 풀었다. 루트를 기준으로 자식 노드로 탐색하면서 문자열을 만들어간다.현재 노드의 val를 이때까지 만든 문자열 앞에 붙인다.그리고 리프 노드가 되면 이때까지 만든 문자열을 이때까지 구한 정답 문자열과 비교해서 사전순으로 앞서있다면 정답을 갱신한다. 시간복잡도는 모든 노드를 탐색해야 하므로 O(N + 정답문자열 비교 시간 * 리프노드 개수) 이다.완전이진트리라 했을 때 정답문자열 비교 시간 * 리프노드 개수는 트리의 높이는 logN이므로 정답 문자열 비교 시간은 logN이고 리프노드 개수는 N/2이므로 N*logN/2가 된다.좀 더 상세하게 따지면 몇가지 케이.. 2019. 2. 9. [SW Expert Academy][2819] 격자판의 숫자 이어 붙이기 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE 만들 수 있는 서로 다른 일곱 자리 수를 구하는 문제이므로 set을 이용했다.수를 이어 붙여서 7자리 수를 만들어야 하므로 DFS를 이용했다.(0, 0) ~ (4, 4)를 시작 지점으로 상하좌우 dfs를 돌리면서 수를 이어붙인다.이어붙인 수가 7개가 되면 set에 만든 문자열을 넣는다.탐색을 모두 마친 후 set의 size가 정답이 된다. 소스코드 : https://gist.github.com/fpdjsns/92ce5fc97f0fb363b588979.. 2019. 1. 5. 깊이 우선 탐색(DFS: Depth First Search) 트리나 그래프를 탐색하는 방법엔 여러가지가 있습니다. 그 중 가장 보편적인 방법이 깊이 우선 탐색과 너비 우선 탐색입니다.이번에는 두 가지 탐색 방법 중 깊이 우선 탐색에 대해 알아보겠습니다. 깊이 우선 탐색에 대해 말해보자면 말 그대로 깊숙이 탐색하는 방법입니다. 예를 들어서 살펴보겠습니다. [예시 그래프]깊이 우선 탐색 알고리즘은 간단하게, 1. 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다. 2. 탐색하지 않은 이웃 노드가 없는 경우 이전 노드로 돌아간다. 3. 1번으로 돌아간다. 입니다. 이를 모든 노드가 탐색될 때까지 실행합니다. 위의 그래프를 1번 노드 부터 깊이 우선 탐색(DFS)으로 탐색해 보겠습니다. 일단 1번 노드가 시작 노드이므로 1번 노드를 탐색합니다. 그리고 1번 노드.. 2018. 10. 27. 이전 1 2 3 4 다음
