📌 01 - 경로 탐색(DFS-인접 행렬: 노드 개수가 적을 때) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. 다음과 같이 방향 그래프가 주어지면 인접 행렬로 표현할 수 있어야 한다. v 정점(행)에서 i 정점(열)으로 가는 경로가 존재한다면 1, 존재하지 않으면 0으로 표시한다. 📝 풀이 방법 v - 현재 정점, i - 마지막으로 도달해야하는 정점 ch - 해당 정점을 지났는지 체크하는 배열 재귀를 돌면서 graph[v][i]는 1이고 ch[i]는 0이라면 v 정점에서 i 정점으로 이동할 수 있다는 것이므로 해당 정점으로 이동했음을 나타내기 위해 ch[i]..

📌 15 - 수들의 조합 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 문제이다. 예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12, 2+4+12로 2가지가 있다. 📝 풀이 방법 😵 나의 풀이 방법 if문 안에 2개의 조건을 같이 주어 L(레벨)이 k(뽑는 개수)와 같더라도 sum이 6의 배수가 아니라면 else문으로 이동한다. 이 과정에서 결과는 동일하게 나오지만 시간을 잡아먹을 수 있다.🤬 L이 k와 같다면 else 문으로 이동하는 것이 아닌 if문 내부에서 sum이 6의 배수인지를 확인하고 빠져나와야 한다. function solution(n, k, arr,..

📌 14 - 조합 구하기 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하는 문제이다. M개를 뽑는다고 했으므로 조합을 이용해야 한다. N이 4이고 M이 2인 경우를 생각해보자❗ 위 그림과 같이 L1이 정해지면 L2는 L1 + 1부터 N까지 for 문을 돌면서 정해진다. 📝 풀이 방법 s는 for문에서 초기값에 해당한다. 다음과 같이 그림으로 한번 이해하고 외우도록 하자(중요❗) L(레벨)이 m과 같다면 하나의 경우가 만들어진 것이므로 tmp를 얕은 복사(slice)하여 answer에 추가한다. function solution(n, m) { let answer = []; let tmp = Array.from({ length: m }, () => 0); function DFS..

📌 13 - 수열 추측하기 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두 개를 더한 값이 저장되게 된다. 예를 들어 N이 4이고 가장 윗줄에 3 1 2 4가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 문제이다. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력해야 한다. 입력예제 4 16 출력예제 3 1 2 4 이번 문제를 풀기 위해서는 먼저 다음과 같은 규칙을 알아야한다. 빨간 색과 같이 순열의 첫 번째 부터 마지막 숫자까지 차례대로 n-1C0, n-1C1, n-1C2, n-1C3번 더해진 것을 알 수 있다. 결론적으로 순열 구..

📌 12 - 조합의 경우 수(메모이제이션) nCr = n! / (n - r)!r! 로 계산한다. 하지만 이 공식을 쓰지 않고 다음 공식을 사용하여 재귀를 이용해 조합 수를 구하는 문제이다. 입력설명 첫째 줄에 자연수 n(3

📌 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(동전의 합)이..