본문 바로가기

알고리즘 문제풀이/인프런45

[알고리즘] 9-7 원더랜드 - 프림 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 프림 알고리즘(Prim Algorithm) 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 동작 과정 시작 정점을 최소 신장 트리 집합에 포함한다. 집합에 포함된 정점과 연결된 정점들 중에 최소 비용으로 연결된 정점을 선택하여 연결하여 집합을 확장한다. (단, 회로를 형성하는 이미 집합에 포함된 정점끼리 연결하는 것은 제외) 2번 과정을 최소 신장 트리가 완성될 때까지 반복한다. 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가.. 2021. 6. 30.
[알고리즘] 9-7 원더랜드 - 크루스칼 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 크루스칼 알고리즘(Kruskal Algorithm) 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 Greedy를 이용하여 가중치 그래프의 모든 정점을 최소 비용을 연결하는 방법을 찾는 것 최소 신장 트리 : 가중치 그래프에서 간선의 가중치 값의 합이 최소가 되고, 회로가 없이 모든 정점이 연결되어있는 트리를 뽑아내는 것 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가 없는 그래프 동작 과정 그래프의 간선들을 가중치.. 2021. 6. 30.
[알고리즘] 9-3 결혼식 - Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-03 풀이 친구들 5명의 (도착시간, 떠나는시간)이 다음과 같을 때, (14, 18), (12 ,15), (15, 20), (20, 30), (5, 14) 시간의 흐름을 그림으로 나타내면 다음과 같다. class Time implements Comparable{ int time; char status;//S: 도착시간, E: 떠나는 시간 public Time(int time, char status) { this.time = time; this.status = st.. 2021. 6. 26.
[알고리즘] 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.

티스토리툴바