본문 바로가기

알고리즘/백준77

1197번 - 최소 스패닝 트리(Prim 알고리즘) 1197번: 최소 스패닝 트리 (acmicpc.net) 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 예제입력3 31 2 12 3 21 3 3 처음에는 트리라는 것을 생각하지 않고, 하나의 경로라는 생각을 했다.시작점이 다를때 다른 결과가 나올거라는 잘못된 생각을 하게되어 아래처럼 시간복잡도가 큰 코드가 짜여지게 되었다.더보기import jav.. 2024. 7. 8.
1916번 - 다익스트라 알고리즘(Comparable 클래스) 다익스트라 알고리즘을 사용해 가장 비용이 싼 경로를 찾는 문제였다.출발지와 목적지가 주어졌고, 각 경로의 가격이 주어졌다.처음엔 다익스트라를 이용하지 않아 시간초과가 되었고 해당 코드는 아래와 같다.더보기더보기import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class 최소비용구하기_1916번_시간초과 { static int N, M; static List[] listArray; static int[][] fees; static boolean[] visited; static int start, end; static int min = 100000000; public stati.. 2024. 7. 5.
1806번 - 부분합 골드 5티어의 부분합이라는 문제이다.제목과 문제가 같은데 K이상의 부분합을 가지는 가장 짧은 배열의 길이를 구하는 문제이다.나는 입력부터 각 배열의 요소를 그대로 저장하기보다는, 해당 배열의 요소의 합을 누적해서 저장했다.그렇게 저장한 배열의 요소중 K 이상이 되는 곳을 찾아 따로 저장해놓고,K보다 작은 값이 나올때 까지 요소에서 요소를 빼줬다.import java.util.*;public class 부분합_1806번 { static int N, K; static int min = 100000; static int[] sumList; public static void main(String[] args) { Scanner sc = new Scanner(System.in);.. 2024. 7. 4.
1700번 - 멀티탭스케줄링(나중에 사용되는 요소) 최근 푼 문제중 가장 티어가 높은 문제로 골드 2티어의 문제이다.사용할 제품과 돼지코의 수가 주어지고, 제품의 사용순서가 주어지며, 제품은 중복 사용이 된다.이 때 코드를 가장 적게 뽑는 횟수를 구하는 것이다.처음에는 재귀를 이용했다. 때문에 너무 많이 불필요한 검사를 했고, 시간 초과가 되었다.아래는 해당 코드이다.더보기더보기import java.util.Scanner;public class 멀티탭스케줄링_1700번_시간초과 { static int N, K; static int[] products; static boolean[] stuck; static int min = 100; static int[] consent; public static void main(Strin.. 2024. 7. 4.

티스토리툴바