dfs3 dfs 를 이용하여 조합 구하기 오늘은 dfs를 이용한 조합 구하기를 정리해볼꺼다. 조합은 서로다른 n 개중에 r개를 선택하는 경우의 수를 의미한다. 조합을 다른식으로 표현하면 아래처럼 표현이 되는데 알고리즘을 구현할때는 아래 방법을 알고 있어야 한다. 그리고 이를 dfs를 이용해 내려가다 보면 이런 생각이 들것이다. "중복되는 것들이 생기네?" 이렇게 중복되는 값을 또 재귀로 돌리다보면 분명 성능이 좋지 않다. 이를 위해 다이나믹 프로그래밍 즉 dp를 이용하여 효과적으로 구현할 수가 있다. 아래는 구현안 예제 코드이다. import java.util.Scanner; public class Combination { static int[][] dp ; public static void main(String[] args) { Combina.. 2021. 9. 12. dfs를 이용한 순열 구하기 하이 .. 전에 dfs 알고리즘에 대해 글을 올린적이 있다. https://devkingdom.tistory.com/263?category=956302 DFS (Depth-First Search) 알고리즘 정리 오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다. DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다. 일단 코드소스 devkingdom.tistory.com 오늘은 우리가 고등학교 시절 수학시간에 배웠던 순열, 조합 을 dfs 알고리즘을 이용해서 구현해보려고한다. 중복순열 중복순열은 서로 다른 n개 중 r 개를 순서를 고려해서 나열하는 순열을 의미한다. 기로호는 nΠr 로 나타낼 수 있다. 이를 dfs로 각 경우의 수를 p.. 2021. 9. 6. DFS (Depth-First Search) 알고리즘 정리 오늘은 알고리즘에서 가장 중요한 개념중에 하나인 DFS에 대해 설명을 드리고자 한다. DFS는 다양한 경우의 수를 구할때 굉장히 많이 쓰이는 알고리즘이나 꼭 익혀두길 권장한다. 일단 코드소스를 먼저 보여드리겠다. public class DFS { public static void main(String args[]) { DFS tree = new DFS(); Node root = new Node(1); root.lt = new Node(2); root.rt = new Node(3); root.lt.lt =new Node(4); root.lt.rt = new Node(5); root.rt.lt = new Node(6); root.rt.rt = new Node(7); tree.dfs(root); } publi.. 2021. 7. 28. 이전 1 다음
