🔸 볼링공 고르기 A,B 두 사람이 볼링공을 고를 수 있는 조합의 수를 구하는 문제이다. 볼링공 수는 N으로 최대 1,000 볼링공 무게는 M으로 최대 10 서로 같은 무게의 볼링공은 고를 수 없음 같은 무게의 공이 여러 개 존재할 수 있지만, 다른 공으로 간주 📌 예시 5 3 1 3 2 3 2 → 8가지 8 5 1 5 4 3 2 4 5 2 → 25가지 📌 초기 접근 방법 A가 첫 번째 공을 골랐다고 가정한다. 1을 골랐으므로, 나머지 공 중 1이 아닌 것의 개수를 구한다. 그 뒤 3을 골랐을 경우, 나머지 공 중 3이 아닌 것의 개수를 구한다. ... 위의 방식으로 첫 번째 공, 두 번째 공, 세 번째 공을 골랐을 때마다 뒤의 공 중 무게가 다른 공의 개수를 합해가며 최종 답을 구하였다. 📌 교재 접근..

🔸 만들 수 없는 금액 동전 n개가 주어졌을 때, 해당 동전들로 만들 수 없는 금액을 구하여라. 동전은 최대 1000개, 각 동전의 크기는 최대 1,000,000원이다. ex) 1,2,3, 7원 동전이 주어졌을 때, 1원 : 1 2원 : 1 3원 : 3 4원 : 1+3 5원 : 2+3 6원 : 1+2+3 7원 : 7 8원 : 1+7 9원 : 2+7 10원 : 3+7 11원 : 1+3+7 12원 : 2+3+7 13원 : 1+2+3+7 14원 : X 📌 초기 접근 방법 처음에 생각한 접근 방식은 어려웠다. 동전의 모든 조합을 구한다. 조합 별 최종 합을 구한다. 최종 합을 set에 담는다. 여기서 문제는 모든 조합을 구할 때 너무 많은 비용이 든다. Combination 연산 시에는 팩토리얼 단위로 연산하기..

🔸그리디 알고리즘 Greedy는 탐욕스럽다는 뜻으로 매 순간 최선의 선택을 수행함으로써 문제를 해결하는 방식입니다. 따라서 몇몇 예외를 제외하면 문제 유형이나 테크닉한 기술 없이도 풀 수 있는 문제입니다. 하지만, 문제를 접했을 때 해결할 수 있는 최소한의 아이디어는 떠올릴 수 있어야 해결이 가능하므로 문제풀이를 통해 감을 익힐 필요가 있는 유형이라고 볼 수 있습니다. 단, 다익스트라 알고리즘, 정렬 알고리즘과 함께 출제되는 경우 미리 숙지가 필요한 경우도 있습니다. 📌 정리 그리디 알고리즘을 해결하기 위해서는 다음 능력을 키울 필요가 있습니다. 매 번 최선의 선택만 수행해도 문제를 해결할 수 있는지를 파악해야 합니다. 문제를 해결하기 위한 최소한의 아이디어를 떠올릴 수 있어야 합니다. 명확한 문제 유형..