inflearn78 [ 자바스크립트(JavaScript) ] section08 - 12 - 조합의 경우 수(메모이제이션) 📍 section08 - 12 - 조합의 경우수 (메모이제이션) 다음 공식을 사용하여 재귀를 이용해 조합수를 구하는 프로그램을 작성하세요. 조합의 경우의 수를 구하는 문제는 n의 범위가 20정도 넘으면 메모이제이션으로 풀어야 한다. 왜냐하면 연산 시간이 오래 걸리기 때문이다. 메모이제이션을 하는 이유는 동일한 계산을 반복하지 않기 위함인데, 이전에 한창 지식인 답변 활동을 했을 때 피보나치 수열의 합계를 구하는 질문에서 답했었다. 문제에 주어진 공식으로 풀 때 메모이제이션을 적용하는 이유도 마찬가지다. 그런데 기존에 알던 공식을 사용해도 되는데 새로운 공식을 사용하는 이유는 뭘까?(이 공식을 나는 처음 봤다 😅 😅) 예를 들어 5[1, 2, 3, 4, 5]개 중 3개를 뽑는 경우의 수(5C3)를 구한다고.. 2021. 9. 28. [ 자바스크립트(JavaScript) ] section08 - 11 - 팩토리얼 📍 section08 - 11 - 팩토리얼 자연수 N이 주어지면 N! 값을 구하는 문제다. 재귀 함수를 통해서 풀 수 있는데 종료 조건은 N이 1일 때 return 1을 선언해주고, 나머지는 return n * factorial(n-1)을 해준다. 흐름은 다음과 같다. let n = 5; console.log(solution(n)); function solution(n) { let answer; function factorial(n) { if (n === 1) return 1; else return n * factorial(n - 1); } answer = factorial(n); return answer; } 2021. 9. 27. [ 자바스크립트(JavaScript) ] section08 - 10 - 순열구하기 📍 section08 - 10 - 순열구하기 문제: 10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하라.(중복은 허락하지 않는다.) // 입력 3 2 3 6 9 // 출력 3 6 3 9 6 3 6 9 9 3 9 6 이전에 풀었던 중복을 허락하여 순열 구하기와 비슷한 문제이지만 이번엔 중복을 허락하지 않는 조건에서 푸는 문제다. 중복을 허락하지 않았을 때 나올 수 있는 전체 경우의 수는 3*2=6이다. 핵심 포인트는 visited 배열을 선언하여 이전에 방문했던 index는 제외하고 방문하면 중복되지 않은 값이 나온다. 또한, 방문하고 다시 올라갈 때 visited를 0으로 바꿔줘야 다음 L에서 index를 순서대로 방문한다는 점이다. visited를 0으로 바꿔.. 2021. 9. 26. [ 자바스크립트(JavaScript) ] section08 - 9 - 동전교환 📍 section08 - 9 - 동전교환 다음과 같이 여러 단위의 동전들이 있을 때 거스름돈을 가장 적은 수의 동전으로 교환하려면 어떻게 할까? 각 단위의 동전은 무한정 쓸 수 있다. // 입력 3 1 2 5 15 // 출력 // (5, 5, 5) 동전 3개로 거슬러 줄 수 있다. 3 거스름돈 문제는 그리디로 풀어본 적 있다. 하지만, 이 문제는 그리디로는 풀 수 없다. 왜냐하면 동전의 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우기 때문이다. 이럴 땐 DFS 혹은 DP를 이용하면 된다. 만약, 동전이 [500, 100, 50, 10]처럼 배수형태로 나오면 그리디로 풀 수 있다. 또, 앞서 배운 부분집합으로는 이 문제를 풀 수 없는데, 왜냐하면 동전을 각 한 번씩 쓰는 것이 아니고 거스름돈이 더 .. 2021. 9. 23. [ 자바스크립트(JavaScript) ] section08 - 8 - 중복순열 구하기 📍 section08 - 8 - 중복순열 구하기 1부터 N까지 적힌 구슬이 있는데, 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력하라. // 입력 3 2 // 출력 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 9 입력으로 주어진 중복순열의 모든 경우의 수는 n*n 즉, 9가 된다. 그런데, 이런 중복순열 문제는 다음과 같이 for문으로 풀면 더 간단하지 않을까? let n = 3; let m = 2; for (let i=1 ; i 2021. 9. 23. 이전 1 2 3 4 5 6 7 ··· 16 다음
