인공지능 사관학교 - 1주차 기초 파이썬 (5일차, 재귀함수/완전탐색)

탐색 알고리즘 (Day5)

재귀 함수

재귀 함수의 기본 구조

재귀 함수는 두 가지 주요 부분으로 구성됩니다:

1. 기본 조건 (Base Case): 재귀 호출을 멈추는 조건입니다. 이 조건이 충족되면 함수는 더 이상 자신을 호출하지 않고 종료됩니다.
2. 재귀 조건 (Recursive Case): 함수가 자기 자신을 호출하는 부분입니다. 이 부분이 기본 조건을 향해 문제를 축소시킵니다.

예제: 팩토리얼 함수

팩토리얼 함수는 양의 정수 n에 대해 1부터 n까지의 정수를 모두 곱한 결과를 반환하는 함수입니다. 팩토리얼을 재귀적으로 정의하면 다음과 같습니다:

• 0! = 1 (기본 조건)
• n! = n * (n-1)! (재귀 조건)

이를 파이썬으로 구현하면 다음과 같습니다:

 

예제: 피보나치 수열

피보나치 수열은 각 항이 앞의 두 항의 합인 수열입니다. 첫 번째 항은 0, 두 번째 항은 1입니다. 피보나치 수열을 재귀적으로 정의하면 다음과 같습니다:

• F(0) = 0 (기본 조건)
• F(1) = 1 (기본 조건)
• F(n) = F(n-1) + F(n-2) (재귀 조건)

이를 파이썬으로 구현하면 다음과 같습니다:

 

재귀 함수의 중요 개념

1. 기본 조건: 반드시 있어야 하며, 없으면 함수가 무한히 호출되어 스택 오버플로(Stack Overflow)가 발생합니다.
2. 재귀 조건: 문제를 기본 조건으로 점진적으로 축소시키는 부분입니다.

장점과 단점

장점

• 단순성: 문제를 단순하게 표현할 수 있습니다. 복잡한 문제를 재귀적으로 정의하여 쉽게 이해할 수 있습니다.
• 분할 정복: 문제를 작은 부분 문제로 나누어 해결하는 데 유용합니다. 많은 알고리즘이 재귀적으로 구현됩니다.

단점

• 효율성: 많은 경우 재귀 호출은 함수 호출 스택을 많이 사용하여 메모리 효율이 떨어질 수 있습니다.
• 오버헤드: 재귀 호출 시마다 함수 호출에 따른 오버헤드가 발생합니다.
• 스택 오버플로: 너무 깊은 재귀 호출은 스택 오버플로를 초래할 수 있습니다.

재귀를 반복문으로 변환

재귀 함수는 때때로 반복문으로 변환할 수 있습니다. 예를 들어, 위의 팩토리얼 함수는 다음과 같이 반복문을 사용하여 구현할 수 있습니다:

 

 

피보나치 수열도 다음과 같이 반복문으로 구현할 수 있습니다:

 

요약

• 재귀 함수는 함수가 자기 자신을 호출하는 함수입니다.
• 기본 조건과 재귀 조건을 포함해야 합니다.
• 장점: 단순하게 문제를 표현하고, 분할 정복에 유용합니다.
• 단점: 효율성 문제, 스택 오버플로 위험, 함수 호출 오버헤드.
• 재귀 함수는 때때로 반복문으로 변환할 수 있습니다.

----------------------------------------------------------------------------------------------------------------

완전 탐색

💡 완전 탐색(Brute Force)은 가능한 모든 경우를 모두 탐색하여 문제의 해를 찾는 알고리즘 기법입니다.

• 문제의 해를 보장하기 때문에 직관적이며 이해하기 쉽지만, 일반적으로 매우 비효율적
• 주로 문제의 입력 크기가 작거나, 최적의 해를 반드시 찾아야 하는 상황에서 사용

완전 탐색의 특징

1. 단순함: 모든 가능한 경우를 탐색하므로 알고리즘이 매우 단순하고 직관적입니다.
2. 보장된 해: 가능한 모든 경우를 확인하므로, 문제의 해를 반드시 찾을 수 있습니다.
3. 비효율성: 경우의 수가 기하급수적으로 증가할 수 있기 때문에 시간 복잡도가 매우 높아질 수 있습니다.

완전 탐색의 종류

완전 탐색은 여러 방식으로 구현할 수 있으며, 일반적으로 다음과 같은 방법이 사용됩니다:

1. 순열 (Permutation): 주어진 요소들의 모든 순서를 탐색합니다.
2. 조합 (Combination): 주어진 요소들 중에서 일부를 선택하는 모든 경우를 탐색합니다.
3. 부분 집합 (Subset): 주어진 요소들의 모든 부분 집합을 탐색합니다.
4. 백트래킹 (Backtracking): 불필요한 경우의 수를 줄이기 위해 탐색을 중간에 중단하는 방법입니다.

1. 순열 (Permutation)

주어진 리스트의 모든 순서를 탐색하는 반복문을 사용한 방법입니다.

재귀

 

스택

 

 

2. 조합 (Combination)

주어진 리스트에서 특정 개수의 요소를 선택하는 모든 경우를 반복문을 사용하여 탐색하는 방법입니다.

 

재귀

 

스택

 

 

3. 부분 집합 (Subset)

주어진 리스트의 모든 부분 집합을 반복문을 사용하여 탐색하는 방법입니다.

재귀

 

스택

 

설명

• 순열 예제는 스택을 사용하여 모든 가능한 순서를 생성합니다. 각 단계에서 선택된 요소를 제외한 나머지 요소들로 새로운 상태를 생성하여 스택에 추가합니다.
• 조합 예제는 스택을 사용하여 선택된 요소의 개수가 k에 도달할 때까지 새로운 요소를 추가합니다. 시작 인덱스를 이용해 중복을 피합니다.
• 부분 집합 예제는 각 요소를 기존 부분 집합에 추가하여 새로운 부분 집합을 생성합니다. 결과 리스트에 모든 부분 집합을 유지합니다.

요약

• 완전 탐색은 가능한 모든 경우를 탐색하여 해를 찾는 알고리즘 기법입니다.
• 모든 경우를 탐색하기 때문에 해를 보장하지만, 경우의 수가 많아지면 비효율적일 수 있습니다.
• 다양한 구현 방법이 있으며, 문제의 특성과 크기에 따라 적절히 선택하여 사용해야 합니다.

완전 탐색 실습

문제 1: 배열의 모든 부분 집합 찾기

주어진 배열의 모든 부분 집합을 출력하세요. 예를 들어, 배열 [1, 2, 3]이 주어지면, 가능한 모든 부분 집합을 출력해야 합니다.