접근법 가장 기본적인 최소 신장 트리 간선의 정보를 가중치 기준 오름차순 정렬한 뒤 사이클이 돌지 않는 선에서 선들을 이어준다. 추가 V-1만큼을 이어주면 탈출하는 조건을 넣는다면 좀 더 시간이 빨라질 것 같다. ⇒ 미묘한 성능 향상 코드 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class BOJ_1197_최소_스패닝_트리 { static int[] parent; static int ..
접근법 구현문제. 문제가 원하는 조건에 맞게 구현을 잘하면 된다. 내가 중요하게 생각했던 부분은 bfs로 구현할 때 주변에 중복되지 않으면서 0이 아닌 빙산이 주어진다면 queue에 집어넣는다. 0이 주어진다면 방금 녹은건지 아닌지를 판단해야 한다. 이 둘 모두를 visited로 처리할 수 있다. 코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class BOJ_2573_빙산 { static b..
접근법 진짜 빡구현이란 이런 것이다.. 디버깅이 헬이었던 문제 최적화가 필요할 것 같다 참고한 테스트케이스 첨부하겠음 #TC 1 input: 4 2 16 16 0 32 16 4 1 4 16 32 0 2 0 8 8 correct answer: 128 output: 64 #TC 2 input: 4 0 8 1 1 8 0 1 4 8 0 8 32 1 32 32 0 correct answer: 128 output: 64 #TC 3 input: 4 2 32 16 8 4 0 4 4 0 1 8 4 32 32 0 32 correct answer: 64 output: 128 코드 package boj; import java.io.BufferedReader; import java.io.IOException; import ja..
접근법 각 알파벳이 어떤 수를 나타내야 가장 큰 수가 나오게 되는지를 확인하는 문제 충분히 그리디 알고리즘으로도 해결이 되는 문제. 각 알파벳마다 나오는 자릿수만큼을 모조리 더하면 가장 큰 수가 될 수 있는 경우들이 보이게 된다. 합이 높은 수에 높은 수를 배치하게 되면 가장 큰 수가 나올 수 있을 것이다. 문제는 제일 처음 0은 올 수 없다는 점으로 이 부분만 잘 처리해 주면 문제 해결은 어렵지 않다. 코드 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class BOJ_1132_합 { public sta..
접근법 문제 유형이 투포인터라는 점과, 수열을 확인하며 각 수열마다 겹치는 원소를 확인하는 방법은 굉장히 비효율적이며, 시간초과가 날 것이라는 생각이 들어 다음과 같이 생각했다. 각 자리에 있는 원소들에서부터 만들 수 있는 조건에 맞는 수열은 중복되는 원소가 나오기 전까지의 수열의 갯수이다. 예로 {1, 2, 3, 4, 3, 5, 6} 을 살펴보자.{1}, {1,2}, {1,2,3}, {1,2,3,4} 가 된다. 이 것은 수열 {1,2,3,4} 의 원소의 갯수와도 같다. 처음 원소인 1에서 만들 수 있는 조건에 맞는 수열은 중복된 원소가 나오는 순간 순열의 처음부터 끝까지 움직이며 어느 위치에 해당 중복되는 원소가 있는지 확인한다. 2-1) 이 과정에서 중복된 원소가 아닌 원소에서도 조건에 맞는 수열들이..
