알고리즘 문제풀이153 [알고리즘] 8-2 바둑이 승차 - DFS(깊이우선탐색) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/08-02 문제 설명 : N마리의 바둑이와 각 바둑이의 무게 W, 트럭에 태울 수 있는 최대 무게 C가 주어졌을 때 트럭에 바둑이들을 태울 수 있는 가장 무거운 무게를 구하는 문제 풀이 DFS(깊이우선탐색)으로 바둑이를 트럭에 태우는 모든 경우의 수를 구하며 바둑이들의 무게 합이 c보다 작지만 가장 큰 값을 구한다. package inflearn.dfs_bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.Input.. 2021. 6. 20. [알고리즘] 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-9 Tree 말단 노드까지의 가장 짧은 경로 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이를 정리하고 있습니다. 문제 설명 : 주어진 이진트리의 루트 노드1에서 말단 노드까지의 길이 중 가장 짧은 길이(간선의 개수가 적은)를 구하는 문제 풀이 넓이우선탐색(BFS)을 진행하다가 자식이 없는 말단 노드를 만나면 해당 노드의 레벨을 반환한다. package inflearn.recursive_tree_graph; import java.util.LinkedList; import java.util.Queue; //Tree 말단 노드까지의 가장 짧은 경로 public class Main7_9 { public static int bfs(Node root) { Queue q = new LinkedList(); q.offer(r.. 2021. 6. 17. [알고리즘] 7-8 송아지 찾기 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 수직선상 좌표에서 현수의 위치에서 송아지의 위치까지 갈 수 있는 최소한의 점프 횟수를 구하는 문제(한 번의 점프로 앞으로 1 or 뒤로 1 or 앞으로 5 이동 가능) 문제 링크 : https://cote.inflearn.com/contest/10/problem/07-08 풀이 최단 경로를 구하는 문제이기 때문에 BFS(넓이우선탐색)을 사용한다. 풀이 과정을 트리 그림으로 나타내면 다음과 같다. 노드의 숫자는 좌표 위치를 뜻하고 간선 위의 숫자는 한번의 점프로 이동하는 거리를 나타낸다(불필요한 중복 좌표는 생략). 즉, 트리의 레벨이 점프 횟수를 나타내고 최초로 송아지의 위치가 발.. 2021. 6. 16. [알고리즘] 7-7 이진트리 순회 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 이진트리를 넓이우선탐색(BFS)하는 문제 넓이우선탐색(BFS)란 시작 정점으로부터 가까운 정점을 우선적으로 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법으로 다음과 같은 순서로 탐색이 진행된다. 시작 정점으로부터 가까운 정점을 우선적으로 방문한다는 것은 시작 정점과 연결된 간선의 수가 적다는 것을 의미하기 때문에, 트리의 낮은 레벨부터 마지막 레벨까지 순차적으로 정점을 방문하며 탐색을 진행하게 된다. 코드 깊이 우선 탐색과 달리 재귀적으로 구현하지 않음 Queue 자료구조를 이용해서 구현한다. 어떤 정점을 방문했을 때, 자신을 출력하고, 자식이 있다면 큐에 넣는다. .. 2021. 6. 15. 이전 1 ··· 14 15 16 17 18 19 20 ··· 26 다음
