본문 바로가기

재귀3

[DFS] 재귀와 스택으로 가볍게 문제 풀기 들어가며저번 포스팅에서는 이전 상태를 기억해야하는 문제가 대표적인 스택 활용법이라고 소개했습니다.(이전 포스팅) 스택과 재귀는 이러한 점에서 비슷한 점이 많습니다. 깊게 파고들어갔다가 다시 나오는 형태는 동일하죠. 오늘은 이러한 유형의 문제를 접했을 때, 재귀를 선택해야 하는지 스택을 선택해야하는지 알아봅시다.기준스택 기반 DSF재귀 DFS코드 복잡도스택 선언, 쌍(pair) 관리, 반복문 사용함수 호출로 구조 단순가독성흐름을 따라가기 어려움논리적으로 단계적이며 자연스러움성능비슷함 (N이 작음, 최대 8자리)거의 차이 없음정렬후처리 필요 (벡터 + 정렬)탐색 순서 조절 가능 (for문 오름차순으로)저도 디버깅의 난해함과 직관적이지 않은 코드 흐름 때문에 재귀를 외면하곤 했습니다. 하지만 대부분의 DFS .. 2025. 5. 16.

[그래프 탐색] 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색(Depth-First Search, DFS)깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 가능한 깊이까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아오는 방식(백트래킹)으로 동작합니다.🔹 DFS 개념DFS는 스택(재귀 호출 or 명시적 스택)을 사용하여 그래프를 깊게 탐색하는 방법입니다.먼저 현재 노드를 방문하고,방문하지 않은 인접 노드가 있으면 해당 노드로 이동하여 탐색을 계속함.더 이상 방문할 노드가 없으면 이전 노드(부모 노드)로 돌아감(백트래킹).🔹 DFS 동작 방식DFS의 기본 동작 순서는 다음과 같습니다.시작 노드를 방문하고 방문 처리현재 노드에서 갈 수 있는 노드를 확인방문하지 않은 노드가 있으면 해당 노드로 이동방문한 노드라면 스킵더 .. 2025. 2. 12.

하노이의 탑 이해하기 겉으로 보기에는 하노이의 탑에서 재귀의 조건인 부분 분할의 경우가 없어보이지만, 자세히 들여다 보면 반드시 존재한다. 하노이의 탑은 기둥 3개는 고정이기 때문에 시작점(From), 옮길 지점(To), 나머지 지점(Mid)로 구성된다. 원반 3개 예를 들어보자.(원반을 1에서 3으로 옮기는 과정, N: 3, From: 1, Mid: 2, To: 3) 첫번째 빨간 영역은 원반 2개를 (1)에서 (2)로 옮기는 과정이다.(N: 2, From: 1, Mid: 3, To: 2) 이 후, 1->3은 가장 큰 원반을 목적(To)지점으로 옮기는 과정이다. 두번째 빨간 영역은 원반 2개를 (2)에서 (3)로 옮기는 과정이다.(N: 2, From: 2, Mid: 1, To: 3) 정리하면, hanoi(3)의 결과는 han.. 2022. 2. 18.

이전 1 다음

티스토리툴바