DFS27 [ 자바스크립트(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. [ 자바스크립트(JavaScript) ] section08 - 7 - 최대점수 구하기(DFS) 📍 section08 - 7 - 최대점수 구하기(DFS) 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 구하는 문제다. 처음 문제를 봤을 때 회의실 배정문제와 비슷한 줄 알았는데, 그리디로는 풀 수 없었다. 점수를 높은 순으로 정렬(sort)한 다음 순서대로 풀면 제 한 시간 안에 최대 점수를 얻을 수 있지 않나?라고 생각했는데 그것보다, 모든 경우의 수(부분집합)를 구해서 M보다 작으면서 동시에 최대 점수를 갱신하면 되는 문제였다. 여기서 모든 경우의 수를 구하지 않고 edgeCut(가지치기)을 이용했는데 현재까지 누적된 시간이 M보다 크다면 더 이상 계산 할 필요 없이 return하는 코드를 추가했다. 종료 조건은 L===n인데, 문제는 한 유형당 한 개씩만 풀 수 있기 때문에 하나씩 모.. 2021. 9. 23. 이전 1 2 3 4 5 6 다음
