본문 바로가기

전체 글657

깊이 우선 탐색(DFS: Depth First Search) 트리나 그래프를 탐색하는 방법엔 여러가지가 있습니다. 그 중 가장 보편적인 방법이 깊이 우선 탐색과 너비 우선 탐색입니다.이번에는 두 가지 탐색 방법 중 깊이 우선 탐색에 대해 알아보겠습니다. 깊이 우선 탐색에 대해 말해보자면 말 그대로 깊숙이 탐색하는 방법입니다. 예를 들어서 살펴보겠습니다. [예시 그래프]깊이 우선 탐색 알고리즘은 간단하게, 1. 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다. 2. 탐색하지 않은 이웃 노드가 없는 경우 이전 노드로 돌아간다. 3. 1번으로 돌아간다. 입니다. 이를 모든 노드가 탐색될 때까지 실행합니다. 위의 그래프를 1번 노드 부터 깊이 우선 탐색(DFS)으로 탐색해 보겠습니다. 일단 1번 노드가 시작 노드이므로 1번 노드를 탐색합니다. 그리고 1번 노드.. 2018. 10. 27.
[Leetcode][915] Partition Array into Disjoint Intervals 문제 : https://leetcode.com/problems/partition-array-into-disjoint-intervals/ 배열 A를 뒤에서부터 탐색하면서 [탐색중인 인덱스, 끝] 에 포함되는 배열 요소들의 최소값을 저장하는 배열을 만든다.최소값을 저장하는 배열을 만들었다면 이번에는 배열 A를 앞에서부터 탐색하면서 [시작 ~ 탐색중인 인덱스]의 요소들의 최대값을 구한다.탐색중인 인덱스를 ind라 하였을 때 만약 ind까지 구한 최대값이 [ind, 끝] 범위의 최소값보다 작다면 정답이 될 수 있는 경우이다.ex) [5, 0, 3, 8, 6] -> [5, 0] [3, 8, 6] 으로 나뉜다고 보면 ind는 1이 되고 ind까지의 최대값은 5, ind ~ 끝 범위의 최소값은 3이 되므로 정답이 될.. 2018. 10. 26.
[Leetcode][917] Reverse Only Letters 문제 : https://leetcode.com/problems/reverse-only-letters/ 문자열 S를 앞에서부터 탐색하면서 문자라면 스택에 넣고 문자가 아니라면 큐에 넣는다.모두 탐색했다면 다시 한 번 문자열 S를 탐색하면서 정답 문자열을 만든다.2번째 탐색때 문자라면 스택의 top에서 문자를 꺼내 정답 문자열 뒤에 붙인다. 문자가 아니라면 큐의 front에서 기호를 꺼내 정답 문자열 뒤에 붙인다. 시간복잡도는 O(|S|). 소스코드 : https://gist.github.com/fpdjsns/2c4c2a29c1ff9037b27b81b4033f8daf 2018. 10. 25.

티스토리툴바