코딩관계론

문제 이해하기 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 계산하는 문제였다. 단 모든 예산을 지원해야 한다.문제 해결 방법 설명하기1. 경우의 수 계산하기  문제를 풀기 위해서 먼저 경우의 수를 계산해야 하는데 부서별 지원여부를 두고 경우의 수를 계산하면 2(해당 부서의 지원 여부 O or x)^100(부서의 개수)가 나오게 되고, 제한시간안에 문제를 해결할 수 없다. 따라서 완전 탐색은 사용할 수 없게 된다. 최대한 많은 부서에 예산을 지원하면 되기 때문에 예산 요청이 작은 순으로 지원하면 된다. 따라서 그리디하게 지원하면 문제를 해결할 수 있다. 코드def solution(d, budget): ..

문제 이해하기 등굣길 경로의 경우의 수를 구하는 문제이다. 좌표 (1,1)인 집에서 부터 (m,n)인 학교까지 가는 경로를 구하는 문제인데 사이에 웅덩이를 피해 가야한다. 경우의 수를 계산해보면 200!/(100! * 100!)이 된다. 매우 큰 수이기 때문에 완전탐색으로는 제한시간안에 답을 찾을 수 없다. https://m.blog.naver.com/parkhc1992/220669287080 [확률과 통계] 최단거리 경우의수 중2때 배운적이 있을거에요. 최단거리 경우의수 구하는 문제 예를 들면 이런 그림 하나주고 점A에서 점B... blog.naver.com 문제 해결 방법 설명하기 1. 최단거리 구하는 수 계산하기 최단 거리를 구하는 경우의 수는 아래의 그림과 같다. 이를 코드로 구현하면 아래와 같다..