Greedy

Algorithm/Programmers
[Java] 프로그래머스 (최고의 집합) Level 3
Problem : https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족 programmers.co.kr Approach 약간 Greedy한 성격의 문제였다. 일단, 합이 s인 n개의 숫자 곱이 크려면 n개의 숫자가 s / n 과 가까운 숫자여야 한다. s 를 n으로 나눈 나머지를 rest, 몫을 value 라고 할 때, 곱했을 때 최대가 되려면 rest개 만큼 value + 1인 숫자가 존재하고, 나머지 개수를 value가..
→2021.02.23
Algorithm/Baekjoon Online Judge
[java] 백준 11047 (동전 0) Silver 1
Problem : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net Approach 주어지는 동전의 가치가 항상 배수관계이므로, 동전의 개수가 최소가 되게끔 동전을 사용하려면 동전의 가치가 큰 것부터 동전을 구성해나가면 된다. 예를들어, 500원 2개보단 1000원 1개 사용하는게 개수가 더 적다.(주어지는 동전의 가치들이 항상 배수관계이므로 가능함) 다른 테크닉은 필요하지 않는 간..
→2021.01.08
Algorithm/Programmers
[java] 프로그래머스 (구명보트) Level 2
Problem : https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr Approach N kg의 하중을 견디는 보트를 최소로 사용하여 모든 사람을 구출하는 문제이다. 일단 사람들의 몸무게를 오름차순으로 정렬한다. 그리고 밑의 단계를 반복한다. 구출하지 못한 사람들 중, 몸무게가 가장 큰 사람과 작은 사람의 합이 보트의 하중 기준치를 넘긴다면, 가장 큰 사람만 태운다. 구출하지 못한 사람..
→2021.01.06
Algorithm/Programmers
[java] 프로그래머스 (위장) Level 2
Problem : https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr Approach 조합의 수학적 규칙을 알고 있다면 쉽게 풀 수 있는 문제이다. N개의 옷이 있을 때, 옷을 고를 수 있는 경우의 수(입지 않는 경우도 포함)는 N+1가지다. 그래서 M종류의 옷이 각각 N1, N2, ... , Nm개씩 있을 때, 옷을 고를 수 있는 경우의 수(입지 않는 경우도 포함)는 (N1 + 1) * (N2 + 1) * ... * (Nm + 1) - 1(옷을 하나도 안입는 경우) 이다. 위 규칙만 안다면 각각 옷의 개수가 몇개인지만 판별하면 된다. 필자는 HashMap을 사용하여 옷의 개수를 카운팅하기가 편했다..
→2021.01.04
Algorithm/Programmers
[java] 프로그래머스 (큰 수 만들기) Level 2
Problem : https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr Approach (Wrong) 처음엔 주어진 문자열로 만들 수 있는 모든 수를 만들어 가장 큰 값을 저장해서 풀면 된다고 생각했다. 그러나 주어진 문자열의 길이가 최대 1,000,000자리 이하인 숫자이므로 당연하게 TLE, RTE를 받았다. Approach (Correct) 주어진 문자열에서 K개를 지워 가장 큰 수를 만들려면 앞자리 수가 클수록 좋다. 그렇다면 앞자리가 커질 수 있게, 앞의 수가 뒤의 수보다 작으면 삭제하면 된다. ​ -> 언제까지? K개까지만 (K개만 지울 수 있으니까) 작지 않다면 그 뒤에 붙인다...
→2021.01.01

• 이전
• 1
• 2
• 다음