접근법 가장 기본적인 최소 신장 트리 간선의 정보를 가중치 기준 오름차순 정렬한 뒤 사이클이 돌지 않는 선에서 선들을 이어준다. 추가 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) 이 과정에서 중복된 원소가 아닌 원소에서도 조건에 맞는 수열들이..
접근법생각보다 까다로웠던 문제. 처음 접근은 가장 긴 오름차순 배열의 길이를 구하는 문제인 줄 알았다. 이 접근법은 네 가지의 문제가 있다.내림차순도 생각해야 한다는 점 ( 위에서 내려다보는 )마냥 오름차순이나 내림차순이라고 해도 건물에 가릴 수도 있다는 점몇 건물이 가리더라도 뒷 건물이 매우 크면 또 보일 수 있다는 점하나의 건물에서 좌, 우로 볼 수 있다는 점이 네 가지를 유념하면서 문제를 바라보면 다르게 생각할 수 있다. 바로 각도다. 하나의 건물을 기준으로 바라보는 각도가 밑에서 위로 올라가면서 몇 개의 건물을 볼 수 있는지를 찾으면 되는 문제 그래서 각도가 올라가면서 각도의 최댓값을 갱신할 때, 갯수를 세어 최대 갯수를 출력한다.코드package boj; import java.io.Buffere..
1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 접근법 점화식을 잘 세우면 금방 풀 수 있는 문제 이 식을 잘 도출할 수 있다면 다음 필요한 dp를 구하는 것은 어렵지 않다. 육각수 배열을 h라 할 때, dp[n]은 h[i]값이 n을 넘지 않는 한에서, dp[n-h[i]]의 최솟값을 구하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..
1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 더보기 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은..
