📌 11 - 팩토리얼(DFS) 자연수 N을 입력하면 N! 값을 출력하는 문제이다. N! = N * (N - 1) * (N - 2) * ... * 1이다. 만약 N이 5라면 5! = 5 * 4 * 3 * 2 * 1 = 120이다. 👍 풀이 방법 재귀를 돌면서 n이 1과 같다면 1을 return한다. function solution(n) { let answer; function DFS(n) { if (n === 1) return 1; else return n * DFS(n - 1); } answer = DFS(n); return answer; } console.log(solution(5));

📌 10 - 순열 구하기 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하는 문제이다. 중복순열 구하기 문제와 다른 점은 중복없이 순서에 상관있게 선택한다는 점이다. 만약 3개의 자연수가 주어지고 이 중 2개를 뽑아 일렬로 나열하는 방법은 다음 그림과 같이 총 6가지이다. 👍 풀이 방법 ch 배열은 tmp 배열에 어떤 수가 선택되었는지 확인하기 위한 배열이다. (중복 검증) ch[i]의 값이 0이면 선택되지 않았다는 것이므로 선택해도 된다는 의미이다. 반대로 ch[i]의 값이 1이면 이미 선택되었다는 것이므로 건너뛴다. L(트리의 레벨)이 m과 같다면 하나의 경우가 완성된 것이므로 tmp 배열을 얕은 복사하여 answer 배열에 추가한다. DFS 함수의 호출이 끝..

📌 09 - 동전교환(DFS) 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려고 한다. 이때 동전의 최소 개수를 출력하는 문제이다. 각 단위의 동전은 무한정 쓸 수 있다. 입력예제 1 2 5 15 출력예제 3 설명: 5 5 5 동전 3개로 거슬러 줄 수 있다. 👍 풀이 방법 중복순열 구하기 문제를 먼저 이해하고 온다면 어렵지 않게 이번 문제를 해결할 수 있을 것이다. 단, 이번에는 함수를 종료시켜야 하는 시점을 잘 생각해봐야 한다. 불필요한 탐색까지 할 필요가 없기 때문이다. 동전의 최소 개수를 구하는 문제이므로 answer(그 시점에 동전의 최소 개수)보다 L(레벨, 동전의 개수)이 크거나 같다면 더 이상 깊이 탐색할 필요 없이 return 한다. sum(동전의 합)이..

📌 08 - 중복순열 구하기 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력하는 문제이다. 입력예제 3 2 출력예제 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 재귀를 알지 못했다면 이중 for 문(뽑는 횟수 2번)을 이용해 풀었을 것이다. 게다가 다중 for 문과 재귀는 같다고 해도 무방하다. 하지만 왜 더 간단한 이중 for 문을 사용하지 않고 재귀를 이용해 문제를 풀어야 할까 하는 의문이 생긴다..🤔 for 문을 이용한 방법 function solution(n) { let answer = []; for (let i = 1; i

📌 07 - 최대점수 구하기(DFS) 이번 정보 올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는 데 걸리는 시간이 주어지게 된다. 제한 시간 M 안에 N개의 문제 중 최대점수를 얻을 수 있는 경우를 구하는 문제이다. 단, 해당 문제는 해당 시간이 걸리면 푸는 걸로 간주하고 한 유형당 한 개만 풀 수 있다. 👍 풀이 방법 이전에 풀었던 바둑이 승차 문제를 이해했다면 이 문제 또한 어떻게 풀어야 하는지 감이 올 것이다. 문제를 푼다, 안푼다, 2가지의 경우의 수만 존재한다. 재귀를 돌면서 문제를 푼 경우 sum 변수에 해당 문제의 점수를 누적하고 time 변수에 해당 문제를 푸는데 걸리는 시간을 누적한 후 인자로 보낸..

📌 08 - 바둑이 승차(DFS) 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 단, 철수는 C킬로그램을 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶어한다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 문제이다. 👍 풀이 방법 각각의 바둑이를 트럭에 태운다, 안 태운다, 2가지의 경우의 수만 있으므로 이진 트리 구조의 부분집합을 구하는 문제를 떠올려야 한다. 다음 부분집합 구하기 문제를 참고해보자. 재귀를 돌면서 트럭에 태운 바둑이들의 무게 합(sum)을 구한다. sum이 c(트럭에 태울 수 있는 최대 무게)보다 큰 경우엔 바로 return 한다. sum이 c보다 작으면서 L(이진 트리 레벨)이 배열의 길이와 같다면 하나의 부분..

📌 05 - 합이 같은 부분집합(DFS : 아마존 인터뷰) N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력하는 문제이다. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 한다. 👍 풀이 방법 부분집합 구하기 문제의 풀이 과정을 그림으로 그려가면서 이해를 했다면 어렵지 않은 문제이다. 이번 문제 또한 그림을 그리면서 이해를 하였다. 배열 요소들의 총 합(total)을 구한다. 재귀를 돌다가 탐색하고 있는 idx가 배열의 길이와 같다면 총 합에서 sum(부분 집합의 합)을 뺀 값이 sum과 같은지 비교한다..

📌 04 - 부분집합 구하기(DFS) 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 문제이다. 첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래의 출력예제와 같은 순서로 출력해야 한다. 단, 공집합은 출력하지 않는다. 입력예제 3 출력예제 1 2 3 1 2 1 3 1 2 3 2 3 부분집합의 개수는 2^N 이지만 공집합은 출력하지 않으므로 -1을 해준다. N이 3이면 출력해야하는 부분집합의 개수는 7개가 된다. 재귀함수를 이용해 부분집합을 찾아갈 때 다음과 같이 그림을 그리면서 이해를 하면 도움이 된다. 📝 소스 코드 function solution(n) { let answer = []; let ch = Array.from({ length: n + 1 }, () => 0..