dfs (2) 썸네일형 리스트형 [인프런 코딩테스트] 이진트리(깊이 우선 탐색)로 부분집합 구하기, DFS 1. 문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 단, 공집합은 출력하지 않습니다. 1) 부분집합과 공집합 우선 문제를 풀기 전에, 부분집합에 대해서 알아보자. 부분집합은 한 집합의 일부를 나타내는 것으로, 집합 A의 모든 원소가 집합 B에 포함될 때 A를 B의 부분 집합이라고 한다. 공집합은 원소를 하나도 가지고 있지 않은 집합으로, 부분집합에 포함된다. 만일 { 1, 2, 3 }이라는 집합이 있다고 해보자. 이때 부분집합을 구하기 위해서는 각 원소들이 집합에 포함되는지 확인해야 한다. 1이 포함되는 경우와 그렇지 않은 경우, 2가 포함되는 경우와 그렇지 않은 경우, 3이 포함되는 경우와 그렇지 않은 경우. 이를 트리로 표현하면 위와 같.. [Algorithm] 깊이우선탐색 알고리즘 (DFS, Depth First Search Algorithm) 1. 깊이우선탐색(DFS, Depth First Search) 깊이 우선 탐색은 트리나 그래프를 탐색하는 방법 중 하나로, 깊이를 우선으로 하여 시작노드에서 자식노드까지 순서대로 탐색하는 알고리즘을 말한다. 부분집합, 미로 풀기, 그래프에서 연결된 구성 요소 찾기, 퍼즐 풀기 등에서 사용된다. 재귀함수와 스택으로 비교적 쉽게 구현할 수 있으며, 후에 배울 BFS에 비해 메모리를 덜 사용한다. 그러나 재귀함수와 스택 자료구조를 사용하기 때문에 스택을 적절하게 관리하지 않으면, stack overflow로 이어질 수 있다. 또한 항상 최적의 솔루션을 찾는 것은 아니다. * 트리구조 동그란 부분을 노드(node)라고 한다. * 스택 오버플로우(stack overflow) 지정한 스택 메모리 사이즈보다 더 많은.. 이전 1 다음
