본문 바로가기

Algorithm study/재귀9

재귀함수를 이용해 순열 구하기 ✏️ 목표 1부터 n까지 번호가 적힌 구슬이 있는데, 이 중 m개를 뽑아 일렬로 나열하는 방법을 모두 출력해 보자. (이때 출력 순서는 사전순으로 오름차순으로 한다.) 📍 입력 첫 번째 줄에 자연수 n(3 2023. 7. 16.
재귀함수를 이용한 문제 풀어보기 - 동전 교환 ❓ 문제 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. ➡️ 입력 : 동전의 종류 개수 n (1 2023. 7. 15.
재귀함수를 이용해 중복순열 구하기 ✏️ 목표 1부터 N까지 번호가 적힌 구슬이 있는데, 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력한 후 마지막에는 방법의 수를 출력해 보자. (이때 출력 순서는 사전순으로 오름차순으로 출력해야 한다.) ❓ 중복순열 서로 다른 n개의 수에서 중복을 허락하여 r개를 선택하여 일렬로 나열하는 경우의 수이다. 따라서 같은 수를 여러 번 뽑아도 되는 것이다. 1부터 3까지 번호가 적힌 구슬 중에서 중복을 허락하여 2개를 뽑아 일렬로 나열하는 방법의 모든 경우의 수는 다음과 같다. (사전순으로) (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) 총 9개의 경우의 수가 나온다. 💡 해결하기 이번에는 이전 시간까지 계.. 2023. 7. 15.
재귀함수 이용한 문제 풀어보기 - 바둑이 승차 ❓ 문제 철수는 그의 바둑이들을 데리고 시장에 가려 한다. 그런데 그의 트럭은 C 킬로그램을 넘게 태울 수 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 만들어 보자. 📍 예제 // 입력예제 259 5 81 58 42 33 61 // 출력예제 242 💡 해결하기 ➡️ 기본 원리는 부분집합 구하기에서 사용했던 방식을 사용하면 된다. 재귀 함수로 부분집합 구해보기 (tistory.com) 재귀 함수로 부분집합 구해보기 ✏️ 목표 숫자를 하나 입력받아 해당 숫자까지의 모든 자연수들로 구성된 부분집합을 만들어 출력해 보자. (공집합은 출력하지 않는다.) ❓ 부분집합.. 2023. 7. 15.

티스토리툴바