반응형 재귀함수16 [백준] 15654번 - N과 M(5) (Java) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 오름차순으로 출력해야 하기 때문에 입력값을 먼저 정렬해야 한다. 2. 숫자 대신 배열 인덱스를 넘겨주고, 배열 A[i]를 저장한다. 3. 중복 조합을 허용하지 않기 때문에 방문배열을 사용한다. - 방문한 숫자가 아니면 값을 조합한다. - 재귀에서 돌아오면 다음 탐색을 위해 방문처리를 초기화한다. import java.util.Scanner; import java.util.Arrays.. 2022. 12. 9. [백준] 15652번 - N과 M(4) (Java) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복 숫자를 허용한다. - 방문배열 사용X 2. 순서가 바뀌어도 동일 조합으로 본다. - for(i=start to N)으로 하고 재귀호출 때 DFS(i, level+1)을 한다. import java.util.Scanner; import java.lang.StringBuilder; public class Main { static int N, M; static int A[]; static .. 2022. 12. 9. [백준] 15651번 - N과 M(3) (Java) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복숫자와 순열 모두 허용이다. N과 M (1)과 (2)에서 중복을 막기 위해 사용했던 visited[]을 사용 안하면 된다. 다만, 출력을 System.out.print()를 하게 되면 시간초과가 난다. 대신 StringBuilder로 문자열을 계속 머지한다음 마지막 한번 출력했더니 통과했다. import java.util.Scanner; //[백준] 15651번 - N과 M(3) (Java).. 2022. 10. 13. [백준] 15650번 - N과 M(2) (Java) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(1)과 비슷한데 중복 순열을 허용하지 않는 점이 차이가 닌다. 이전 문제는 중복 숫자만 방문배열을 통해서 처리를 했는데 이 문제에서는 순서가 달라도 중복이면 표시하면 안된다. 예제를 보면, 4 2 ---- 1 2 1 3 1 4 2 3 2 4 3 4 이런 식으로 1로 시작하는 값이 2로 시작하는 순열을 시작할 때 중복체크 락이 걸려있어야 한다. (1)에서는 재귀 호출에서 돌아오면 중복체크.. 2022. 10. 13. [백준] 15649번 - N과M(1) (Java) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다. dfs탐색을 사용한 백트레킹 알고리즘으로 풀자. 백트레킹은 탐색할 노드를 조건문으로 판단하여 유.. 2022. 10. 13. 재귀함수 - 재귀적으로 작성하는 법 1. 재귀 카테고리 : 반복 실행 - 반복적으로 한 작업을 실행하는 알고리즘이다. - 파라미터를 전달해 반복 계산한다. - 재귀에는 항상 종료 조건이 있어야 한다.(!) - 재귀 함수는 전체 작업의 일부만 수행하고, 나머지는 재귀 호출에 위임한다. 2. 재귀 카테고리 : 계산 - 하위 문제의 계산 결과에 기반해 계산할 수 있다. - 하위 문제는 입력값을 더 작게 한 똑같은 문제이다. - Factorial 함수가 대표적이다. - 계산 방식은 "상향식"과 "하향식"이 있는데, 상향식은 루프와 재귀의 방식이 같다. - 하향식이야 말로 재귀를 사용하는 주된 이유이다. 3. 하향식 재귀 : 새로운 사고방식 3-1. 하향식 사고 절차 a. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자. b. 문제의 하위 .. 2022. 9. 19. [백준] 10872번 - 팩토리얼 (Java) https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼은 그 수 보다 작은 모든 정수의 곱이다. 5! = 5 x 4 x 3 x 2 x1이다. 즉, n! = n x (n-1)!과 동일하다. 이를 재귀함수로 구성하자. import java.util.*; import java.io.*; /* [백준] 10872번 - 팩토리얼 (Java) */ public class Main { static int N; void InputData() { Scanner in = new Scanner(System.in); N = in.nextInt(); } // 재귀함수로.. 2022. 9. 19. 이전 1 2 다음 반응형
