본문 바로가기

recursion5

[백준] 1991번: 트리 순회 (Java) 1. 문제설명이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제이다.시간 제한: 2초메모리 제한: 128MB 2. 접근 방식루트 노드를 ‘A’로 설정하고, 이진 트리의 노드 정보를 입력받는다.노드 삽입각 노드에 대해 부모 노드와 자식 노드 정보를 입력받고, 해당 부모 노드를 트리에서 찾아서 왼쪽과 오른쪽 자식 노드로 연결한다.자식이 존재하지 않으면, 자식 노드를 null로 설정한다.재귀적으로 호출하여 트리의 모든 노드를 연결한다.전위 순회: 루트 노드부터 시작하여, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 방문한다.중위 순회: 왼쪽 자식 노드를 먼저 방문한 후, 루트 노드를 방문하고, 마지막으로 오른쪽 자식 노드를 방문한다.후위 순회: 왼쪽 자식 노드, 오른쪽 자식 노드를 .. 2024. 8. 25.
[백준] 18511번: 큰 수 구성하기 (Java) 1. 문제설명N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 문제이다.ex) N=657이고, K={1, 5, 7}일 때 답은 577시간 제한: 1초메모리 제한: 256MB 2. 접근 방식=> 재귀함수를 이용해 모든 가능한 숫자를 조합하여, (완전탐색) N보다 작거나 같은 가장 큰 수를 찾는다.K의 원소를 배열에 저장하고, 오름차순 정렬한다.재귀를 사용해서 주어진 원소를 조합해 가능한 모든 수를 만든다.만들어진 수가 n보다 크면 종료한다.만들어진 수가 n보다 작거나 같은 경우 중 최대값을 찾는다.배열을 역순으로 탐색한다. (큰 수부터 만들기 위해) 3. 최종 코드import java.io.*;import java.util.*;public class Main { s.. 2024. 8. 8.
[백준] 4779번: 칸토어 집합 (Java) 1. 문제설명주어진 n에 대해 “-”가 3^n이 있는 문자열을 생성하고, 모든 선의 길이가 1일 될 때까지 문자열을 3등분하여 가운데 문자열을 공백으로 만든다.마지막 문자열의 결과를 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식문자열을 3등분하고 모든 선이 1이 될 때까지 재귀 호출하는 함수를 사용한다.cantor 함수검사하려는 시작 인덱스(`s`)와 문자열 길이(`len`)를 매개변수로 받는다.`len`이 1이면 종료한다.`len`을 3으로 나눈 `div`를 구해, `s+div ~ s+div*2`에 해당하는 부분(2번째 부분)을 공백으로 변경한다.1번째, 3번째 부분을 재귀 호출한다. 3. 최종 코드import java.io.BufferedReader;import java... 2024. 8. 6.
[백준] 25501번: 재귀의 귀재 (Java) 1. 문제설명문제에서 주어진 팰린드롬(앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열)을 판별하는 isPalindrome 함수와 recursion 함수를 이용하여, 주어진 문자열에 대해 팰린드롬의 여부와 recursion 함수의 호출 횟수를 출력하는 문제이다.시간 제한: 2초메모리 제한: 1024MB 2. 접근 방식문제에서 주어진 isPalindrome, recursion 함수를 자바 코드로 수정한다.isPalindrome 함수recursion 함수를 호출하여 팰린드롬 여부를 검사하는 함수이다.문자열과 시작인덱스, 끝 인덱스를 인자로 recursion 함수를 호출한다.recursion 함수문자열이 팰린드롬인지 재귀적으로 확인하는 함수이다.왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 1을 반환.. 2024. 8. 5.
[백준] 10870번: 피보나치 수 5 (Java) 1. 문제설명n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식재귀 방법을 사용한다.피보나치 메서드합을 구한 두 개의 값을 매개변수로 받는다.두 개의 합을 구하고 저장한 뒤, 구한 합과 두 번째 매개 변수로 재귀 호출한다.n번째 피보나치 수를 구한 경우 종료한다.단, n이 0이면 0을 출력, 1이면 1을 출력한다. 그 외의 숫자는 피보나치 메서드를 호출한다. 3. 올바른 접근 방식 및 해결 방식재귀 방법을 사용해 피보나치 수를 구한다.n이 0과 1일 경우는 fibonacci 메서드를 호출하면 에러가 발생하기 때문에 따로 체크해주어야 한다. 4. 최종 코드import java.io.BufferedReader;import java.io.IOExc.. 2024. 8. 5.
반응형