개발자꿀꿀이

문제 https://www.hackerrank.com/challenges/organizing-containers-of-balls/problem Organizing Containers of Balls | HackerRank Determine if David can perform some sequence of swap operations such that each container holds one distinct type of ball. www.hackerrank.com Swap을 통해서 하나의 컨테이너에 하나의 타입만 놓을 수 있는 지 판단하는 문제다. 풀이 완전 탐색으로 문제를 풀 수 있을 것 같은데 시간 복잡도가 너무 많이 나올 것 같은 문제는 보통 DP 아니면 그리디인 경우가 많은데, 이 문제는 점..

문제 https://www.hackerrank.com/challenges/non-divisible-subset/problem Non-Divisible Subset | HackerRank Find the size of the maximal non-divisible subset. www.hackerrank.com Given a set of distinct integers, print the size of a maximal subset of where the sum of any 2 numbers in is not evenly divisible by k. 풀이 부분 집합 중에서 두개의 합이 항상 k 로 나눠지면 안되는 문제다. n < 10 ^ 5 기 때문에 모든 부분집합을 구해서 푸는 방법은 불가능하다. 두개의..

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 풀이 탐욕알고리즘의 기초문제 동전 거스르기 문제랑 같은 문제라고 보면된다. Greedy Algorithm 은 세가지 조건을 만족해야한다. 해 선택(Selection Procedure) : 지금 당시에 가장 최적인 해를 구한 뒤, 이를 부분해 집합에 추가한다. 적절성 검사(Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다. 해 검사(Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번부터 다시 시작한..