작성한 질문수 10

0

안녕하세요 ㅎㅎ

void형이 아니라

int형으로 return 하는 부분 말씀 하시는 거죠?

int go(int index, int k, int mask) {
    if (k < 0) return 0;
    if (index == 26) return count(mask); 
    int ret = go(index+1, k-1, mask | (1 << index)); 
    if (index != 'a'-'a' && index != 'n'-'a' && index != 't'-'a' && index != 'i'-'a' && index != 'c'-'a') {
        ret = max(ret, go(index+1, k, mask)); 
    }
    return ret;
}

이 코드를 보면 ret에 max값을 쌓아서 실행하고 있습니다.

이거로 설명하기에는 조금 어렵고 좀 더 쉬운 예제를 제가 들어볼게요.

트리로 되어있는 자료구조(단방향간선만 있음)에서 한 노드에서 탐색을 이어나갈 때 몇개의 정점까지 탐색하게 될까?

라는 로직을 들어볼까요? 이런 그림을 생각해보죠. 자 이걸 void형으로도 풀 수 있습니다.

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 
vector<int> adj[1004];
int cnt;
void dfs(int here){
    cnt++;
    for(int there : adj[here]){
        dfs(there);
    }
}
int main() { 
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[3].push_back(4);
    adj[3].push_back(5);
    dfs(1);
    cout << cnt << '\n';
    return 0;
}

이렇게 하면 1부터 노드를 탐색해서 5를 출력하게 되겠죠?

자 그러면 이걸 int형으로 해볼게요.

저 정점에서 1이라는 값을 부여해서 그 1이라는 값을 누적해서 + 한다라고 생각하시면 됩니다.

이렇게 되는 것입니다. 코드로 나타내면 다음과 같이 됩니다.

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 
vector<int> adj[1004]; 
int dfs(int here){
    int value = 1; 
    for(int there : adj[here]){
        value += dfs(there);
    }
    return value;
}
int main() { 
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[3].push_back(4);
    adj[3].push_back(5); 
    cout << dfs(1) << '\n';
    return 0;
}

int형 dfs : int형인 값을 반환한다.

value : 해당 정점의 값에 1을 생성한다.

+= : 해당 정점에 연결된 노드의 값들을 모두 더한다.

라고 생각하시면 됩니다. 누적해서 쌓아간다 ~ 라고 이해하시면 쉬울 거 같아요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.