일이 있어서 교육용으로 만든 알고리즘 문제 세트가 꽤나 좋은 세트 같아서 퍼블릭하게 공개하고 싶어졌습니다. 같이 문제를 만든 사람은, kajebiiiKENNYSOFT 입니다. 


문제들의 난이도는 KOI 중등부 1번 ~ 고등부 3번 정도인 것 같습니다. 문제들이 꽤 넓은 분야를 다루고 있으니 문제를 풀고 풀이를 들으면 실력이 오르는 세트라고 생각합니다.


문제들은 잘 알려진 문제들도 있고, 만든 문제들도 있으며 다른 곳에서 가져오거나 변형한 문제들도 있습니다. 블로그에 문제와 풀이를 계속 올릴 생각입니다. Logical Thinking은 일이 바빠서 잘 안 올리고 있네요...

혹시 문제가 지금 궁금하고 풀어보실 생각이 있거나 관심이 있으시면 이 게시글에 비밀 덧글로 이메일 주소를 달아주시거나 이메일 sakura★kyouko.moe 로 (★=@) 메일을 보내주시기 바랍니다.




문제는 계속 추가 되고 있습니다. 앞으로 10문제 쯤 더 추가 될 예정입니다. 현재 문제들의 목록은 다음과 같습니다. :


이 문서는, acmicpc.net 15328번 산타의 선물 문제를 만들게 된 계기, 풀이 그리고 테스트 데이터를 만든 방법에 대해 설명합니다. 문제 스포일러를 원치 않는 분은 읽지 않아주셨으면 합니다.




문제를 단순화 하면 다음과 같습니다.인지 아닌지 판단하세요.


이 문제를 만들게 된 계기는 어떤 트윗에서 시작합니다.

UCPC 2016 D번문제인 Flowey's Love입니다. 입력과 출력이 전부다 정수이지만, 실수오차에 매우 민감한 가혹한 문제입니다. 사실 데이터가 충분히 강한지도 의문입니다. 왜냐하면 이 문제는 유리수, 혹은 제곱근, 혹은 그 수의 제곱근등등을 대소비교를 해야하는 문제이고, 이 문제가 다항시간 안에 풀리는지 안 풀리는지는 현재도 아직 결론이 나지 않은 문제입니다.

뭐 결론적으로 말해서, 컴퓨터에서 지원하는 double 자료형은 오차가 있기 때문에 사용을 해서는 안됩니다. 한가지 예로는 double을 사용한 sqrt에서는

sqrt(6222) + sqrt(8801) + sqrt(14431) + sqrt(8132): 383.00000000000006

이지만, 실제로는



입니다. double을 사용하면 383보다 크다고 나오지만, 실제로는 작죠.


여담으로, a, b, c, d가 모두 제곱수가 아닌 경우에는 등호가 성립하지 않습니다. 숫자가 4개가 아니라 임의의 갯수여도 성립합니다. 다음 논문을 참조하면 좋을 것 같습니다. http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/INCOMING/reu_paper.pdf


뭐 결국에는, 문제는 실수 오차입니다. 실수 오차에 대해서 깊은 설명은 하지 않겠지만, double자료형의 경우에는 2-53, long double자료형의 경우에는 2-64만큼의 오차가 계산할 때 생길 수 있습니다. 이 문제를 풀기 위해서는 충분하지 못한 정확도 입니다.


사람들이 실수 오차에 대해 좀 더 유의해줬으면 바라고, 문제를 내는 사람들이 실수에 대해 좀 더 관대한 생각을 가지기를 그리고 사람들이 고통받는것을 보기 위해 이 문제를 내었습니다.




이 문제에 대한 제 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
typedef __float128 real_t;

__float128 mysqrt(__float128 x)
{
if(x==0) return 0;
__float128 y = 1, gy = 0;
do
{
__float128 t = (y+(x/y))/2;
gy = y;
y = t;
}while(y!=gy);
return y;
}


int main()
{
int N; scanf("%d", &N);
for(int i=0; i<N; ++i)
{
int px = 0, py = 0, pz = 0;
real_t ans = 0;
int x; scanf("%d", &x);
for(int j=0; j<4; ++j)
{
int a, b, c; scanf("%d%d%d",&a,&b,&c);
ans += mysqrt(real_t((px-a)*(px-a)+(py-b)*(py-b)+(pz-c)*(pz-c)));
px = a, py = b, pz = c;
}
if(ans <= x) puts("YES");
else puts("NO");
}
return 0;
}

결국에는, __float128자료형을 써서 해결했습니다. 어떻게 __float128을 사용하면 충분한 정확도를 가지냐 라는것을 확인했냐고요? 왜냐하면, 이 문제를 만들 때에 모든 가능한 입력에 대해서 확인을 해 보았습니다.

0부터 40000까지의 제곱수 세개의 합으로 표현 가능한 숫자는 58000개 정도가 나옵니다. 여기서 4SUM 문제를 풀고 (4SUM문제는 N^2 lgN의 시간복잡도를 가집니다.)  오차가 일정 범위안에 있는 수들을 다 뽑아내었습니다. 램은 26GB, CPU시간은 2.8GHz 프로세서에서 18분이 걸렸고, 숫자들의 후보를 모은 파일은 60GB였습니다.

여기서 오차가 매우 작은 숫자들을 추려내고 추려내서 숫자들을 뽑아내고, 그리고 그 데이터를 가지고 절댓값이 100 이하가 되게 넣을 수 있는지를 이리저리 계산을 했습니다. 그래서 데이터 파일들을 만들었습니다.


사용된 데이터 중 하나는,

2
583
-9 -5 0
-97 -21 -16
22 -100 95
-100 98 -96
747
-42 -30 -2
-98 -93 74
97 57 -66
-98 -98 99

이고,



의 결과를 얻었습니다.


참고로 이 문제는, 제곱을 열심히 반복하면 정수만 사용해서 문제를 풀 수 있다고 합니다. minimal polynomial이 16차이고, 이걸 구해서 대소비교를 하는 방법으로도 해결을 할 수는 있습니다.



기프티콘을 받으신 모든 분들 축하합니다! 그리고 기프티콘을 받지 못하신 분도 이런 재미있는 문제가 있으면 제가 다시 기프티콘을 들고 오도록 하겠으니 풀어주셨으면 합니다. 감사합니다.





* 아래의 내용은 개인의 의견일 뿐 전문가의 의견이 아니며 어떤 특정한 단체의 의견을 대변하지 않습니다.


자기비하란, 스스로를 낮춰서 평가하고 말하는 것을 말한다. 자기비하를 하는 데에는 문화적인 요인, 정신적인 요인, 박탈감 등이 있을 수 있을 수 있다. 하나하나씩 짚어보고 넘어가자면...


문화적인 요인에는 특히 유교 문화권에서는 겸손이 미덕이라는 말이 있다. 한국에서는 "벼는 익을수록 고개를 숙인다." 같은 속담도 있다. 그 중 겸손하기 위한 방법이 상대를 높이기 위해 자기 자신을 낮추는 경향이 있는 문화가 존재하기도 한다. 이런 문화적인 상황에 있으면 과도한 겸손으로 자기비하를 할 수 있다.

정신적인 요인에는 우울증등을 포함한 자기 자신에 대한 비관적인 생각때문에 자기비하를 할 수 있다.

박탈감에는, 자기 자신과 비교해서 상대적으로 특정한 일을 잘 하는 상대를 보고, 내가 그 일을 못한다고 생각하는 것이다.


내가 자기비하에 대해 가진 생각들을 몇 개 적어보도록 하겠다.



[그림 1] 더닝-크루거 효과

사실 사람들이 자기비하를 하는 합리적인 이유는 굉장히 많다고 생각한다. 그 (결과?)중 하나는 더닝-크루거 효과라고 생각한다. 이 더닝-크루거 효과는 말하자면, 능력이 없는 사람이 다음의 경향을 보이는 것을 말한다. [출처는 링크 참조]

  • 자신의 능력을 과대평가한다.

  • 다른 사람의 진정한 능력을 알아보지 못한다.

  • 자신의 능력이 부족하기 때문에 생긴 곤경을 알아보지 못한다.

  • 훈련을 통해 능력이 매우 나아지고 난 후에야, 이전의 능력 부족을 알아보고 인정한다.

이 과대평가라는 것은, 정도가 굉장히 심해서 평균 상위 90% 정도의 사람이 자신을 평균 상위 40%에 있다고 까지 생각한다.

사실 이 현상은 능력이 있는 사람에게도 비슷하게 나타난다. 자신의 능력을 과소평가하는 방향으로 나타난다. 그렇기 때문에, 그들은 자신이 굉장히 못한다고 판단한다. 물론 상위 90% 정도의 사람이 자신을 상위 40%라고 생각한다면, 당연히 그 반대도 있을 것이다.


내가 나에게 느낀 이유는, 내가 올라오려고 노력했기 때문이라고 생각한다. 사실 잘 하는 사람들은 자신의 아래를 유의 깊게 보지 못한 사람이기도 하다. 왜냐하면 그들은 올라오기 위해 계속 위를 보아 왔기 때문이다. 상위 5%의 사람은 자신의 시각으로는 상위 10% 정도의 사람까지 밖에 보이지 않기 때문에 그들이 보는 곳에서 자신은 절반정도의 위치이다. 사실 내가 바라보고 있던 곳은 굉장히 높은 곳이기 때문에, 그 곳까지 올라가기 위해서는 더더욱 그 곳만을 볼 수 밖에 없고, 자기비하는 점점 더 심해져 간다.


다른 사람보다 자기 자신이 해놓은게 별로 없다고 느껴지는 이유에 대해 내가 느낀 것을 나름대로 간단히 설명하자면 "모든게 다 나를 기준으로 하기" 때문이다. 모두가 "어렵다" 라고 느끼는 것을 내가 "쉽다"라고 느끼면, 그것은 나의 적성이지 일이 쉬운 것이 아니다. "나에게 쉬운것은 쉽고, 어려운 것은 어려운 것" 이라는 잣대를 가져다 대면, 나의 적성은 그냥 당연한것이라고 여겨져 버리고, 다른 사람이 잘 하는 것은 그 사람의 천성이라고 생각해 버린다.




사실 이 이유는, 굉장히 안타까운 이유이기도 하다. 왜냐하면 그들은 정말 자신이 그렇게 생각하는 경향을 가지기 때문이다. 하지만 자신이 객관적으로 평가하는 자신의 실력과 사람들 앞에서 말하는 자신의 실력이 다른 경우도 있다. 이게 내가 말하고 싶은 두 번째 이유이다.


놀라운 표를 하나 본 적이 있다. 표의 원본은 기억나지 않으므로 생각이 나는 대로 다시 만들어보면... 


[그림 2] 우리가 어떤 것에 대해 모른다고 말해야 하는 이유



와 비슷했다.


이것이 주는 답은 의외로 간단하다.  "자기가 모른다고 말하면 상처를 받지 않는다." 이다. 자기비하는 다른 사람으로 하여금, 그 주제에 대해 자기가 인지하고 있다는 것을 알고 먼저 할 말이 없게 만든다. 이것은 자기가 상처를 받는게 두려워서 자기가 못한다고 말한 것이기 때문에, 정말 그 사람 보고 못한다고 말하면 화를 낼 수 도 있다. 그리고 이것은 사실 사람을 대할 때 굉장히 화나게 만드는 이유이기도 하다. 만약 내가 대하는 사람이 나보다 실력이 좋은 사람인데 그 사람이 자기 자신을 못한다고 말하는 것은, 나에게도 심각한 박탈감을 줄 수 있다. 

또한, 이것은 객관적으로 그 사람의 실력이 필요할 때 걸림돌이 되기도 한다. 만약에 정말 공동체에 기여할 생각이 있다면, 자신의 정보에 대해서 최대한 잘 전달하려고 노력해야 하지 않을까?




결론적으로 겸손은 굉장히 중요한 것이지만, 그것을 넘어서서 사람들은 여러 이유로 자기비하를 하고 가끔 이것이 문제가 되기도 한다. 자신의 실력을 객관적으로 알 수 있는 기회가 많은 경우에는, 그것을 측정하고 확인하고, 객관적으로 바라봤으면 좋겠다. 자신의 적성을 보고, 자기 자신을 사랑하고, 자기 자신을 자랑했으면 좋겠다고 생각한다. 물론 이것은 글을 쓴 나 자신에게 가장 해 주고 싶은 말이기도 하다.


'생각들' 카테고리의 다른 글

동아리 하제  (0) 2018.08.27
교수님과 상담을 하고 왔습니다  (0) 2018.07.11
2018년 가을 5학기 수강신청  (0) 2018.07.09
기말고사 안 갔다.  (0) 2017.12.12
자취에 대해서  (0) 2017.11.22
기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다. 기말고사 안 갔다.

'생각들' 카테고리의 다른 글

동아리 하제  (0) 2018.08.27
교수님과 상담을 하고 왔습니다  (0) 2018.07.11
2018년 가을 5학기 수강신청  (0) 2018.07.09
자기비하에 내가 느낀 점에 대해  (0) 2017.12.16
자취에 대해서  (0) 2017.11.22

시간복잡도(Time complexity)는 어떤 프로그램이 수행하는데 걸리는 시간을 말한다. 프로그램이 빨리 실행 될 수록 이로운 점이 많기 때문에, 우리는 시간복잡도를 줄이려고 노력한다. 프로그램이 수행하는데 걸리는 시간과 시간복잡도에 대해 알아보자. 참고로 이 글에는 이해하기 어려울 수 있는 수학적인/공학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다.


프로그램의 실행 시간

최신 프로세서 들은 어느정도의 연산을 할 수 있을까? 필자가 쓰고 있는 컴퓨터의 CPU는 Intel(R) Core(TM) i7-7700HQ @ 2.80GHz 이다. 여기서 2.80GHz라는 의미는, 1초에 28억번 "클럭"을 돌릴 수 있다는 것이다. CPU는 기본적으로 하나의 클럭에 한 가지 연산을 처리한다. 쉽게 말하면, 내 CPU는 1초에 28억번 연산을 할 수 있다는 뜻이다. 물론 실제로는 그렇지 않고, 파이프라이닝이라는 것을 한다.


[그림 1] (a)는 일을 순차적으로 처리한다. (b)는 파이프라인을 통해 동시에 처리한다.


쉽게 말해서, 동시에 진행할 수 있는 일 들을 동시에 진행하는 것이다. 우리가 어떤 두 수를 더하기 위해서는, 그 두 수를 본 다음에 계산을 하고, 결과를 어딘가에 작성해야 한다. 그래서 우리가 더해야 할 두 수가 많으면, 속도를 올리기 위해서 "두 수를 보는 것", "계산 하는 것", "결과를 작성하는 것"의 세 단계로 나눠서 일을 수행하게 되고 결과를 작성하면서 두 수를 보고, 계산을 하게 된다. CPU 내에서도 이런 작업이 일어나게 된다. 이것을 "파이프라이닝"이라고 한다. 최신 CPU의 파이프라인은 13~30단계 정도이고, 하나의 파이프라인이 기본적으로 하나의 일을 하는데 걸리는 시간은 1클럭이다. 모든 연산이 모든 파이프라인을 거치는 것은 아니며, 여기서 연산들의 속도차이가 생긴다.

결론적으로 말해서, 연산 하나의 연산시간을 측정하는 것은 의미가 없고, 그 연산의 "평균적인" 연산시간을 측정하는 것이 전체 실행시간을 판단하는 데에 도움을 준다. 간단한 연산인 64bit수의 덧셈, 뺄셈 같은 것은 1클럭 정도가, 곱셈 등은 3클럭, 메모리 접근은 4~300클락, 나눗셈은 80~100 클락 정도가 걸린다. 자세한 내용은 http://www.7-cpu.com/ 등의 사이트를 참조하면 좋다.

뭐 결론적으로, 우리는 가벼운 연산들을 30억번 정도, 무거운 연산들을 1억번 정도 할 수 있다고 생각하면 된다.


큰 수에서의 프로그램의 실행 시간

다음 두 함수를 생각하자. 이 두 함수는 같은 입력에 대해 같은 결과가 나온다. 이 두 프로그램의 차이가 뭔지 살펴보자.

unsigned func1(unsigned n)
{
int sum = 0;
for(int i=0; i<=n; ++i) sum += i;
return sum;
}

unsigned func2(unsigned n)
{
return (unsigned long) n * (n-1) / 2 + n;
}

위의 프로그램은 덧셈, 비교라는 가벼운 연산으로 이루어져 있어서, 연산 하나하나의 실행속도가 빠르다, 반면 아래의 프로그램은 곱셈과 나눗셈(사실 대부분의 컴파일러는 나눗셈을 최적화 해준다.) 으로 이루어져 있어서, 연산 하나하나의 실행속도가 느리다. 우리는 대략, 위의 프로그램이 기본 2클락에, 숫자를 한번 더 할 때 3클락 정도가 걸린다고 생각할 수 있다. 그리고, 아래의 프로그램은 입력에 관계 없이 100클락 정도가 필요하다는 것을 알 수 있다. 결론적으로, 우리는 실행시간을 n에 대한 함수로 나타낼 수 있다. 첫번째 함수의 실행시간은 T(n) = 3n+2일 것이고, 두번째 함수의 실행시간은 T(n) = 100일 것이다.


만약 우리가 쓰는 n의 범위가 0에서 10정도라면, 우리는 func1(n)을 사용할 것이다. 왜냐하면 func1은 2~32클락이 필요할 것이고, func2는 100클락이 필요할 것이기 때문이다. 하지만 만약 우리가 프로그램이 임의의 큰 n에 대해서 빠르게 돌기를 원한다면, n이 33을 넘은 시점부터는 func2가 더 빠르기 때문에, func2를 써야한다.


우리는 대부분 프로그램이 큰 입력에 대해서도 빠르게 실행되기를 원하기 때문에, func2를 사용할 것이고, 여기서 우리가 관심이 있는것은 n에 대해서 얼마나 프로그램의 실행시간이 커지는지에 대해서이다. 우리는 프로그램의 시간을 big-O 표기법으로 표현할 것이다. 이 표기법은 가장 시간이 오래 걸리는 부분에 대해서만 관심을 가진다. 첫번째 함수의 경우 T(n) = 3n + 2에서, 3n은 2보다 충분히 빠르게 커지기 때문에, 2를 무시하고 3n만 남길 수 있다. 그리고 커지는 정도에서 우리는 3이라는 숫자에 관심을 가지지 않는다. 왜냐하면, 이 숫자가 얼마나 크든 작든, 큰 수에서의 대소관계가 변하지 않기 때문이다. T(n) = an인 알고리즘과, T(n) = bn2인 알고리즘이 있으면, a와 b가 얼마나 크든 충분히 큰 n (>a/b)에 대해서, 앞의 알고리즘이 유리할 것이기 때문이다. 그래서 우리는 T(n) = 3n+2에서, 의미있는 부분인 n만 가져와서, O(n)이라고 부른다. T(n) = 100일 경우에는, O(1) 알고리즘이 되는 것이고,  T(n) = 0.00001n4+8n+92312312 같은 경우에는, O(n4) 알고리즘이 되는 것이다. (좀 더 자세히 말해서, f(n) = O(g(n)) 이라고 부르는 것은, 일 때 이다.)


우리가 충분히 큰 입력에 대해서 빠르게 실행되는 것에 관심을 가지는 이유는 여러가지가 있지만, 시간을 상수배만큼 줄이는것보다, n에 관한 식으로 줄이는게 좀 더 효율적이기 때문인 것이 크다.




최근에 바빠서 글을 못 남기는것 같아서, 짧게 짧게라도 글을 올리는게 낫겠다고 느껴서 간단하게 올렸다. 다음 포스트에서는 시간복잡도 분석에 대해서 써 볼것이다. 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.




이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8

32bit의 (부호 없는)숫자가 할 수 있는 것을 생각해 보자. 하나는 0부터 4294967295까지의 수를 표현할 수 있다. 이것은 32비트 자료형 정수(int32_t)가 할 수 있는 일이다. 또 다른 일은 0부터 31까지의 숫자로 이루어진 "집합"을 표현할 수 있다는 것이다. 우리는 이 숫자를 집합으로 사용하는 것에 대해서 고찰해 보려고 한다.



집합의 비트 표기 방법


우리는 어떤 수를 이진수로 표현할 수 있다. 그러면, 20, 21, ..., 2n자리에 각각 0이나 1이라는 수가 있을 것이다. 2n의 자리가 1이면, n이라는 원소가 있는것이고, 만약 아니면 없는 것이다. 예를들면, 9는, 2진수로 표현하면 1001이고, 이것은 {0, 3}이라는 집합을 나타내는 것이다. 이 방법을 쓰면, 32비트 자료형 정수를, {0, 1, ..., 31}의 부분집합에 하나씩 대응 시킬 수 있다.




비트연산과 집합연산 표기


집합에서 가장 기본적인 연산은, 합집합, 교집합, 차집합, 여집합 등등일 것이다. 우리는 합집합, 교집합, 여집합이 각각 | (bitwise-or, 둘 중 하나라도 1이면, 결과도 1이다.), & (bitwise-and, 둘 다 1인 경우에만, 결과가 1이다.), ~ (bitwise-not, 결과의 0, 1이 바뀐다.) 로 표현됨을 알 수 있다. 


그리고 어떤 숫자 n만 들어있는 집합은, 2n이 {n}에 대응되고, <<연산으로 만들 수 있다.


우리는 이것들을 조합해서여러가지의 결과들을 정리할 수 있다. (집합 A는 비트 a에 대응된다.)




이렇게 숫자를 비트로 표시하면 빠른 속도로 다양하게 사용할 수 있는 여러 특징들을 가진다. 예를들면, 어떤 배열의 모든 subset에 대해 연산을 하는 방법은 다음과 같다.


for(int i=0; i<(1<<n); ++i)

{

for(int j=0; j<n; ++j)

{

printf("{");

if(i&(1<<j))

printf("%d, ", j);

printf("}\n");

}

}

위 코드는, 모든 {0, 1, ..., n-1} 부분집합을 전부다 출력하는 코드이다. printf를 바꿔서, 추가적인 연산을 할 수 있도록 바꿀 수 있다.




그리고 여러가지 bit manipulation들이 있다. 비트연산을 가지고 재미있는 일들을 할 수 있다. 가장 마지막 비트를 뽑아내는 연산, 모든 크기 x인 집합들을 순회하는 방법 등등 여러가지 manipluation이 있다. 재밌는 hack들이 있는 링크와 자주 쓰는 핵들을 몇개 소개하고 글을 마치겠다.


//x의 가장 마지막 비트를 계산함

x&-x;


//v랑 크기가 같고, 사전순으로 다음에 오는 집합을 찾음

unsigned int t = (v | (v - 1)) + 1; w = t | ((((t & -t) / (v & -v)) >> 1) - 1);


//x의 모든 부분집합을 순회함.

for(int i=0; i=(i-x)&x; )


//x의 모든 부분집합을 역순으로 순회함

for(int i=x; i>0; i=(i-1)&x)


//gcc내장함수 이용, x에 있는 비트의 갯수를 반환함

__builtin_popcount(x); //x가 long long type이면 __builtin_popcountll(x);


//gcc내장함수 이용, x의 앞에 있는 0의 갯수를 셈 (x의 가장 큰 원소 = log2(x) = 31-clz(x))

__builtin_clz(x);


//gcc내장함수 이용, x의 뒤에 있는 0의 갯수를 셈 (x의 가장 작은 원소를 가져 옴, x&-x는 1<<__builtin_ctz(x)과 같음)

__builtin_ctz(x);

다양한 비트연산에 관련된 것들이 들어 있는 링크: https://graphics.stanford.edu/~seander/bithacks.html


Logical Thinking 게시글의 현재까지의 제목과 게시물 링크를 모아놓고, 새로운 게시글이 생길 때 마다 업데이트 하도록 하겠다.


[Logical Thinking] 1. 수학적 귀납법


[Logical Thinking] 2. 루프 불변조건(Loop-invariant)


[Logical Thinking] 3. 동적 계획법


[Logical Thinking] 4. 시간복잡도

동적 계획법(Dynamic Programming)은 프로그래밍을 할 때 생기는 문제를 작은 문제들로 나눠서 풀고, 그것을 합치는 방법이다. 그 과정에서 이미 풀어봤던 문제가 발생하면, 문제를 다시 풀지 않고, 예전에 풀었던 정보를 가져오는 방법이다. 이것 때문에 분할 정복과는 다른 면이 있다. 글들은 최대한 이해하기 쉽게 작성하려고 했다.


동적 계획법

동적 계획법을 최대한 쉽게 설명해 보려고 노력 했고, 내가 할 수 있는 제일 쉬운 설명을 가져왔다. 숫자를 세어 보도록 하자, 첫번째 줄에는 1이 몇개 있는가?

1 1 1 1 1 1 1 1 1 1

아마 대부분이 세어 보지 않았을 거라고 생각하지만, 1이 10개가 있다. 그러면 여기서 1을 하나 더 그었다고 생각해 보자.

1 1 1 1 1 1 1 1 1 1 1

아래에서는 1이 몇개 있는가? 이것은 아마 이 문장을 보기 전에 답을 알고 있을 것이다. 11개이다. 우리는, 11개라는 답을 얻어낼 때, 처음부터 다시 세어본 것이 아니라 이전에 세었던 결과들을 미리 가져 온 것이다. 이것은 동적 계획법의 기본이 된다. 문제들을 비슷한 문제들로 바꾸고, 똑같은 문제에 대한 답을 미리 기억 해 놓는다.



최장 증가 부분 수열과 최적 부분구조(Optimal Substructure)

그림으로 그린 LIS문제, 3 4 5 6은 증가하는 수열이다.


동적 계획법의 예를 들어 보기 위해서, 우리는 간단한 하나의 문제를 가지고 올 것이다. 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이라는 문제는 굉장히 흔하게 알려진 문제이다.

임의의 수열을 하나 가지고 오자 예를들면 길이 10의 수열 "3 1 4 1 5 9 2 6 5 3"이 있다고 하자. 우리는 이 숫자들을 적당히 차례로 골라서 가장 길고, 증가하는 숫자들을 찾으려고 한다. 예를 들면 "3 1 4 1 5 9 2 6 5 3" 에서 굵게 표시된 "3 4 5 6"은, 증가하는 수열이고 순서를 보존한다. 이것 보다 더 큰 증가하는 부분 수열은 찾을 수 없기 때문에 "3 4 5 6"은 최장 증가 부분 수열이다. 이것이 유일하지는 않다. 예를들면 마지막 숫자만 9로 바꾼 "3 4 5 9"도 최장 증가 부분 수열이다. 하지만, 이 수열들의 길이는 4로 같다. 우리는 이 길이를 구하는 것에 초점을 맞추어 볼 것이다.


우리는 다음의 정리를 증명하려고 한다.


"(길이 2 이상의) i번째 수로 끝나는 증가 부분 수열중 가장 길이가 긴 것은, 1번째 수로 끝나는 증가 부분 수열 중 가장 길이가 긴 것 또는 2번째 수로 끝나는 증가 부분 수열 중 가장 길이가 긴 것 또는 ... i-1번째 수로 끝나는 증가 부분 수열을 포함하고 있다."

라는 것이다. 즉, "최장 증가 부분 수열"은, 더 작은 최장 증가 부분 수열을 포함하고 있다는 뜻이다.


증명은 간단하다. i번째 수로 끝나는 증가 부분 수열에 마지막에서 두번째 원소가 j번째 수라고 하자. (첫번째 원소를 x번째 수라고 해서, 수열을 ax, ..., aj, ai로 나타내자.) 만약, 이 증가 부분 수열이 j번째 수로 끝나는 증가 부분 수열을 포함하고 있지 않다면 우리는 수열의 앞부분을 교체해서 더 길게 만들 수 있고, 우리가 "가장 길다"라고 말한 것에 모순이다. (j번째 수로 끝나는 최장 증가 부분 수열인 (ay, ..., aj)가 (ax, ..., aj)보다 더 길면, (ay, ..., aj, ai)가 (ax, ..., aj, ai) 보다 더 길다.) 그러므로, 본 명제가 증명되었다.


어쨌든 결론은 우리는 최장 증가 부분 수열을 문제를 풀 때, 큰 문제의 답에는 작은 문제의 답이 들어 있다는 것이다. 이것을 최적 부분 구조(Optimal Substructure)라고 말하고, 작은 문제를 풀고 그것을 이용할 수 있다는 것이다. 이것을 토대로 우리는 코드를 짜 볼 수 있다.


// 배열 A가 주어졌을 때, M번째 원소로 끝나는 최장 증가 부분수열의 길이를 구한다.

int solve(int M, const int A[])

{

// 자기 자신이 유일한 최장 증가 부분 수열인 경우

int ans = 0;


// 부분 문제를 답으로 가지고 있다.

// i번째 수열을 사용하려면, A[M]을 덧붙일 수 있어야 한다.

// 그래서 A[i] < A[M]일 경우에만, 문제의 답을 가져온다.

for(int i=0; i<M; ++i)

if(A[i] < A[M])

ans = std::max(ans, solve(i, A) + 1);


return ans;

}


int LIS(int N, const int A[])

{

// 모든 숫자에 대해서, 그 숫자로 끝나는 최장 증가 부분 수열의 길이를 구한다.

// 그 중 최댓값이 전체에서의 최장 증가 부분 수열이다.

int ans = 0;

for(int i=0; i<N; ++i)

ans = std::max(ans, solve(i, A));

 

return ans;

}


부분문제 반복(Overlapping Subproblem)


위의 코드를 실제로 실행 시켜 보면, 굉장히 느릴 것이다. 왜냐하면, 우리는 solve(1, A)를 호출 할 때도, solve(2, A)를 호출할 때에도 계속 solve(0, A)를 호출 할 수 있기 때문이다. 하지만, 우리는 여러번 실행 시켜봐도 답이 변하지 않는다는 사실을 알고 있다. (코드가 어떤 경우에도 결정적이고, 외부에 있는 변수를 바꾸지 않는다.) 그래서 우리는 몇가지 트릭을 써보려고 한다. 만약에 우리가 한번 계산한 값이면, 다시 계산할 필요가 없고, 이 값을 저장시켜 놓는 것이다. 우리는 그 배열의 이름을 dp라고 정할 것이다.: 코드는 다음과 같다.


int *dp;

int solve(const int M, const int A[])

{

// 이미 계산된 값일 경우, 그 값을 그대로 쓴다.

if(dp[M] != -1) return dp[M];

int ans = 0;


// 부분 문제를 답으로 가지고 있다.

for(int i=0; i<N; ++i)

if(A[i] < A[N])

ans = std::max(ans, solve(i, A) + 1);

 

// 계산된 값을 저장해 놓는다.

dp[M] = ans;

return ans;

}


int LIS(const int N, const int A[])

{

// dp배열을 -1로 채운다.

// 여기서 -1은 우리가 아직 계산을 해 보지 않은 값이란 의미이다.

dp = new int[N]; fill(dp, dp+N, -1);


int ans = 0;

for(int i=0; i<N; ++i)

ans = std::max(ans, solve(i, A));

 

delete[] dp;

return ans;

}


이 방법을 쓰면, 우리는 여러번의 같은 코드가 실행되는 상황에서 한번만 그 문제를 계산하고, 나머지는 있는 값을 그대로 가져오는 것으로 풀 수 있다. 즉, 여러번의 문제가 반복되는 상황에서(부분문제 반복) 중복된 계산을 하지 않는다. 이 코드를, solve함수를 명시적으로 만들지 않고, 암시적으로 만들면 다음과 같은 코드가 된다.

int LIS(const int N, const int A[])
{
int* dp = new int[N];

int ans = 0; //LIS 함수에서의 ans 값이다.

for(int i=0; i<N; ++i)

{

dp[i] = 0; //solve 함수에서의 ans 값이다.

for(int j=0; j<i; ++j)

  if(A[j] < A[i])

dp[i] = std::max(dp[i], dp[j] + 1);


ans = std::max(ans, A[i]);

}

delete[] dp;

return ans;

}

우리가 이런 코드를 만들 수 있는 이유는 위에서 solve(i, A)가 계산 될 시점에는, solve(0, A), solve(1, A), ..., solve(i-1, A)가 모두 계산 되어 있기 때문이다. 즉, 우리가 solve의 계산이 수행되는 순서를 알고 있기 때문이다. 그렇기 때문에, dp 배열의 값들을 안전하게 이용할 수 있다.


이 구역에 있는 두가지 코드는 동적 계획법을 계산하는 같은 역할을 하는 서로 다른 코드이다. 두 방법의 장단점이 모두 있으니, 상황에 따라 쓰면 좋다. 첫번째 방법의 좋은 점은, 필요 없는 dp값을 계산하지 않는 다는 점과, solve가 호출되는 순서를 알 필요가 없다는 것이다. 두번째 방법의 좋은 점은, 함수의 오버헤드가 없어서 실행 속도가 굉장히 빠르다는 점이다. 그리고 배열의 식을 그대로 사용하기 때문에 다양한 최적화를 하기 쉽다는 것이다.




동적계획법의 방법과 예제에 대해서 알아 보았다. 이 문제는, 현실의 문제를 푸는데도 굉장히 많이 이용된다. 대부분의 문제가 최적 부분구조와 부분문제 반복이라는 구조를 가지고, 문제를 변형하면 DP를 적용하기 쉬운 형태가 된다. 특히 bit-DP라는 방법이 현실의 문제를 푸는 방법과 많이 유사하다. 다양한 테크닉은 이 글의 범위를 초과하니 따로 포스트를 작성하는 것으로 하겠다. 다음에는 시간복잡도에 대한 포스트를 작성하도록 하겠다. 아래에 풀어볼만한 연습문제를 남겨 놓겠다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다. 참고로 5번 문제는 Fenwick Tree라는 자료구조를 알고 있는 사람이 풀어 보았으면 좋겠다.

 



    1. https://www.acmicpc.net/problem/1463


    2. https://www.acmicpc.net/problem/11726


    3. https://www.acmicpc.net/problem/1932


    4. 그래프 문제중에, "단순 최장 경로"라는 문제가 있다. 이것은, 그래프에서 정점을 중복해서 지나지 않는 최장경로를 찾는 문제다. 이 문제는 정점에 대한 동적 계획법으로 풀리지 않는다. 왜 풀리지 않는가 설명하라.


    5. 그런 반면에, 최단경로를 구하는 문제는 동적 계획법으로 매우 잘 풀린다. (모든 간선의 길이가 양수 일 때) 동적 계획법으로 그래프의 모든 정점쌍간의 최단거리를 구하는 알고리즘을 만들어라.


    6. 가장 마지막의 LIS함수를 Fenwick Tree를 사용하여 O(n log n)으로 최적화 하여라.

     



    이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8

    최근에 소녀전선에서 거지런을 많이 돌다 보니, 쓰기 적당한 거지런 루트가 4개 정도 있는 것 같다. (4-3E, 0-2, 5-2N, 6-3N) 각각 거지런들과 작전보고서를 함께 정리 해 보려고 한다.



    작전보고서

    작전보고서는 한 개를 만드는데에 전지 3개를 소모하며, 하나당 1500개의 경험치를 준다. 10렙, 30렙, 70렙. 90렙, 100렙을 만드는 데에 각각 2, 15, 235, 659, 1088개의 작전보고서가 필요하다. 작전 보고서는 편제 수에 영향을 작지 않으므로, 편제가 작을 수록 (상대적으로) 효과적이며, 나는 작전보고서 15개를 먹여서 3링을 찍은 이후에 시작하는 편이다.



    0-2 거지런


    0-2 거지런은 최종 컨텐츠라고도 알려져 있다. 딜러를 G11/SOPMOD/FAL/HK416 같은 하나 빼고 유탄 계열딜러를 쓰고, 탱커를 M16A1을 써서 도는 거지런이다. 핸드건을 하나 넣어서 딜러의 빠른 딜링을 도와주는게 좋다. 탱커와 딜러를 제외하고 3명의 승객을 태울 수 있다. 수복을 포함하여 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 70/60/36/7이고, 경험치는 588/490 * 2(2.5)이고, 총 경험치는 7840 * 2(2.5) = 15680(19600)이다. 한번 전투 할 때 쓰는 시간은 대략 3분정도이다. 코어벌이도 같이 할 수 있고 자유 경험치도 잘 오르기 때문에 꽤나 선호되는 거지런이다.



    4-3E 거지런


    가장 처음으로 접할 수 있는 4-3E 거지런이다. 딜러를 4링크 혹은 5링크 AR을 두고, 탱커를 5링크 또는 키울 손님을써서 도는 거지런이다. 탱커를 포함하여 4명의 승객을 태울 수 있다. 수복을 포함하여 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 55/48/24/5이고, 경험치는 444/370 * 2(2.5)이고, 총 경험치는 6216 * 2(2.5) = 12432(15540)이다. 75~84렙 까지는 경험치 감소가 있어서, 받는 경험치량이 4972*2.5=12430, 85~94렙까지는 3729*2.5=9323이다. 한번 전투 할 때 쓰는 시간은 대략 2분정도이다. 저렙의 딜러들을 꽤나 빠르게 키울 수 있고, 4링 딜러를 쓸 경우 딜러도 육성을 할 수 있기 때문에 그럴 경우에 가장 효율이 좋은 거지런이다.



    5-2N 거지런


    머신건을 쓰는 야간전 거지런이다, 탱커를 두지 않으며, 딜러를 4링크 MG하나를 두고, 4명의 승객을 태우는 거지런이다. (사실 MG육성도 필요하기 때문에 자기 자신도 태운다고 봐도 된다). 탄통을 이용해서 탄약을 12까지 올려주어야 한다. 탱커가 없기 때문에 수복이 없다. 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 45/46/15/0이고, 경험치는 624(MVP)/576/480 * 2(2.5)이고, 총 경험치는 5280 * 2(2.5) = 10560(13200)이다. 딜러를 빼면 4032*2(2.5) = 8064(10080)이다. 한 번 전투 할 때 쓰는 시간은 대략 1분 정도이다. (전투를 시작하기 전에 제대편성 기능으로 딜러를 바꾸면 좀 더 시간을 단축할 수 있다.) 두번째 전투때 앞열에 있는 인형들을 퇴각해 줘야하고, 5-1N을 뚫고 스토리를 보지 않을면 5-2N을 뚫어야 하는등 여러 준비가 필요하고 꽤나 힘든 점도 많지만, 장비를 얻어서 강화재료로 쓸 수 있다는 좋은 점이 있다.



    6-3N 거지런


    머신건을 쓰는 야간전 거지런이다, 탱커를 두지 않고, 딜러를 5링크 MG하나를 두고, 4명의 승객을 태우는 거지런이다. 탄통을 이용하여 탄약을 11까지 올려주어야 한다. 탱커가 없기 때문에 수복이 없다. 승객이 3-4링일 때, 전투당 쓰는 인탄식부는 대략 50/56/27/0이고, 경험치는 600/500 * 2(2.5)이고, 총 경험치는 4200 * 2(2.5) = 8400(10500)이다. 한 번 전투 할 때 쓰는 시간은 대략 1분 30초 정도이다.  5-2N과 비교해 퇴각컨이 필요 없지만, 한 턴을 더 보내야 한다. 장비를 얻어서 강화재료로 쓸 수 있다. 컨트롤 할 필요가 없다는 점 때문에 선호되는 거지런이다.




    거지런은 결국에는 제일 효율적인 방법을 찾아서 돌게 되는데, 내가 느낀것은 초반에 30렙까지 작전보고서를 먹여서 키운 다음에 0-2거지런과 6-3N거지런을 기본적으로 돌고, 4링 AR을 키울 때는 4-3E, 머신건을 키울 때는 5-2N, 섞어서 키우는게 제일 좋은 것 같다. (폰 성능이 안 좋다 보니 휴대폰으로 할 때는 5-2N대신 6-3N을 선호하는 편이다.) 코어 벌이나 장비 벌이가 필요할 때 마다, 퀘스트가 나올 때 마다 필요한 것을 섞어서 해주면 좋지 않을까 싶다.







    '게임' 카테고리의 다른 글

    BOFXV BMS Package  (0) 2019.11.23
    General BMS Package (64.5GB) (Outdated)  (0) 2019.09.06
    BMS Archive Service  (0) 2019.08.12
    따오콘을 샀습니다.  (0) 2019.07.09
    방어력 감소의 함정  (0) 2019.05.08

    XOR연산(⊕로 많이 표기 된다.)은 논리 이항 연산자이고, 두 입력이 다를 때만 참을 반환하는 연산자이다. 다음 그림은 XOR연산의 진리표이다.

    그리고 이 연산은 Z2(Z/2Z라고도 표기한다)와 깊은 관련이 있다. Z2란, 어떤 정수를 2로 나눈 나머지인 0과 1에만 관심을 가지는 체계를 말한다. 예를 들면, 우리는 X와 Y가 어떤 수이든 관계 없이, X가 짝수이고, Y가 짝수이면 X+Y도 짝수임을 알 수 있다. 이 XOR연산은 Z2에서의 덧셈과 일치한다. 즉 홀짝성이 다른 두 수를 더해야만 홀수가 나온다.

    이 xor을 비트단위로 나눠서 확장한게 bitwise-xor 이고(C, C++, Python 등에서 ^ 연산자로 많이 표기된다.), 이진법으로 표현했을 때의 각 자리마다 비트를 표기한다. 예를들면 1100(2)⊕1010(2)=0110(2) 같이, 1(2)의 자리가 00 = 0이므로 0이고, 10(2)의 자리가 0⊕1=1 인 등등.. 으로 계산한 결과이다. 이 비트단위 xor은 각 자리마다 연산이 보존 되기 때문에 우리는 각 자리를 따로 생각할 수 있고, 결론적으로 bitwise-xor 연산은 Z2n에서의 덧셈이 된다. 그리고 이것을 우리는 스칼라가 Z2이고, 각 벡터가 Z2n인, 벡터 공간으로 생각할 수 있다.


    그래서 우리는 다양한 xor이 연관된 문제들을 벡터 공간으로 바꾸어서 해결 할 수 있다. 예를들면, 숫자들이 여러개 있는데 몇 개를 xor해서 최대가 되게하라는 문제를, 벡터 공간에서 최댓값을 찾아라 같은 문제들로 적당히 바꿀 수 있고, 벡터 공간은 여러가지 좋은 성질들이 많기 때문에 유용하게 사용될 수 있다. 그리고, Row space를 벡터 공간으로 가지는 행렬을 생각할 때 가장 먼저 고려되는 연산인 Reduced Row Echelon Form을 구할 때, 숫자들을 비트단위로 관리할 수 있어, 상수를 크게 줄이는데(32~64배 정도 계산량을 줄일 수 있다.) 도움을 줄 수 있다.


    이 사실로 풀 수 있는 문제를 몇 개 남기려고 한다. 대부분의 문제가 어렵기 때문에, 문제를 해결 할 수 있다면 자신감을 가져도 좋다고 생각한다. 질문이 있으면 덧글로 남겨주면 된다.








    + Recent posts