알고리즘 - 재귀함수

백준 알고리즘 문제들 중 재귀함수에 관한 내용을 정리하였다. 재귀를 사용하여 문제를 접근할 때에는, 재귀를 통해 들어가고 빠져나오는 과정을 이해하고 로직을 설계해야 한다. 또한 비트 연산을 통하여 보다 빠르게 문제를 풀어내는 방법을 제시하였다.

재귀함수 사용하기

1,2,3 더하기를 재귀를 사용해서 풀 수 있다.

int go(int count,int sum, int goal {
    if (sum>goal) return 0;
    if (sum==goal) return 1;
    int now = 0;
    for (int i=1;i<=3;i++) {
        now += go(count+1,sum+i,goal);
    }
    return now;
}

암호 만들기(1759번 문제)

사용가능한 알파벳이 6개 a t c i s w 라고 하자

이 중 4개의 문자를 가지고 암호를 만들어야 한다고 한다면,

6*5/2 = 15가지가 아니고, 최소 한개의 모음과 최소 2개의 자음으로 이루어져야 하므로 14개가 나타나게 된다.

접근법

먼저 알파벳을 증가하는 순서로 만들어 놓는다

암호를 만드는 방법은 어떤 알파벳을 선택할지 말지 로 구분되게 되며, 이렇게 쭉쭉 나아가다가 길이가 정해진 길이가 되면 멈추게 된다. 물론 그때 유효성 검사(최소 한개의 모음과 최소 두개의 자음으로 이루어져 있는가)도 해주게 된다. 만약 모두 맞다면 결과를 출력해주게 된다.

코드는 다음과 같다

void go(int n,vector<char> &alpha,string password,int i) {
    if(password.length()==n) {
    	if(check(password)) {
            printf("%s\n",password);
        }
    }
    if(i>=alpha.size()) return ;
    go(n,alpha,password+alpha[i],i+1);
    go(n,alpha,password+alpha[i],i);
}

bool check(string &password) {
    int ja=0,mo=0;
    for (char x : password) {
        if(x==('a' || 'e' || 'i' || 'o' || 'u')) mo+=1;
        else ja+=1;
    }
    return ja>=1 && mo>=1;
}

로또(6603번 문제)

여기서도 마찬가지로 어떤 숫자를 선택할지 말지를 결정해가며 cnt 가 정해진 길이에 도달하면 끝나게 된다.

이 재귀함수에서 중요한 것은 어떤 재귀를 먼저 돌릴것인지 결정하는 것이다. 모든 숫자들이 정렬되어 있다고 전제하고, 재귀에서 선택하는 것을 먼저 돌리게 되면 오름차순으로(사전순으로) 나타나게 되고, 반대로 하게 되면 사전 순서가 아니게 된다.

vector<int> lotto;
void go(vector<int> &a, index i, int cnt) {
    if(cnt == 6) {
        for (int num : lotto) {
            printf("%d ",num)
        }
        printf("\d");
        return;
    }
    if(a.size()==index) return;
    lotto.push_back(a[index]);
    solve(a,index+1,cnt+1);
    lotto.pop_back();
    solve(a,index+1,cnt)
}

부분집합의 합(1182번 문제)

N개의 정수로 이루어진 집합이 있을 때, 공집합이 아닌 부분집합 중에서 그 집합의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다.

접근법

먼저 N개의 정수(A1,A2,A3…)가 있을 때, 집합에 A1 이 포함될수도 있고 아닐수도 있으므로 재귀함수를 통해 푼다

여기서 재귀는 해당 원소를 더해가면서 돌다가, 더한 값이 S가 되면 멈추게 된다. 또한 더한 값이 S를 넘어가게 되면 옳지 않은 연산이다.

재귀 함수 구조

여기서 중요한 것은 재귀 함수를 돌 때 Sum 이 S가 된다고 바로 멈추는 것이 아니라, 모든 N개의 정수를 선택할지 말지를 결정하고 끝나야 한다. 만약 그렇지 않으면 Sum 만 같았다고 뒤의 원소를 고려하지 않고 끝나버리게 된다

1. 정답 찾음 : Sum == S && index == n
2. 불가능한 경우 : index == n && Sum != S (n-1 까지 원소가 있으므로)
3. 다음 재귀 경우 : index 의 원소를 포함하는 경우, 포함하지 않는 경우

여기서 공집합의 경우는 모두 선택하지 않은 경우, 즉 Sum 이 0 이 되는 경우이다. 따라서 공집합을 제외하려면 0 이 나왔을 때, 전체 카운트에서 하나를 빼주면 된다.

퇴사(14501번 문제)

위의 문제를 보면 4일째에 가장 큰 돈을 벌수있는 상담이 있지만 선택할 수 없다. 퇴사가 6일째에 있기 때문이다.

이 문제는 재귀함수로 앞에서부터 시작하여 상담을 선택할지 말지를 고르게 된다. 또한 모든 골라진 경우의 수들 중 가장 돈을 많이 번 경우를 선택하게 된다.

여기서 재귀를 돌 때 주의할 점은, 골라진 상담이 걸리는 일수만큼 index 를 증가시켜서 날짜를 뛰어넘은 다음 재귀를 돌아야 한다.

재귀 함수의 구조

마지막 일을 할수 있는 날이 n 이라 할때

1. 불가능한 경우 : day > n+1
2. 정답인 경우 : day == n+1
3. 다음 경우 : 상담을 하는경우, 상담을 하지 않는 경우

연산자 끼워넣기(14888번 문제)

N개의 수와 N-1 개의 연산자가 있을 때 수식의 최대값과 최소값을 구하는 문제이다. (수식의 연산자 우선순위를 무시한다)

접근법

먼저 여기서는 숫자와 숫자 사이에 연산자(4개) 를

재귀 함수의 구조

1. 정답인 경우 : index = 입력으로 수어진 수들의 크기 -1
2. 불가능한 경우 : 사용할 수 있는 연산자의 개수가 0보다 작아진 경우
3. 다음 경우 : +를 사용한 경우, -를 사용한 경우, * 를 사용한 경우, /를 사용한 경우

이 문제는 최소값과 최대값을 모두 리턴해야 하기 때문에, 재귀함수에 들어갔을때 리턴값을 pair<int,int> 로 해주면 한번에 리턴이 가능하다. auto 자료형이란 초기화하는 값에 따라서 자료형이 정해지는 편리한 자료형이다(몰랐음;;)

연산자 끼워넣기(2) (15658번 문제)

다른건 위의 것과 똑같은데, 연산자의 개수가 N-1개 이상으로 주어진다.

따라서 위의 문제와 달라지는 부분은, 코드상으로 없다.

왜냐면 연산자를 선택할 때 남은 연산자의 개수가 N-1 이상인지 아닌지 고려하지 않았기 때문이다. 결국 위의 문제와 풀이가 정확하게 같다

—

비트마스크

비트 연산에서 주의해야할 점은 not 연산이다.

A = 83 = 1010011 인데 ~A = 10101100 이다(8비트의 자료형인 경우 모든 자리수의 0과 1을 반대로 작성해 준다)

이 결과 값은 signed 인 경우 2의 보수법 표현에 의해 -84가 된다 (부호를 바꾸고 1을 빼준 값) unsigned 인 경우 4+8+32+128 = 172 가 된다.(그대로 2진수로 계산해 준 값)

또다른 주의해야할 비트 연산으로는 shift left(<<) 와 shift right(>>) 가 있다. A « B (A를 왼쪽으로 B 만큼 민다)

밀어지고 새로 생기는 비트는 0으로 채워진다

비트연산을 쓰는 경우는 a가 1인 경우에 자주 사용된다. 2의 제곱으로 늘어나는 연산에 주로 사용된다.

A » B (A를 오른쪽으로 B만큼 민다)

결론적으로 보자면 비트 연산은 다음과 같은 결과를 나타낸다.

A « B 는 A * 2^B 와 같다.

A » B 는 A / 2^B 와 같다.

(A+B) / 2 는 즉 (A+B) » 1 로 쓸 수 있다.

비트마스크

즉 정수를 보고 어떤 숫자가 포함된 집합을 의미하는 지 알 수 있다.

과연 근데 이렇게 직접 써야 하는가?

1. 배열이 필요 없다. 수로서 표현을 할 수 있다.
2. 배열안에 집합을 포함시키기 편하다.

특징

보통 0~N-1 까지 정수로 이루어진 집합을 나타낼 때 사용하게 된다. 1부터 N까지 정수로 이루어진 집합을 사용하는 건 공간이 2배 더 필요하다. 각종 연산을 조금 변형해서 사용해야 한다. 0~N-1 까지로 변형해서 사용하는 것이 더 좋다.

실제 사용 예시

집합에 원소가 포함되어있는지 보려면 (1<<원소) 를 & 연산해주면 알 수 있다. 결과값으로 0 이 아닌 값이 나온다면 집합에 원소로 존재하는 것을 의미한다.

집합에서 원소를 제거하는 연산은 ~(1<<원소) 를 & 연산해주면 된다. 원리는 같다. 결과값으로 원소를 제거하고 나타내준다.

집합에서 원소를 토글(있는것을 삭제, 없는것을 추가) 하기 위해서는 다음과 같이 (1<<원소) 를 ^ 연산 해주면 된다.

전체집합 표현 : (1«N) -1 (n만큼 0을 만들고 하나를 빼주면 n-1 개의 1이 나타난다) 공집합 : 0

비트 연산을 사용할 때 주의할 점

연산자 우선순위를 항상 생각해야 한다.

ex) 1 « N - 1

의 경우는 N-1 이 먼저 실행된다. 헷갈리니까 괄호를 꼭 쓰자

bitset (암기하기)

C++에서 int 는 32비트, long long 은 64비트 이다. 따라서 64비트가 넘는 수를 정수로 나타낼 수가 없는데(native 하게) 이런 경우 bitset 을 이용한다.

부분집합의 합(1182번 문제)

원소를 포함하는지 아닌지를 0 과 1로 표현하여 풀어본다. 공집합은 정수로 0 을 나타내므로 1 이상부터 (1«N) 까지의 수들을 모두 구하면 된다.

for(int i=1;i<(1<<n);i++) {
    int sum = 0;
    for(int k=0;i<n;k++) {
        if(i&(1<<k)) {
            sum += k;
        }
    }
    if (sum == s) ct +=1;
}