DFS6 11/12 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 예제) 중복 순열 구하기(DFS) 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다. ▣ 입력설명 첫 번째 줄에 자연수 N(3 2022. 11. 12. 11/06 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. DFS 그래프 탐색의 일종으로 재귀함수 알고리즘의 형태를 띄고 있다. 전위 순회, 중위 순회, 후위 순회의 형태의 트리 순회가 존재한다. 주로 사용하는 것은 전위 순회이다. 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 명심하자! 구현 방법은 재귀 함수 혹은 명시적 스택을 사용하는 것이다. 인접 리스트의 경우 O(N+E)(노드, 엣지), 인접 행렬의 경우 O(n^2)의 시간 복잡도를 갖는다. 예제) 합이 같은 부분 집합(DFS) N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇.. 2022. 11. 6. 이전 1 2 다음