반응형 재귀함수3 [실버1]백준 1342번(행운의 문자열) - 코테공부 26일차(2025.02.17) 문제유형백트래킹, 제귀함수풀이 방법 도출 과정1. 예로 들어 aaabbbaaa는 같은 문자열이 오는 경우가 있어 행운의 문자열이 아니다.2. 그런데 이 문자열들을 순열로 하여 섞어 행운의 문자열을 찾는 것이 문제이다. 3. 문자열의 모든 가능한 순열을 생성하고 그 문자가 행운의 문자열인지 알아내는 코드를 작성해보도록 하겠다.시간 복잡도시간 복잡도는 모든 순열의 수 N! X 각 순열을 생성하는 데 걸리는 시간 N을 곱한 정도가 된다. 최악의 경우 10! X 10정도는 3600만이므로 1초 이내에는 계산이 가능하다. 코드 및 간단설명백트래킹과 재귀함수를 활용하여 문제를 해결하였다. def func(lev): global S, chars, cnt, choose, ans # base case .. 2025. 2. 17. [class2]백준 4779번(칸토어 집합) - 코딩테스트 23일차(2025.02.13) 문제유형재귀 함수풀이 방법 도출 과정1. 3^N 개가 있는 문자열을 만든다.2. 문자열을 3등분 한 뒤 가운데 문자열을 공백으로 바꾼다.3. 나머지 2개를 3등분하고 가운데를 공백으로 바꾼다.4. 모든 선의 길이가 1이면 멈춘다.5. 이걸 출력하는 프로그램을 만들면 된다.6. 이걸 재귀함수로 만들어보도록 하겠다. 시간 복잡도각 단계에서 N만큼의 문자열 결합 연산이 발생.재귀적으로 N/3 크기의 문제를 두 번 호출.즉, O(N/3)이 시간복잡도 코드 및 간단설명재귀함수를 사용하여 문제를 풀었다. def line_one(N): if N == 1: return '-' prev = line_one(N // 3) space = ' ' * (N // 3) return.. 2025. 2. 13. [class1]백준 10870번(피보나치 수 5) - 코딩테스트 23일차(2025.02.13) 문제유형재귀 함수풀이 방법 도출 과정1. 피보나치 수는 n = (n-1) + (n+1)의 형태를 띄고 있다. 2. 이런 경우 재귀함수를 쓰게 되면 간단하게 풀수가 있을 것이다.3. 이를 이용하여 문제를 풀어보도록 하겠다. 시간 복잡도입력 받기 O(1)재귀함수 O(2^n)총 O(2^n)이 시간 복잡도이다코드 및 간단설명재귀함수를 사용하여 문제를 풀었다. def ponachi_num(n): if n == 0: return 0 if n == 1: return 1 return ponachi_num(n-1) + ponachi_num(n-2)n = int(input())print(ponachi_num(n))다른 풀이1) 메모이제이션을 사용하는 재귀 구현 메모이제이션은 이미 .. 2025. 2. 13. 이전 1 다음 반응형
