본문 바로가기

PS

 (215)
[백준 #1197] 최소 스패닝 트리 - JAVA(자바) 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.해설최소 스패닝 트리를 구하는 연습 문제이다. 최소 스패닝 트리란 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중 가중치의 합이 최소인 트리를 말한다. 즉, 사이클이 존재하면 안되며 결과의 간선(e)의 개수가 v(정점)-1이 돼야 한다. 크루스칼 알고리즘, 프림 알고리즘을 이용해서 풀 수 있는데 어떤 알고리즘을 사용해도 상관없다. 나는 크루스칼 알고리즘을 사용했다. 크루스칼 알고리즘의 순서는 다음과 같다.간선(a-b) 를 가중치를 기준으로 오름차순 정렬가중치가 가장 작은 것부터 봐서 그 간선의..
[프로그래머스 2021 카카오 채용연계형 인턴십] 표 편집 - JAVA(자바) 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr해설문제 조건을 보면 행의 개수 n의 범위가 5 ≤ n ≤ 1,000,000 이고 명령어들이 담긴 배열 cmd의 범위는 1 ≤ cmd ≤ 200,000 이 된다. 모든 행에 대해서 삽입, 삭제를 배열에서 하면 O(n*cmd) 이 돼서 시간 초과가 된다. 그래서 처음 생각은 삽입, 삭제에 유리한 LinkedList를 고려했지만 삽입,삭제가 O(1) 이지 그 노드까지 가려면 O(n)이 걸린다. (..
[백준 #3067] 보석 도둑 - JAVA(자바) 문제세계적인 도둑 상덕이는 보석점을 털기로 결심했다.상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.해설그리디 문제이다. 보석의 최대 가격을 훔쳐야 하니 보석의 가격을 기준으로 내림차순으로 정렬해서 가장 비싼 보석을 가방에 넣을 수 있는지 확인한다.이때 가방은 그 보석이 들어갈 수 있는 가장 작은 가방을 선택하면 된다. 따라서 코드에서는 TreeMap 자료구조를 이용해서 celilngKey() 함수를 사용했다. 이 함수는 key 값보다 큰 값 중 가장 작은 값..
[백준 #3067] Coins - JAVA(자바) 문제우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.해설Dynamic Programming의knapsack 문제이다. dp 문제는 보통 1) dp 배열 정의, 2) 초기화, 3) 점화식 세 단계를 갖는다.  1) dp 배열 정의:dp[n][m]: n번째 동전까지 모두 사용했을 때 금액 m을 만들 수 있는 방법의 수 2) 초기화dp[n][0] = 1보통 dp 문제는  1) dp..
[백준 #2623] 음악프로그램 - JAVA(자바) 문제인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.1 4 36 2 5 42 3첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는..
[백준 #12865] 평범한 배낭 - JAVA(자바) 문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.풀이Dynamic Programming 의 knapsack 알고리즘 이라고 한다.DP 에서는 크게 DP 배열 정의, DP 초..
[백준 #1654] 랜선 자르기 - JAVA(자바) 문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가..
[프로그래머스] 순위 검색 - JAVA(자바) 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr코드import java.util.*;class Solution { HashMap> map = new HashMap(); // info 배열의 크기(m) list : map.values()){ list.sort((o1,o2) -> o1 - o2); } // 3. 각 query에 맞는 지원자들을 찾고 이분탐색으로 target 이상의 점수를 받은 지원자 수를 구한다: O(n*logm) int[] answer = new int[q..

티스토리툴바