dfs9 [알고리즘] 8-1 합이 같은 부분집합 - DFS(깊이우선탐색) , 아마존 인터뷰 (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/08-01 문제 설명 : n개의 원소를 가진 자연수 집합이 주어지고, 이 집합을 두 개의 부분집합으로 나눴을 때 각 부분집합의 원소의 합이 서로 같은 경우가 존재하는지 묻는 문제 풀이 DFS(깊이우선탐색)을 진행하며 부분집합 경우의 수를 구한다. 한 부분집합의 합이 전체 집합의 합의 절반이면 두 부분집합의 합이 같다 참고 : 부분집합 구하기 문제 - DFS package inflearn.dfs_bfs; import java.io.BufferedReader; import java.io.IOExceptio.. 2021. 6. 20. [알고리즘] 7-11 경로 탐색 - 인접행렬, 인접리스트, 깊이우선탐색(DFS) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 문제 입력 설명 : 첫째 줄에는 정점의 수 n과 간선의 수 m이 주어지고 다음 줄부터는 m 줄에 걸쳐 연결 정보가 주어진다. 인접행렬과 인접리스트 두 가지 방법으로 풀이한다. 정점의 개수가 많은 경우 인접행렬을 사용하면 그만큼의 2차원 배열을 만들어야 하기 때문에, 정점의 개수가 1000개, 10000개와 같이 많을 때는 인접리스트를 사용하는 것이 좋다. 그래프 이론에서 경로는 한번 방문한 노드를 다시 방문하지 않는다. 그래서 checked 배열을 통해 노드 방문 여부를 체크한다. 풀이1 - .. 2021. 6. 17. [알고리즘] 7-6 부분집합 구하기 - DFS(깊이우선탐색) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 자연수 n이 입력되면 1~n까지의 원소를 갖는 집합의 부분집합을 출력하는 문제(단, 공집합은 제외) 풀이 {1, 2, 3} 3개의 원소로 이루어진 집합의 부분 집합의 개수를 구하는 방법은 원소 1이 있는경우, 없는 경우 -> 2가지 원소 2가 있는 경우, 없는 경우 -> 2가지 원소 3이 있는 경우, 없는 경우 -> 2가지 2 * 2 * 2 = 8 로 8개의 부분집합을 가지게 된다. (즉, n개의 원소를 가진 집합의 부분 집합의 개수는 2n) 집합의 각 원소를 트리의 노드로, 부분 집합에 포함된다 안된다를 간선으로 표현해 이진트리를 만들어보면 DFS(깊이 우선 탐색)을 진행하여 .. 2021. 6. 15. 이전 1 2 다음
