(자료구조 & 알고리즘 정리) 재귀, 완전탐색, 순열, 조합, 부분집합 정리(2023.06.04)

1. 재귀

---

1) 개념

- 자기 자신을 다시 호출하는 함수

- 스택에 자료구조가 쌓이는 방식과 동일하게 함수가 쌓여 처리됨. 가장 최근에 호출된 함수가 종료조건(return 혹은 함수 흐름 종료)이 충족되면 함수가 종료되며 가장 상단(최근)에 쌓인 함수가 꺼내져 처리되는 방식을 따름.

- 종료 조건 명시 필수. 제대로 명시하지 않을 경우, 함수가 무한히 호출되어 스택 오버플로우 발생될 수 있음.

 

2) 재귀( vs 반복문) 의 장단점

(1) 장점

• 가시성이 높음
• 구현이 쉬움
• 변수를 많이 만들 필요가 없어짐. 

(2) 단점

• 지속적으로 함수를 호출하면서 지역변수, 매개변수, 반환값 모두를 stack에 저장함으로써 선언한 변수만 사용하는 반복문에 비해 메모리를 더 많이 사용. 이는 속도저하로 이어짐. 

 

3) 꼬리재귀

- 스택에 쌓인 함수가 끝나면 돌아갈 위치도 함께 기억함으로써 생기는 성능저하를 줄이기 위한 재귀 방법

- 함수의 return 부분에 재귀함수를 호출 할 때 다른 연산과 함께 쓰지 않고 재귀함수만 호출하기(재귀함수를 호출함과 동시에 이전에 있던 함수 종료 됨) 

- 재귀호출이 끝나면 아무 일도 하지 않고 결과만 반환 가능. 아무것도 하지 않고 각 함수는 값만 전달. => 자기 자리를 기억하고 있을 필요가 없음. 

- 팩토리얼 문제를 통한 일반재귀와 꼬리재귀의 비교

// 일반재귀
int factorial(int n) {
	if(n==1) {
    	return 1; 
     }
     return n * factorial(n-1);
   }
   
   
//꼬리재귀
int factorial(int n, int total){
    if(n === 1){
        return total;
    }
    return factorial(n - 1, n * total);
}

 

 

2. 완전탐색

---

1) 개념

- 가능한 모든 경우의 수를 다 탐색해서 정답(최적의 결과)을 찾는 기법

- 경우의 수가 작을 때 사용.(너무 클 땐 시간초과) 

 

2) 사용 방법

 

(1) 반복, 조건문을 활용해 모두 탐색

 

(2) 순열

 

(3) 재귀 함수 호출

 

(4) 비트마스크

 

- 이진수를 비트 연산을 통해 경우의 수를 줄여가며 탐색하는 방식

- 비트 마스크를 사용하면 하나의 변수에 여러 개의 상태정보 저장 가능 => 복잡한 조건문을 간단히 처리 가능

- 빠르게 계산이 가능해 경우의 수가 많은 경우에 유용함.

 

- 원소가 포함되거나 포함되지 않거나 하는 상황일 때 

- ex) 원소가 n개인 모든 부분집합을 구할 때, 각 원소가 포함되는지 않되는 지를 0과 1로 구분하여 배열에 저장

 

- 비트연산

연산자	설명
&	두 비트 모두 1일 때 1을 반환, 그 외에는 0을 반환
|	두 비트 중 하나라도 1일 때 1을 반환, 둘 다 0일 때 0을 반환
^	두 비트가 서로 다를 때 1을 반환
~	비트를 반전시켜 반환
<<	지정한 수만큼 비트들을 전부 왼쪽으로 이동시킴(빈자리는 0으로 채워짐)
>>	부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴
>>>	지정한 수만큼 비트들을 전부 오른쪽으로 이동시킴(빈자리는 0으로 채워짐)

 

- 예시

• 10 <<2 
  • 00001010 -> 00101000
• 1 << 1    : 많이 사용하게 될 것.
  • 00000001 -> 00000010

 

(5) BFS, DFS 활용

 

 

3) Baby-gin Game으로 살펴보는 완전탐색

- 문제 설명 

• 0~9 사이의 숫자 카드에서 임의의 카드 6장 뽑았을 때, 3장의 카드가 연속적인 번호를 가지면 run, 동일한 번호를 가지면 triplet
• 6장의 카드가 run과 triplet으로만 구성되면 baby-gin
• 6자리의 숫자를 입력받아 baby-gin 여부를 판단하기

- 위 문제를 그리디적으로 접근하고자 정렬을 하면 1,2,3,1,2,3 과 같은 숫자 구성의 경우baby-gin임을 놓칠 수 있음. 완전탐색으로 접근해볼 것.

- 6개의 숫자로 구성할 수 있는 모든 숫자를 나열하고 baby-gin인지 각각 판단하

 

 

 

 

3. 순열

---

1) 개념

- 서로 다른 n 중 r개를 뽑아 일렬로 나열하는 것

- 뽑힌 r개가 서로 구분 됨. 즉, 순서가 의미가 있음

- n개의 요소들에 대해 n!개의 순열 : n<=10일 때 정도만 사용

 

- 순열인지를 확인하려면 뽑은 대상들의 순서가 바뀌었을 때 다른 경우인지를 꼭 체크해보자 ! 

 

2) 구현

(1) 반복문

- n개 중 r개를 뽑을 때, r이 고정적이면 사용 가능

- 중첩 반복문을 활용(r개의 반복문 중첩)

- 중복을 허용하지 않는다면, 앞에서 뽑은 대상을 포함시키지 않도록 if문 적절히 사용할 것

 

(2) 재귀

- r이 가변적인 모든 상황에서의 순열 경우의 수 구하기 구현 가능

- 순열 저장할 배열, n개의 후보에 해당되는 index를 통해 해당 후보 사용 중인지 저장하는 배열(visited) 필요, 현재까지 뽑은 개수 저장할 변수 필요(cnt) ( ==r이면 종료)

 

- 중복 허용하지 않을 때 슈더코드(중복 순열일 때는 visited 불필요)

numbers[]
visited[]
perm(cnt) { 
	if(cnt==r) {
        System.out.print(Arrays.toString(numbers));
        return; //재귀함수 종료
     }
     for i from 1 to n { 
     	if(visited[i] == false){
         numbers[cnt] = i;
         visited[i] = true;
         perm(cnt+1) //재귀
         visited[i] = false; //다 뽑은 후 되돌려놓기
     }
   }

 

 

 

4. 조합

---

1)  개념

- 서로 다른 n개의 원소 중 r개를 순서 없이 고르는 것

- 뽑힌 r개의 순서가 바뀌어도 같은 경우

- nCr = n-1Cr-1 + n-1Cr )(=> 추가된 1개의 원소를 포함하거나 포함하지 않는 경우의 수의 합 = nCr)

 

2) 구현

(1) 반복문

- 순열과 마찬가지로 뽑는 개수인 r이 고정적일 때 사용

 

(2) 재귀

- 뽑는 개수 r이 유동적일 때 구현 가능

input[] //입력으로 n개의 원소 받아 저장, n개의 후보가 되는 대상들이 모인 배열
numbers[] //선택된 값을 저장할 배열

//cnt : 뽑은 개수
//start : 조합을 시도할 시작 인덱스(중복 없을 예정이므로)

comb(cnt, start){
	if(cnt==r){
    return;
    }
    
    for(int i=start; i<n; i++){
    	numbers[cnt] = input[i];
        comb(cnt+1; i+1);
     }
  }

 

 

 

5. 부분집합

---

1) 개념

- 집합에 포함된 원소들 선택

- 원소가 n개인 집합의 부분집합의 개수는 2^n개 (각 원소를 포함하거나 포함하지 않거나) 

- 완전탐색으로 부분집합 문제를 풀기 위해서는, 집합의 모든 부분집합을 생성한 후 전체 생성된 부분집합들을 문제 상황에 적용해 계산해봐야 함.

 

2) 구현

(1) 반복문

- 전체 집합의 원소의 개수만큼 for문을 작성.  for문의 범위 0과 1중 하나( 선택/비선택 중 하나)

 

(2) 재귀

-  순열과 같이 cnt를 매개변수로 갖는 함수 작성

- 단 이 때 cnt는 내가 뽑은 원소의 개수가 아니라 현재까지 고려한 원소의 개수(cnt ==n이면 재귀함수 종료)

- 선택할 경우 선택 처리 하고 cnt + 1로 하여 재귀함수 호출 / 선택하지 않을 경우 미 선택처리 하고 cnt+1를 매개변수로 하여 재귀함수 호출

- 슈더코드

input[] //입력 배열, 원소의 개수 N 
visited[] //부부닙합에 포함/비포함 여부 

subset(cnt) { 
	if(cnt==N) { 
    	//이 때 visited가 true인 index에 해당하는 input의 값이 이번에 완성된 부분집합이 됨.
        //필요 시 출력 또는 계산
    	return;
    }
    
    visited[cnt] = true; //cnt번째 원소를 선택했을 경우
    subset(cnt+1);
    visited[cnt] = false; //cnt번째 원소를 선택하지 않았을 경우
    subset(cnt+1);
 }

 

 

(3) 비트마스크(바이너리 카운팅) 

- 원소의 개수가 N개이면 N개의 비트값을 이용. boolean 값처럼 각 자리의 값이 0이면 미선택, 1이면 선택된 것

- 부분집합을 구하는문제(개수가 정해져 있지 않은 조합에서 이 방법 주로 사용)

 

- 아래는 비슷한 문제라고 하니 풀어볼 것.

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

- 슈더코드

input = [] // 배열 원소의 개수 N 이라 하자
N = len(input)

//1<<N 만큼 for문 반복
//원소의 개수만큼 비트 비교

for (int i=0; i<(1<<N); i++) {
	for(int j=0; j<N; j++){
    	if(i & (1<<j)) {
        	print;
    	}
    }
    
    
}

---