알고리즘85 백준 [자바 java] 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 오랜만에 백준이다! 코드트리를 통해서 개념을 어느정도 익혔으니 실전에 적용해보는 연습을 슬슬 해보려고 한다. 이 문제는 내가 5개월 전에 시도했다가 못풀었던 문제이다. 집의 위치와 공유기의 수가 주어지고, 이를 적절하게 배치해서 공유기가 설치된 집 사이의 가장 가까운 거리가 최대가 되도록 해야한다. 이 문제는 이진탐색으로 풀었고, lowerBou.. 2023. 9. 14. 코드트리 [자바 java] 회의실 준비 구현 https://www.codetree.ai/missions/8/problems/implement-scheduling-meeting-room?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 회의가 시작하는 시간과 끝나는 시간들이 주어졌을 때, 하나의 회의실에서 열릴 수 있는 회의 수의 최댓값을 구하는 문제가 있다고 하자. 이렇게 주어졌을 때, 그리디로 풀 수 있는 세가지 방법이 있다. 1. 시작시간을 기준으로 오름차순 --> 더 늦게 시작하지만 일찍 끝나는 회의가 간과된다. 2. 회의시.. 2023. 9. 13. 코드트리 [자바 java] 숫자 합치기 https://www.codetree.ai/missions/8/problems/%08merge-numbers?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 숫자 합치기 문제는 배열이 주어졌을 때 숫자를 두개씩 합쳐서 하나의 수를 만드는 것입니다. 이 때 a라는 숫자와 b라는 숫자를 합칠 때 필요한 비용은 a+b라고 할 때 가능한 최솟값을 구해야 한다고 합시다. 배열이 1, 3, 8, 10 일때는 오름차순으로 정렬하고 앞에서부터 차례로 더해나가면 되지만, 50,50,50,50,일 때에.. 2023. 9. 13. 코드트리 [자바 java] 쪼개어 배낭 채우기 구현 https://www.codetree.ai/missions/8/problems/implement-fractional-knapsack?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 보석의 수와 배낭의 크기가 주어지고, 이 배낭에 담을 수 있는 보석들의 가치의 최댓값을 구하는 문제입니다. 저는 그리디알고리즘을 사용하였습니다. 보석을 쪼갤 수 있으므로, 보석별로 부피당 가치를 구하고, 이를 오름차순으로 정렬해서 최대한 가치가 높은 것으로만 가방을 채웠습니다. 처음에는 TreeM.. 2023. 9. 12. [알고리즘 개념] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘은 문제에서 요구하는 값을 빠르게 구하기 위해 현재 상황에서 최선의 방법부터 탐색하는 알고리즘입니다. 예를 들어, 1,10,50,100원의 동전으로 4567원을 만들기 위한 최소한의 동전 수를 구하는 문제가 있다고 합시다. 이 때 1원으로 4567원을 만드는 방법 먼저 구하는 것 보다는 100원으로 채울 수 있는한 가득 채우고, 그 다음 50원, 10원, 1원을 차례로 메꾸면 훨씬 빠르게 답을 구할 수 있겠죠? 그리디 알고리즘은 최적의 답을 구하기 힘든 복잡한 문제에 대해 실제 답에 근사한 결과를 빠르고 간결하게 구하고 싶을 때 자주 사용됩니다. 어떤 배열이 주어지고, 해당 배열속의 특정 구간의 합 중 가장 큰 값을 구하라는 문제가 있다고 가정합시다. 이 문제에서 그리디를 사용하는 방법은 .. 2023. 9. 11. 코드트리 [자바 java] G & H 반전시키기 https://www.codetree.ai/missions/8/problems/reversing-g-and-h?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 그리디 중 상태반전이 가능한 문제에 해당한다. 위와 같이, 문자열이 주어지고, 구간 단위로 뒤집을 수 있을 때(0은 1로, 1은 0으로) 최소한의 횟수로 뒤집어서 원하는 문자열을 만드는 문제가 있다고 하자. 첫번째 방식과 같이 전체를 뒤집은 후, 특정 구간을 뒤집는 것도 가능하지만, 밑에처럼 원하는 배열과 다른 구간만.. 2023. 9. 10. 이전 1 2 3 4 ··· 15 다음
