[BOJ] 함수

함수는 컴퓨터에서 아주 중요한 개념입니다. 코드의 재사용을 극대화하는데 필수적이라고 생각합니다. 

 

제가 알고리즘 문제를 처음 풀 때는 함수의 오버헤드 때문에 느려지는 것을 막고 싶어서 직접 인라인을 하고 그랬습니다. 인라인은 따로 코드를 함수에 작성하고 함수를 호출하는 일 없이 함수를 호출하는 부분에 로직을 그대로 작성하는 것을 말합니다. 그런데 사실 이건 어찌 보면 바보 같은 생각일 수도 있습니다. 먼저 재귀 함수와 같이 함수 호출을 엄청 많이 하는 것이 아니라면 성능에 영향을 별로 주지 않습니다. 암달의 법칙 때문입니다.  컴퓨터가 워낙 빠르기 때문에 재귀 함수와 같은 경우를 제외하면 수작업 인라인은 별로 쓸모가 없습니다. 그리고 컴파일러가 자동으로 최적화를 위해 인라인을 해주기도 합니다. 특히 함수의 본체가 짧으면 인라인을 해줄 확률이 매우 높습니다. 함수 호출에 걸리는 시간과 함수 본체의 실행 시간이 버금간다면 더더욱 그렇습니다. 이와 관련해서 gcc 컴파일러에게 인라인을 요청하는 inline이라는 키워드가 있습니다. 그런데 인라인의 여부는 컴파일러의 알고리즘에 의해 최종적으로 결정됩니다.

 

[BOJ 15596]

 

쉬워요.

#include <vector>
long long sum(std::vector<int> &a) {
	long long ans = 0;
    for(const int n : a)
        ans += n;
	return ans;
}

 

[BOJ 4673]

 

d 함수를 함수로 작성해주고 이를 활용해주었습니다.

#include <stdio.h>
#include <vector>

using namespace std;

constexpr int N_FINI = 10000;

int d(int n){
    int ans = n;
    while(n != 0){
        ans += (n % 10);
        n /= 10;
    }
    return ans;
}

int main(){
    vector<bool> d_res(1+N_FINI,false);
    
    for(int n=1;n<N_FINI;++n){
        int d_n = d(n);
        if(d_n <= N_FINI)
            d_res[d_n] = true;
    }
    
    for(int k=1;k<=N_FINI;++k)
        if(!d_res[k])
            printf("%d\n",k);
}

 

[BOJ 1065]

 

두자리수인 경우에는 그냥 참입니다. 10으로 나눈 나머지를 구하는 방식으로 각 자릿수를 구해서 초기항과 공차를 뽑아내고 조건을 검사해주면 됩니다.

#include <stdio.h>

bool isonenumber(int n){
    if(n < 100) return true;
    
    int a = n % 10;
    n /= 10;
    int b = n % 10;
    n /= 10;
    const int d = b - a;
    
    while(n != 0){
        a = b;
        b = a + d;
        if((n % 10) != b) return false;
        n /= 10;
    }
    
    return true;
}

int main(){
    int N;
    scanf("%d",&N);
    int count = 0;
    for(int k=1;k<=N;++k)
        if(isonenumber(k)) count++;
    
    printf("%d\n",count);
}

 

오늘은 짧네요. 수고하셨습니다.