세미나(3)

완전탐색과 재귀함수

1. 완전탐색

영어로 브루투 포스 혹은 전수조사 라고함.

모든 경우의 수를 확인하는 방법

알고리즘은 아님

- 장점 :상대적으로 구현이 쉽고, 모든 문제에 대한 접근이 가능

- 단점: 모든 경우의 수를 확인해야 하므로 시간이 많이 듦

 

 

1) 사전식 순열 / 중복을 제거한 사전식 순열

- 주어진 숫자들로만들수 있는 모든 사전식 순열 확인하기/ 중복을 제거한 모든 사전식 순열 확인하기

 

2) 백 트래킹

-가지치기를 하면서 문제를 해결하는 알고리즘

 

3) BFS/DFS

- 그래프의 모든 정점을 탐색하는 완전 탐색 알고리즘

 

ex)) 최댓값

9개의 수에 대해 전부 확인하며 최댓값을 갱신해 출력하는 문제

 

ex))문서검색

문서의 모든 인덱스에 대해 확인하는 문제

 

ex)) 일곱 난쟁이

9명중에서 2명을 제거하는 방법으로 푸는 문제

2중 반복문을 이용해 합에서 제외할 2명의 난쟁이를 고르는 모든 경우의 수를 확인하기때문에 완전탐색 문제이다.

 

만약 N명중에서 합이 100이되는 일곱난쟁이 찾아야할경우?

재귀함수를 이용하자

 

---

재귀

- 컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기자신을 재 창조하는것

 

재귀함수

: 자기자신을 호출하여 작업을 수행하는 방식의 함수 ,

 

원리)

재귀함수는 호출될 때마다 스택에 쌓이고, 스택의 가장 위의 함수가 실행완료되면 스택에서 꺼낸다.

다음으로 실행될 수 있는 함수는 스택의

가장 위에있는 함수가 된다.

 

 

 

- 재귀를 두번하는 경우?

첫번째 재귀를 일단 함

0일때))

근데이제 0은 return 이라서 pop

이라 스택에는 1까지 남아있는 상태

두번째 재귀 시작

1/2 는 0이므로 또 스택에 0을 넣음

 

재귀 함수를 구성하는 방법

- 문제를 쪼개는 부분과 기저조건, 두 부분으로 구성

기저 조건이 없으면 (return 하는거) 스택 오버 플로우 발생

 

<예제>

팩토리얼

N! = 1*2*3*4* ....*N

 

(예제)

모든 순열

모든 순열을 구할때 각 자리에 숫자를 채우기 전 현재까지 사용한 숫자들에 대한 정보가 필요

-> 완성된 순열의 정보 저장 ans 배열

-> 현재까지 사용한 숫자들에 대한 정보 저장 visited 배열 (방문배열 ,True/False)

 

디버깅을 해보시라.