#include <iostream>
#include <utility>
#include <map>
#define LL long long
#define P 1000000007LL
using namespace std;
map<pair<LL, LL>, LL> memoization;
LL f(LL, LL);
LL g(int, int, LL);
int main()
{
int T, A, B;
LL C;
cin >> T;
for (int i = 1; i <= T; i++)
{
cin >> A >> B >> C;
cout << "#" << i << " " << g(A, B, C) << endl;
}
return 0;
}
LL f(LL x, LL y)
{
if (x == 0 || y == 0)
return 1;
map<pair<LL, LL>, LL>::iterator iter = memoization.find(make_pair(x, y));
if (iter != memoization.end())
return iter->second;
LL r = (f(x - 1, y) + f(x, y - 1)) % P;
memoization.insert(make_pair(make_pair(x, y), r));
return r;
}
LL g(int A, int B, LL C)
{
LL sum = 0LL;
for (LL x = 0; x <= C / A; x++)
if ((C - A * x) % B == 0)
sum = (sum + f(x, (C - A * x) / B)) % P;
return sum;
}함수 g부분을 보면 내가 처음 짠 코드는 이중 For문이었는데 저기는 if 문을 쫌 늘려서 씀
뭐 for문 도는것보다 계산하는게 더 나으려나 그럼 그걸로 해보겠다
map을 쓰는 이유를 드디어 알았다.. 내가 짠 코드는 2중For문을 돌아야 값을 찾을 수 있었지만 map을 사용하면 Find로 key값을 찾는게 더 쉽기 때문에 map쓰는게 더 좋은듯 근데 이것도 함수를 계속 호출하는 형식이라서
정답 제출하기 전까지는 어케 될지 모르지만..
그래서 우선 코드를 최적화 하는 기법에 대해 잠시 공부해보도록 하겠다..의식의 흐름대로
왜냐하면 코테에서는 나름 시간이 생명인데
어떤걸 사용해야 더 좋은 코드가 될지, 더 빠르게 돌아갈 수 있을지를 선택하는게 중요한 것 같아서
몇가지는 쫌 머리에 넣어두고 있어야 할듯
//06.16
//06.18
map(x,y,sum)이 들어가야하니까
map(pair<ll,ll>,ll>)이 되는거
계속 런타임 에러..
return iter->second부분이 이해가 안간다 ㅠㅠ
06,17
-map사용
Key를 2개 사용하고 싶을 때는 아래처럼 사용하면 된다.
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(void){
map<std::pair<string, string>, int> m;
m.insert(std::make_pair(std::make_pair("hello", "world"), 1));
m.insert(std::make_pair(std::make_pair("hello1", "world"), 2));
m.insert(std::make_pair(std::make_pair("hello2", "world"), 3));
m.insert(std::make_pair(std::make_pair("hello3", "world"), 4));
m.insert(std::make_pair(std::make_pair("hello4", "world"), 5));
m.insert(std::make_pair(std::make_pair("hello5", "world"), 6));
auto iter = m.find(std::make_pair("hello3", "world"));
cout << iter->second << endl;
cout << m[std::make_pair("hello2", "world")] << endl;
return 0;
}
-코드 최적화 기법
-산술/연산 관련
1)부동 소수점 Float, double은 되도록이면 사용하지 말자
=>정수 자료형은 단순이 2진수체계이지만 부동 소수점은 복잡..
2)나눗셈을 피해라
나눗셈은 매우매우 느린 연산이다.
아래는 초를 증가시켜주는 연산
int sec(int second){
return (++second)%60;
}이런 코드의 경우 우리가 second가 60보다 커지지 않는다는 걸 알고있다면
int sec(int second){
++second;
if (second >= 60) return 0;
return second;
}
이렇게 쓰는게 나을수도
근데 이게 좋은 예제는 아닌것 같다..
한 가지 짚고 넘어갈 점은 위 코드에서 분기문 (if) 를 도입하였다는 점입니다. 때로는 분기문이 프로그램 속도를 저하시킬 수 있습니다.
왜냐하면 CPU 의 경우 명령어 실행 속도를 향상시키기 위해 파이프라이닝 이라는 작업을 수행합니다. 쉽게 말하자면, 다음에 실행될 명령어를 이전 명령어 실행이 채 끝나기 전에 미리 실행시키는 것과 비슷하다고 보면 됩니다.
문제는 분기문이 있을 경우 다음에 실행할 명령어가 무엇인지 모른다는 점입니다. 위 경우 second >= 60이면 return 0; 명령을 수행해야 되고 아니면 return second 명령을 수행해야 한다는 점이지요.
그렇다면 CPU 가 second >= 60 이 끝날 때 까지 기다릴까요? 아닙니다. 이전에 추세를 보아서 대충 참일지 거짓일지 예측 한 다음 다음에 올 명령어를 실행하게 됩니다. 이렇게 분기문을 예측하는 것을 분기 예측(branch prediction) 이라 합니다.
예측이 맞았다면 기분좋게 쭉쭉 진행할 수 있었지만, 예측이 틀렷더라면 여태까지 작업한 것을 모두 버리고 원래 수행했어야 할 명령어를 다시 실행해야 합니다. Intel Skylake CPU 의 경우 해당 페널티가 20 cycle 정도 됩니다. 참고로 정수 나눗셈 연산(DIV) 의 경우 10 cycle 정도 필요하고, 덧셈의 경우 1 cycle 에 끝나게 됩니다. (즉 나눗셈이 덧셈 보다 10 배 느립니다.)
따라서 만약에 분기 예측 정확도를 50% 이상으로 할 수 만 있다면 위와 같이 코드를 바꿨을 때 효율적으로 최적화를 했다고 볼 수 있습니다. 다행이도 CPU 의 분기 예측기는 꽤나 똑똑해서, 이전의 분기 결과에 추세 를 바탕으로 예측을 하게 됩니다. 우리의 inc_second 는 대부분의 경우 second >= 60 이 참일 일이 없기 때문에 (확률상 1/60 이다), 분기 예측 확률이 꽤 높을 것입니다.
-나눗셈을 피해라 2
이건 임베디드때 배운건데 2의 멱수의 경우 (2 4 8 16 32 ..) 나눗셈을 할때 나누기 연산말고 시프트 연산 사용하기!!
Ex)32로 나누고 싶으면 i>>5
-loop 관련
1) 알고있는 일반적인 계산 결과를 이용하라
ex) 1부터 n까지 더하는 함수를 만들고자 할때
- for(int i=1;i<=n;i++){
sum+=i;
} 도 있지만
- sum=(n+1)*n/2; 로 간단히 끝낼 수도 있다.
2)끝낼 수 있을 때 끝내라
조건에 맞는 걸 찾았을 때 break;를 걸라는 뜻!
3)한번 돌 때 많이 해라
4) loop에서는 되도록이면 0과 비교해라
1)for (i = 0; i < 10; i++) {
printf("a");
}
2)for (i = 9; i != 0; i--) {
printf("a");
}
둘중 빠른건 2번 코드
=>
일반적으로 0 과 비교하는 명령어는 CPU 에서 따로 만들어져 있기 때문에 더 빠르게 작동될 수 있습니다.
5)당연한거지만 최대한 루프문을 안쓰도록 해라
int i;
for (i = 1; i <= 3; i++) {
func(i);
}보다는
func(1);
func(2);
func(3);처럼 풀어쓰는게 나을지도
그럼 여기서 내가 저 예제에서 궁금했던 궁금증은 해결됨
함수 호출하는게 루프문 쓰는 것보다 낫다!!
우선 좋은 최적화 방법들이 더 많은데 여기까지 해보고 내일 문제를 풀어보도록 하겠다.
씹어먹는 C 언어 - <24. 더 빠르게 실행되는 코드를 위하여 (C 코드 최적화)>
...
modoocode.com