그리디13 백준 [자바 java] 2138 : 전구와 스위치 https://www.acmicpc.net/problem/2138처음에는 bfs로 풀어야하나 했는데 그렇게 하니까 너무 경우의 수가 많았다.알고보니 그리디를 사용하는 문제였다.앞에서부터 천천히 조건에 부합하기 위한 선택을 해나가면 된다. 그런데 0번 전구 스위치를 누르냐 마냐를 미리 결정하지 않으면 많이 복잡해진다.따라서 나는 0번 스위치를 누르는 경우, 누르지 않는 경우를 나눠서 진행했다 풀이char[] ori = br.readLine().toCharArray();char[] com = br.readLine().toCharArray();char[] nowOri = Arrays.copyOf(ori,n);먼저 원래의 문자열과 바뀐 후의 문자열을 입력받는다.처음에는 nowOri = ori 이런식으로 카피를 .. 2025. 6. 29. 코드트리 [자바 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. 코드트리 [자바 java] 연속 부분 합의 최댓값 구하기 2 https://www.codetree.ai/missions/8/problems/max-of-partial-sum-2?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 배열 안에서 연속한 구간 중 구간 내 수들의 합의 최댓값을 구하는 문제이다. 여기서는 그리디 알고리즘을 사용하였다. 어떤 배열이 주어지고, 해당 배열속의 특정 구간의 합 중 가장 큰 값을 구하라는 문제가 있다고 가정합시다. 이 문제에서 그리디를 사용하는 방법은 왼쪽 끝부터 차례로 구간을 확장시키면서 옆으로 나아가다가 합이 .. 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 다음
