혜아의 아무말

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

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

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

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

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

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

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

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

아니... 그... 저..... pic.twitter.com/agXpmPH9r3

— 시프트 / shift* (@shiftpsh) December 27, 2017

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

Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?https://t.co/6KrhmWuhZchttps://t.co/qeQlJKaZFa

— 이혜아 (@mega_kina) December 27, 2017

뭐 결론적으로 말해서, 컴퓨터에서 지원하는 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차이고, 이걸 구해서 대소비교를 하는 방법으로도 해결을 할 수는 있습니다.

sqrt(d)<k-sqrt(a)+sqrt(b)+sqrt(c) 가 되고 제곱하면 xsqrt(ab)+ysqrt(bc)+zsqrt(ca)<뭔가 정수 가 돼서 c 짝수개 있는 거 오른쪽으로 보내고 하면 되지 않을까요

— 서콴 (@sukh1222) December 27, 2017

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

와 비슷했다.

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

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

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