스팟 마트 문제
SW Expert Academy의 8935. 스팟마트 문제를 풀어 제출하였더니 13/15에서 제한 시간 초과가 발생하였다. 며칠간 고민하여 해결하였는데 그 과정에서 알게 된 것을 정리하고자 한다.
시간 초과가 발생한 코드와 pass가 나온 코드의 알고리즘 자체는 큰 차이가 없다. 변경된 것은 sol이라는 재귀함수 내에 result 변수를 지역변수가 아닌 레퍼런스 변수로 선언한 것 뿐이다.
- 시간 초과 발생 코드
if (dp[n][select][skip][get] != -1) return dp[n][select][skip][get];
int result = 0;
...
dp[n][select][skip][get] = result;
return result;- pass 코드
int& result = dp[n][select][skip][get];
if (result != -1) return result;
result = 0;
...
return result;최종적으로 통과할 때 제출한 풀이 및 전체 코드는 다음과 같다. 스팟 마트 문제 풀이
컴파일러 최적화 옵션
컴파일러가 작성된 코드를 분석하여 실행 결과는 동일하지만 메모리 사용이 적고, 실행시간이 빠른 코드로 변형하는 것을 컴파일러 최적화라고 한다. 최적화에는 여러가지 옵션이 있다. 그 중 /O2 옵션은 최대 속도를 위해 코드를 최적화하는 최적화 옵션이다. /O2 옵션 사용시 최적화 과정에서 아래와 같이 레퍼런스 변수를 사용하지 않도록 코드를 변경할 수 있다.
이 경우 변수 사용을 위한 메모리 할당 및 값 복사가 일어나지 않아 성능이 향상될 수 있다.
하지만 int형 변수 하나의 메모리 할당 및 값 복사에 걸리는 시간은 매우 작다. 그리고 SW Expert Academy의 공지에 따르면 별도의 컴파일 옵션을 사용하지 않고, 기본적으로 적용되는 최적화 옵션이 없는 gcc를 컴파일러로 사용하기 때문에 /O2 옵션이 적용되었을 것이라 생각하기는 어려워 보인다.
Cache Hit Rate
캐시에서 값을 참조하는데 걸리는 시간과 메모리에서 참조하는 걸리는 시간은 매우 큰 차이가 있다. 캐시에서 값을 참조하는 것이 훨씬 빠르다.
sol 함수에서 dp에 접근하는 순서를 살펴보면 매우 불규칙적이다. 그리고 dp 배열을 참조한 뒤 한참 뒤 값을 리턴할 때 다시 dp배열을 참조한다. 그 사이 매우 많은 참조가 발생하는 것이다. 이러한 이유로 캐시 hit rate가 낮아져 시간 초과가 발생한 것이다.
result를 레퍼런스 변수로 선언하면 result를 통해 dp에 직접 접근할 수 있다. result는 dp배열 데이터의 별칭이기 때문이다. 따라서 sol 함수에서 result를 사용하면 dp배열을 참조하는 것이 된다. dp배열의 참조 사이에 다른 참조가 적어지므로 캐시 hit rate가 기존의 시간 초과가 발생한 코드보다 더 높을 것으로 예상할 수 있다.
