알고리즘 문제풀이 시간 단축을 위한 팁 (1)

photo by Christopher Gower on Unplash

라떼만해도 알고리즘 문제풀이 사이트라고 하면 백준, 알고스팟, 코드잼 같은 사이트 밖에 없었던 것 같은데, 우후죽순 많은 사이트들이 생겼고, 사이트들의 문제를 기반으로 많은 신입/경력 채용이 이루어지는 것 같다.(최근 이직 준비를 하면서 알게됨)

 

블로그에 알고리즘 카테고리를 하나 추가하면서, 중상급 이상의 문제에서 적용할 수 있는 테크닉, 풀이 접근방법 등을 정리해보고자 한다. 문제풀이 초/중급이라면 문제풀이를 할 때 어떤 알고리즘이 가장 최적화된 시간 복잡도로 풀이할 수 있는지 직관을 먼저 기르는 것을 추천한다.

 

* 알고리즘 문제풀이에서만 해당되는 내용이며 실무에서는 정반대의 접근법으로 코드 작성을 해야 할 수도 있다. 이 점을 주의해야 한다.

 

 

Function call 최소화

간단한 코드라면 function call을 최소화한다. 특히 루프 내.

long long sum(long long a, long long b)
{
	return a + b;
}

long long function()
{
	long long ret = 0L;
	for(int i = 0; i < 99999999; i++)
	{
		ret = sum(ret, i);
	}
	return ret;
}

위와 같이 sum 함수를 99999999번 호출하게 되면 콜스텍이 99999999번 호출되는 샘이다.

간단한 식이라면 아래처럼 내부에 풀어쓰는 것이 좋다.

 

long long function()
{
	long long ret = 0L;
	for(int i = 0; i < 99999999; i++)
	{
		ret += i;
	}
	return ret;
}

기준 실행 시간이 1/6~1/3 정도까지 줄어들었다.

 

Inline keyword를 맹신하지 말 것

inline 키워드는 컴파일 옵션에 따라 활성화되기도 하고 무시되기도 한다.

inline long long sum(long long a, long long b)
{
	return a + b;
}

long long function()
{
	long long ret = 0L;
	for(int i = 0; i < 99999999; i++)
	{
		//ret = sum(ret, i); // 컴파일 옵션에 따라 inline 적용이 안됨
		ret += i;
	}
	return ret;
}

자신이 답안을 제출할 서버의 컴파일 옵션 모르거나 마음대로 바꿀 수 있는 것이 아니라면, 간단한 함수를 inline 함수로 빼지 말고 위의 예시처럼 풀어쓰는 것을 추천

 

Register keyword 사용 하기

연속해서 쓰이는 변수라면 register 키워드를 사용하여 레지스터에 값을 상주시키는 것이 좋다. 특히 루프에서 많이 사용한다.

long long function()
{
	register long long ret = 0L;
	for(register int i = 0; i < 99999999; i++)
	{
		ret += i;
	}
	return ret;
}

본인 환경 기준 시간 1/3로 단축

 

 

Bit 연산 활용하기

컴퓨터는 2진수에 강하다. 2진수를 사용하는 연산이라면 비트 연산을 활용하자.

// 벡터의 각원소를 8배로 해주는 함수
// 오버플로는 없다고 가정
vector<int> multiple8(vector<int> nums)
{
	for(int i = 0 ; i < nums.size() ; i++)
	{
		nums[i] = nums[i] * 8;
	}
	return nums;
}

// 벡터의 각원소를 8로 나눈 나머지를 반환하는 함수
vector<int> module8(vector<int> nums)
{
	for(int i = 0 ; i < nums.size() ; i++)
	{
		nums[i] = nums[i] & 8;
	}
	return nums;
}

단순히 수치로 8배를 해주는 것보다 비트 연산으로 쉬프트를 해주는 게 더 빠르다.

// 벡터의 각원소를 8배로 해주는 함수
// 오버플로는 없다고 가정
vector<int> multiple8(vector<int> nums)
{
	for(int i = 0 ; i < nums.size() ; i++)
	{
		nums[i] = nums[i] << 3;
	}
	return nums;
}

// 벡터의 각원소를 8로 나눈 나머지를 반환하는 함수
vector<int> module8(vector<int> nums)
{
	for(int i = 0 ; i < nums.size() ; i++)
	{
		nums[i] = nums[i] & 7;
	}
	return nums;
}

약 2배 빨라졌다.

 

Loop optimization

루프 최적화는 컴파일러에게 맡기지 말고 직접 하자.

// 0 ~ 100*N 까지의 합을 반환해주는 함수
int func(int N)
{
	int sum = 0;
	for(int i = 0 ;i <= N * 100; i++)
	{
		sum += i;
	}
	return sum;
}

아래처럼 최적화 가능

// 0 ~ 100*N 까지의 합을 반환해주는 함수
int func(int N)
{
	int sum = 0;
	N * = 100;
	for(int i = 1 ;i <= N; i++)
	{
		sum += i;
	}
	return sum;
}

 

Loop unrolling

루프 언롤링 이란 공간을 약간 희생시키면서 실행 속도를 최적화하려고 시도하는 방식이다. 이 방식이 가능한 이유는 CPU가 연산하는 방식을 이해해야 하는데, A라는 변수에 A를 쓰기 전까진 A와 관련된 연산은 아무것도 할 수가 없다.(실제로는 연산은 하지만 이후에 값이 버려진다.) 그 공백의 시간(CPU 용어로는 hazard라고 한다)을 최소화시키고자 하는 방법이다.

 

 

예를 들자면 +연산이 3단계에 걸쳐서 일어난다고 가정하자.

sum += i; // 3단계 소요
// 3단계 동안 대기
sum += i; // 3단계 소요
// 3단계 동안 대기
sum += i; // 3단계 소요
// 3단계 동안 대기
sum += i; // 3단계 소요

이렇게 sum에 연속해서 값을 쓴다면 cpu에서는 연산 사이에 공백의 시간이 생긴다.

 

이런 공백의 시간을 최소화하기 위해서 loop unrolling 방식을 활용할 수 있다.

// 0 ~ 9999 까지의 합을 반환해주는 함수
int func()
{
    int a, b, c, d;
    a = b = c = d = 0;
	for(int i = 0 ;i < 10000; i+=4)
	{
		a += i;
		b += i + 1;
		c += i + 2;
		d += i + 3;
	}
	return a + b + c + d;
}

sum이라는 한 가지 변수에 저장하는 것이 아니라 분산된 공간에 저장하고 나중에 합침으로써 공백의 시간을 최소화시킨다.