SSAFY 합격의 중심, 알고리즘잡스입니다.
성원 감사 CT 퀴즈 이벤트에 참여해주심에 감사드립니다.
<공 묶음> 문제
추후 재업로드 예정
(기존 수강생은 수강생 전용 토론방 참고)
<공 묶음> 풀이
이번 문제는 그리디 알고리즘 문제 입니다.
공을 오름차순으로 정렬하는걸로 시작합니다.
첫번째 묶음에 가장 가벼운 공을 넣습니다.
그 후 두번째로 가벼운 공이 첫번째 공과 같은 묶음에 들어갈 수 있는지 확인해봅니다. 만약 같은 묶음에 포함될 수 있다면 같은 묶음에 넣고, 포함될 수 없다면 새로운 묶음을 만들어 두번째로 작은 공을 넣습니다.
세번째 공도 마찬가지로 이전에 만들어둔 묶음 중 들어갈 수 있는 곳이 있다면 그중 아무데나 들어가고, 없다면 새로운 묶음을 만들어줍니다. 이를 모든 공에 반복하면 이 문제를 해결할 수 있습니다.
이게 정답을 찾을 수 있다는 증명이 필요한데, 들어갈 수 있는 묶음이 있는데 안들어가는게 더 좋은 정답이 될 수 없다는 것, 그리고 들어갈 수 있는 묶음이 여럿일 때 아무데나 들어가면 된다는 것을 증명해야 합니다. 해당 증명은 여기서 다루지 않지만 어렵지 않으니 한번쯤 생각해보시면 좋을 것 같습니다.(아래 야옹님의 게시글에 아무데나 들어가면 된다는 것에 대한 간단한 증명이 적혀있습니다.)
해당 과정을 빠르게 하는 방법을 알려드리겠습니다. 이 풀이에서는 큐 자료구조를 사용합니다.
네번째 케이스를 보겠습니다.
1 2 3 4 9 16 27 32 64 81 128 243 256, 30
첫번째 수를 큐에 넣습니다.
1
두번째 수는 큐의 제일 앞에 있는 수와 묶일 수 없으므로 그냥 큐에 넣습니다.
1 2
일곱번째 수까지는 모두 서로 묶일 수 없으므로 큐에 넣습니다.
1 2 3 4 9 16 27
그 다음 32는 큐의 맨 앞에 있는 1과 30 이상의 차이가 있으므로 1을 빼고 32를 큐에 넣어줍니다.
2 3 4 9 16 27 32
그 다음 64도 큐의 맨 앞에 있는 2와 30 이상의 차이가 있으므로 큐에서 2를 빼고 64를 큐에 넣어줍니다.
3 4 9 16 27 32 64
이렇게 큐에 단순히 수를 넣는 것은 묶음을 추가하는 과정, 큐에서 수를 빼고 뒤에 새로운 수를 추가하는 것은 기존 묶음에 공을 추가하는 과정이라고 볼 수 있습니다. 이는 위에서 설명한 공이 묶일 수 있다면 그중 아무 그룹에 공을 넣고, 불가능하다면 새로운 묶음을 만드는 과정과 동치입니다.
<공 묶음> 정답
1) 2
2) 3
3) 4
4) 7
5) 9
SSAFY 합격의 중심, 알고리즘잡스입니다.
성원 감사 CT 퀴즈 이벤트에 참여해주심에 감사드립니다.
<공 묶음> 문제
추후 재업로드 예정
(기존 수강생은 수강생 전용 토론방 참고)
<공 묶음> 풀이
이번 문제는 그리디 알고리즘 문제 입니다.
공을 오름차순으로 정렬하는걸로 시작합니다.
첫번째 묶음에 가장 가벼운 공을 넣습니다.
그 후 두번째로 가벼운 공이 첫번째 공과 같은 묶음에 들어갈 수 있는지 확인해봅니다. 만약 같은 묶음에 포함될 수 있다면 같은 묶음에 넣고, 포함될 수 없다면 새로운 묶음을 만들어 두번째로 작은 공을 넣습니다.
세번째 공도 마찬가지로 이전에 만들어둔 묶음 중 들어갈 수 있는 곳이 있다면 그중 아무데나 들어가고, 없다면 새로운 묶음을 만들어줍니다. 이를 모든 공에 반복하면 이 문제를 해결할 수 있습니다.
이게 정답을 찾을 수 있다는 증명이 필요한데, 들어갈 수 있는 묶음이 있는데 안들어가는게 더 좋은 정답이 될 수 없다는 것, 그리고 들어갈 수 있는 묶음이 여럿일 때 아무데나 들어가면 된다는 것을 증명해야 합니다. 해당 증명은 여기서 다루지 않지만 어렵지 않으니 한번쯤 생각해보시면 좋을 것 같습니다.(아래 야옹님의 게시글에 아무데나 들어가면 된다는 것에 대한 간단한 증명이 적혀있습니다.)
해당 과정을 빠르게 하는 방법을 알려드리겠습니다. 이 풀이에서는 큐 자료구조를 사용합니다.
네번째 케이스를 보겠습니다.
1 2 3 4 9 16 27 32 64 81 128 243 256, 30
첫번째 수를 큐에 넣습니다.
1
두번째 수는 큐의 제일 앞에 있는 수와 묶일 수 없으므로 그냥 큐에 넣습니다.
1 2
일곱번째 수까지는 모두 서로 묶일 수 없으므로 큐에 넣습니다.
1 2 3 4 9 16 27
그 다음 32는 큐의 맨 앞에 있는 1과 30 이상의 차이가 있으므로 1을 빼고 32를 큐에 넣어줍니다.
2 3 4 9 16 27 32
그 다음 64도 큐의 맨 앞에 있는 2와 30 이상의 차이가 있으므로 큐에서 2를 빼고 64를 큐에 넣어줍니다.
3 4 9 16 27 32 64
이렇게 큐에 단순히 수를 넣는 것은 묶음을 추가하는 과정, 큐에서 수를 빼고 뒤에 새로운 수를 추가하는 것은 기존 묶음에 공을 추가하는 과정이라고 볼 수 있습니다. 이는 위에서 설명한 공이 묶일 수 있다면 그중 아무 그룹에 공을 넣고, 불가능하다면 새로운 묶음을 만드는 과정과 동치입니다.
<공 묶음> 정답
1) 2
2) 3
3) 4
4) 7
5) 9