일단 내가 생각한 문제는, 동전이 다양한 금액으로 여러개 있을때, 두 사람한테 최대한 공정하게 분배하려면 어떻게 분배해야 할까. 나는 이 문제가 그리디라고 생각했다. 하지만 디피라는 의견이 있는데 왜 그런지 모르겠어서 다른 문제들을 찾아보고 문제 분석과 올바른 접근법을 생각해 보려 한다.
https://www.acmicpc.net/problem/1943
1943번: 동전 분배
세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다.
www.acmicpc.net
음 일단 나중에 풀겠지만, 절반으로 정해진 금액을 만들 수 있는지 여부에 대한 문제이다.
https://www.acmicpc.net/problem/17528
17528번: Two Machines
문제 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작
www.acmicpc.net
음 이게 완탐은 아닌건 알겠는데, 초반에 그리디로 선택 못하겠다는건 알겠다. 왜냐면 초반에 고른걸로 최소 작업 시간이 결정되지 않고, 이후에 결정도 영향을 끼치기 때문이다. 이럴때 무엇을 사용해야 할까?
https://www.acmicpc.net/problem/10982
10982번: 행운쿠키 제작소
데브베이커리에서는 기념일을 맞아 직원들에게 행운쿠키를 선물하기로 하였다. 회사의 간식을 담당하는 철수는 나누어줄 행운 쿠키를 준비하는 역할을 맡게 되었다. 행운쿠키를 만들기 위해서는 N개의 행운반죽을 2개의 오븐을 이용해 구워야 한다. 각각의 행운반죽은 2개의 오븐 중 1개의 오븐에서만 구워져야 하며, 어떤 오븐에서 굽는지에 따라 구워지는데 걸리는 시간이 다르다. 각각의 오븐은 독립적으로 반죽을 구울 수 있으며, 오븐에 반죽을 넣거나 빼는데 걸리는 시간은
www.acmicpc.net
이것도 투머신이랑 똑같다.
https://en.wikipedia.org/wiki/Subset_sum_problem
Subset sum problem - Wikipedia
In computer science, the subset sum problem is an important decision problem in complexity theory and cryptography. There are several equivalent formulations of the problem. One of them is: given a set (or multiset) of integers, is there a non-empty subset
en.wikipedia.org
이 글은 음 부분 합 문제에 대한 글이다.
부분합 문제는 복잡도와 암호화와 관련되서 중요한 결정 문제라고 한다. 몇가지 동일한 형태의 문제들이 있다함. 만약 정수 집합이 주어져있다 해보자. 그 집합 안에 원소들의 합이 0인 부분집합이 존재하는가 ?이런 문제는 np-complete, 즉 주어진 문제에 대한 해결이 유효한지 확인하기 쉽지만, 처음에 봤을때 해결법이 있는지 알기는 어렵다는 말이다 (???).
동일한 다른 형태의 문제는, 자연수들이 주어져 있을때 그 안의 어떤 부분합이 W를 만들 수 있는가? 이 문제는 냅색 문제의 특별한 케이스라 볼 수 있다. 하나의 흥미로운 케이스는 부분합은 partition problem이라 볼 수 있다, 예를 들면 W는 자연수 전체 합의 절반이라 던가.
음 일단 np-complete등에 대한 용어가 잘 기억이 안난다. 그리고 파티션 문제라는게 어떤건지 잘 감이 안잡힌다.
[https://en.wikipedia.org/wiki/Partition_problem]
[https://en.wikipedia.org/wiki/Knapsack_problem]
일단 투머신을 풀어보고 싶다.
'알고리즘 문제 풀기' 카테고리의 다른 글
| <백준> 2294번 동전2 (0) | 2020.04.16 |
|---|---|
| <알고리즘 문제> 해설 보면 안됐는데;, 중요 , 백준 동전1 2293번 (0) | 2020.04.12 |
| <백준> 11400번 단절선, 이중 연결 요소. (0) | 2020.04.04 |
| <leet code> Add Two Numbers ,etc/ c++ malloc vs new (0) | 2020.03.12 |
| <leet code> Two sum (0) | 2020.03.12 |