CS/자료구조,알고리즘 (19) 썸네일형 리스트형 DFS를 활용한 조합 조합이란 우리가 고등학교 때 배웠던 Combination을 말한다. 조합은 순서를 반영하지 않는다. 즉 1 2 3 과 2 1 3 은 같은 조합이다. 우리가 아이폰, 에어팟 조합과 에어팟, 아이폰 조합을 구분하지 않는 것과 같다. 개발을 하다보면 조합을 활용해야할 경우가 상당히 많다. 그때 dfs를 활용한 조합 코드를 유용하게 사용할 수 있다. 그러나 완전탐색을 해야하는 경우나 N이 크다면 조합은 지양하는 것이 좋은데, 우선 백트레킹 방식을 사용하는 dfs 조합은 재귀 방식을 사용하기 때문에 자연스럽게 오버헤드의 부담이 생길 수 밖에 없다. EX) 1, 2, 3, 4 중 3개를 뽑는다고 가정하자. 그렇다면 1 2 3 1 2 4 1 3 4 2 3 4 앞자리수를 고정하는게 가장 편리하다 . dfs또한 이를 따.. 0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bfs는 덱을 사용하여 구현할 수 있다. 지금까지 스택, 큐는 자주 사용했지만 덱은 다뤄본 적이 거의 없다. 먼저 덱(deque)은 큐와 비슷하지만 왼쪽과 오른쪽 모두 pop이 가능한 자료구조이다. 알고리즘은 다음과 같다. 1. 현재 덱의 현재 노드를 꺼내본다. 2. 인접노드를 살펴본다. 3. 인접노드로 넘어가는데 비용이 0이면 front에 1이면 back에 삽입한다. -> why? 왜 프론트와 백에 따로 저장을 할까? 이것은 본문 두번째 줄의 비용이 0인 간선 이동을 장려해야하기 때문이다. 2*x 는 비용.. 그래프 이론 - 깊이 우선 탐색: DFS 그래프란? 우리 일상생활에서 흔히 볼 수 있는 그래프로 도로, 네트워크, 버스 노선도 등을 들 수 있습니다. 그래프를 탐색하거나 분석할 때 그냥 일일히 방문하는 방법도 있겠지만 프로그래머들은 다른 방법이 없을까 고민했습니다. DFS - 깊이 우선 탐색 깊이 우선 탐색이란 한 노드를 선택하고 그 노드를 타고 노드의 끝까지 매우 deep 하게 파고들어갑니다. 방문한 곳에는 항상 방문표시를 합니다. 그림으로 보면 1번 노드부터 시작했습니다. 가장 인접한 노드(자식노드) 2, 5중 더 작은 번호로 가는 것으로 여기선 가정하겠습니다. 2번 노드 도착 -> DFS 그럼 2의 인접노드 3, 4 중 더 작은 번호로 갑니다. 3번 노드 도착 -> DFS 그런데 3번노드에서 보니 자식노드가 없습니다. 그렇다면 위로 돌아가.. 이전 1 2 3 다음
