본문 바로가기
728x90
반응형

Algorithm3

[Algorithm] DFS: Depth First Search 깊이 우선 탐색 DFS 알고리즘을 공부하다보면 반드시 한 번쯤은 들어보게 되고, 공부해야하는 알고리즘이 두가지가 있다. DFS 와 BFS이다. 오늘은 둘 중 DFS(Depth First Search) 알고리즘에 대해서 간단하게 먼저 알아보도록 하겠다. 이름에서 알 수 있듯, 먼저 깊게 쑥~ 들어가보고 옆으로 차근차근 옮겨가며 탐색을 하겠다는 뜻이다. 그림으로 표현하면 다음과 같다. 위 그림은 트리를 나타낸 그림이다. 각 층의 인덱스는 왼쪽부터 오른쪽으로 커진다고 가정하겠다. 먼저 1번 노드에서 탐색을 시작할 것이다. 1번 노드에서 출발하여 다음 자식노드인 2번과 3번 노드를 방문해야하는데, 이때 DFS는 2번 노드 방문 후 3번 노드가 아닌 4번노드, 즉 2번 노드의 자식 노드로 탐색을 이어나가는 것이다. 그 다음은 8.. 2021. 10. 18.
[Algorithm] 프로그래머스 코딩테스트 연습 - 기능개발[Python][파이썬] def solution(progresses, speeds): answer = [] while len(progresses) > 0: toDelete = 0 canDelete = True for i in range(len(progresses)): progresses[i]+=speeds[i] if progresses[i] 0: answer.append(toDelete) return answer 이중반복문을 사용하여 O(n^2)의 시간복잡도를 가진다. 2021. 9. 27.
[Algorithm] 투포인터 - 두 수의 합(Python) n개의 요소를 가진 배열이 있다. [2, 5, 3, 4, 12, 7, 9, 11] 이 배열에서 두 수의 합이 10이 되는 수들의 인덱스를 출력하라. 풀이1-이중반복문 numberArray = [2, 5, 3, 4, 12, 7, 9, 11] n = len(numberArray) target = 10 for i in range(n): for j in range(n): if numberArray[i] + numberArray[j] == target: print(i,j) 시간복잡도 = O(n²) 풀이2-투포인터 numberArray = [2, 5, 3, 4, 12, 7, 9, 11] n = len(numberArray) target = 10 startPointer, endPointer = 0, n-1 numbe.. 2021. 8. 23.
728x90
반응형

티스토리툴바