공부 기록장

이 문제는 SWEA의 D4 레벨, [Professional] 구간 합 이라는 문제이다. 이 문제도 수업에서 다뤘던 내용인데, 선생님께서 식 안 알려주셨으면 무조건 틀렸을거다. 실제로 내 마음대로 풀었다가 시간초과 나서 실패했다. import java.util.Scanner; public class 구간합 { static long start, end; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tc=1; tc

이 문제는 SW 아카데미 D4 레벨 문제이다. 싸피 수업을 들으며 CT시간에 접한 문제인데, 간단해 보였는데 생각보다 어려웠다. 처음에는 BFS를 이용해서 접근했는데, 이렇게 풀면 바로 시간초과가 난다고 해서 다른 방법을 고민하던 중 선생님께서 다른 방법을 알려주셨다. 사실 이렇게 간단한 걸 보고 좀.. 당황했다. 풀이를 해 보자면, sC와 sR 은 각각 시작 좌표, fC와 fR은 도착 좌표이다. x와 y는 도착점에서 시작점을 빼 준 값을 절댓값으로 처리해 준 것인데, (0,0) 부터 (x,y)까지 가는 것으로 계산하기 위해서이다. 여기서 t는 x좌표와 y좌표에서 가장 가까운 y=x 상의 좌표를 의미한다. 이 점을 구하는 이유는, (t,t)에서는 가로로 먼저 출발하든, 세로로 먼저 출발하든 값이 같기 때..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제는 문제가 길어서 링크로 첨부했다. SWEA D4 레벨이고, 크루스칼을 이용한 풀이와 프림을 이용한 풀이를 하나씩 포스팅 해보려고 한다. 일단 첫 번째 풀이는 크루스칼을 이용한 풀이이다. 크루스칼과 프림 알고리즘에 대한 설명은 이전에 포스팅 해 둔 적이 있는데, 간략하게 설명하자면 크루스칼은 루트 노드를 찾아 합쳐주는 방식이다. ArrayList를 사용해서 입력을 받아주었고, Edge라는 자..