Mason

문제 여러가지 지폐의 종류로 원하는 액수를 가저갈수 있는 모든 경우의 수를 구하라. 예를들어 $50, $20, $10 3가지의 지폐종류가 있고 총 50 달러를 가저가려할때 가질수 있는 모든 경우의 수인 4를 구해 반환해야 한다. $50 * 1 $20 * 2, $10 * 1 $20 * 1, $10 * 3 $10 * 5 입력 int 타입의 자연수 int target int 타입의 요소를 갖는 배열 int[] type 출력 long 타입의 모든 경우의 수 풀이 재귀 class Solution { public long ocean(int target, int[] type) { int[] newType = IntStream.of(type).boxed().sorted(Collections.reverseOrder())..

재귀를 이용하여 코딩테스트를 하던도중 계속해서 실행시간 초과로 실패하였는데 알고보니 DP라는 것을 이용해야 하는 문제 였다. 동적 계획법 (DP) 최소의 단위로 문제를 쪼개어 연산한 뒤 배열에 저장하고 그 값들을 계속해서 이용하여 연산 후 배열에 저장, 결국엔 최종 값까지 도달하는 알고리즘 설계 기법이다. 간단히 말해 최소 단위의 문제를 푼뒤 그 값들을 계속해서 재활용하여 최후의 값을 구하는 방식이다. DP의 특징 DP를 사용할때 문제를 최소단위에서부터 연산을 시작하여 나온 값을 이용해 연속적으로 연산을 하게되는데 이는 재귀 구조와 매우 비슷하다. 이렇게 답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 하는 종류의 문제의 구조를 최적 부분 구조(OPtimal Substructure)라 부르며 ..

재귀함수란? mdn에서의 정의는 함수가 자기 자신을 호출하는 행위 이며 더 작은 부분 문제들을 해결하기 위해 사용된다... 란다. 간단히 말해서 어떠한 문제를 해결하기 위해 자기 자신을 호출하는 함수이다. (출처:https://developer.mozilla.org/en-US/docs/Glossary/Recursion) 자기 자신을 반복적으로 호출하는 것이기 때문에 반복문으로도 작성이 가능하다. 고롬 한번 간단하게 작성해보자! 재귀함수를 이용한 factorial 함수 const factorial = (n) => { if (!n) return 1;//base case return n * factorial(n - 1);//recursive case }; factorial(4); 위처럼 재귀함수를 이용하여 f..