Algorithm/개념 정리

[MST 개념] 최소 비용 신장 트리

최소 비용 신장 트리 [ Munimum Spanning Tree ] 신장 트리(Spanning Tree) Spanning Tree : 그래프 내의 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프. Spanning Tree = 신장 트리 = 스패닝 트리 신장트리를 구성하는 방법은 유일하지 않다. N개의 정점을 가지는 그래프의 최소 간선의 수는 (N - 1)개 이고, 모든 정점이 (N - 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 최소 비용 신장 트리(Minimum Spanning Tree) MST(Minimum Spanning Tree)..

2020. 3. 11. 06:57
Algorithm/문제 풀이

[SWEA_1907 - JAVA] 모래성 쌓기

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PNx_KACIDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 상당히 오래걸린 문제. 처음 풀이는 8방탐색으로 완전탐색을 하는 것이었다. 7개의 testcase 중 3개를 맞은 뒤, 시간초과에 걸려 터져버렸다. 파도수가 200 이상이면 2초(1000*1000*200) 이상이 걸려 시간초과. (제출 결과 : 7개 testcase 중 3개 이후 시간초과) 기존 풀이 방식으로는 시간초과를 통과 할 수 없으므로, 큐와 bfs형식으로 재풀이. 기존풀이가 모래..

2020. 3. 3. 14:47
Algorithm/문제 풀이

[SWEA_8382 - JAVA] 방향전환

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWyNQrCahHcDFAVP SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방향을 상하 & 좌우 번갈아 가면서 해야하는 문제. 보는 순간 패턴이 있을것으로 보여 패턴을 찾아 손 쉽게 풀 수 있었던 문제. 예로 0,0 에서 1,1로 이동할 경우 오른쪽 한번 위로 한번으로 이동 가능.(대각선 이동으로 생각하면 편하다.) 풀이 과정은 2가지로 나누어진다. row의 차이와 col의 차이 중 더 작은것*2 만큼 이동( 즉, 대각선으로 이동가능한 모든 경우를 이동) 위의 ..

2020. 3. 3. 13:52
Algorithm/문제 풀이

[SWEA_1247 - JAVA] 최적 경로

풀이 이차원 배열을 만들지 않고 문제에 주어진 거리만을 구해서 풀이. 좌표를 편하게 관리하기 위한 customer 클래스. permutation의 순서는 상관없기에 visit관리는 하지 않음. 순열로 index배열을 만들어 풀이 진행. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92..

2020. 3. 1. 06:38
Algorithm/문제 풀이

[BAEKJOON_11403 - JAVA] 경로 찾기

해결 과정 인접행렬을 뽑아내는 문제로 기존의 풀었던 문제들과 비슷했지만 어렵게 생각해 오래 걸렸던 문제. 기본적인 bfs에 각 행과 열에 대한 반복문을 씌워 문제를 해결. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.uti..

2020. 2. 23. 18:57
Algorithm/문제 풀이

[BAEKJOON_2178 - JAVA] 미로 탐색

문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력..

2020. 2. 23. 17:16