개발용사 준기 Dev Warrior Jungi
DFS 1) DFS란?시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(backtrack) 하여 다음 경로를 탐색하는 방식입니다.한 방향으로 계속 깊게 파고들며, 재귀 또는 스택(Stack)으로 구현 가능하고, 경로 탐색, 조합 탐색, 미로 문제, 백트래킹 등에 유리합니다. 2) DFS 시간복잡도와 공간복잡도시간복잡도 : O(V + E) V = 정점(노드)의 개수E = 간선의 개수공간복잡도 : O(V) 또는 O(h) V = 정점(노드)의 개수h = 그래프의 최대 깊이 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색..
복잡도 ( Complexity ) 1) 복잡도란?복잡도는 알고리즘이 문제를 해결하는 데 소요되는 리소스를 추상적으로 측정하는 방법 2) 복잡도의 종류 종류 의미측정 단위시간 복잡도실행에 걸리는 시간연산 횟수공간 복잡도사용하는 메모리 양저장 공간 3) 시간복잡도 (Time Complexity)입력 크기 n에 대해, 알고리즘이 수행하는 연산의 수를 수학적으로 표현한 것입니다.예시아래 코드는 n번 반복하므로 O(n)입니다.for (int i = 0; i 이중 반복문이라 총 n * n번 → O(n²)for (int i = 0; i 4) 공간복잡도 (Space Complexity)알고리즘이 문제를 해결하는 동안 사용하는 메모리 공간의 양예시배열 n개의 공간이 필요 → O(n)int[] arr ..
