알고리즘 (2) 썸네일형 리스트형 탐색 알고리즘 DFS 깊이 우선 탐색 [코딩 테스트, 코딩 면접 준비] DFS(Depth-First Search)란? 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. '방문 처리'는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할.. 알고리즘 시간 복잡도(Complexity) 쉽게 이해하기 복잡도란? 알고리즘의 성능을 나타내는 척도입니다. 복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있습니다. 시간 복잡도 알고리즘 문제를 해결할 때 단순히 '복잡도'라고 하면 보통 시간 복잡도를 의미합니다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하며, 알고리즘을 위해 필요한 연산의 횟수 또한 의미합니다. 시간 복잡도를 표현할 떄는 빅오(Big-O) 표기법을 사용합니다. 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다. 다음 아래 빅오 표기법 표는 위쪽에 있을수록 더 빠릅니다. 빅오 표기법 명칭 설명 O(1) 상수 시간(Constant time) 문제를 해결하는데 오직 한 단계 처리 .. 이전 1 다음
