책 이야기

날짜 : 2024.4.21.

저자: Frans De Waal 저, 이충호 역

출판사 : 세종서적

이미지 : 예스24

정가 : 22,000원

부제를 봐서 알 수 있듯이, 요즘 많이 논의되고 있는 젠더라는 이슈를 영장류를 연구하면서 알게 된 내용 중심으로 정리하고 있는 책이다.

나이가 들어 집중력이 떨어져서인지, 유튜브, OTT 등의 미디어 덕분인지, 저자가 글을 재밌게 쓰지 않아서인지, 책의 주제에 대한 관심이 많지 않아서인지는 몰라도 책이 잘 넘어가지 않아서 생각보다 많은 시간이 소요되었다.

읽기 어려웠지만 저자가 이야기하고자 하는 바는 충분하게 공감되었다. 젠더라는 이슈에서 더 많이 드러났지만, 몇가지 종류의 유인원을 관찰하면서 발견한 사실을 바탕으로 문화라는 이름과 함께 고정관념화 된 여러가지 중 성역할에 대해 문제제기를 하고 있는 것이다.

젠더에 대한 여러 논쟁이 사람뿐만 아니라 동물에 대해서도 견해를 정해놓고 관찰해서 끼워맞춘 것에 가까웠는데 저자는 관찰을 통해 도출되는 결과를 최대한 객관적으로 서술하려고 노력을 한 것으로 느껴졌다.

그리고, 유인원도 성별에 따른 성역할이 기본적으로는 있지만 (암컷이 없는 경우 수컷이 육아를 담당하는 등) 상황에 따라 유연하게 대응하는 이야기를 보면서 우리사회가 성역할에 대한 고정관념으로 각자가 해야하는 역할을 너무 강요하고 있는 것이 아닌가라는 생각이 들었다.

인간과 동물의 차이, 젠더, 문화라는 몇가지 키워드에 대해 또다른 시각으로 생각을 하는 기회가 되었다. 그리고, 침팬지 폴리틱스를 이어서 읽을 예정인데 이 책 보다는 조금 더 재미있게 읽을 수 있으면 좋겠다.

서로 다른 소수인 p와 q로 만들어지는 정수 p^qq^p는 합성 정수(Hybrid Integer)라 부른다.

예를 들어, 800=2⁵5²은 합성 정수이다.

C(n)을 n이하의 합성 정수의 갯수라 정의하자.

C(800)=2이고 C(800⁸⁰⁰)=10790이다.

C(800800⁸⁰⁰⁸⁰⁰)을 구하시오.

--------------------------------------------------------------------------

처음에는 숫자가 너무 커서 다루기 겁이 나서 지나갔던 문제이다. 다른 사람의 접근을 보니 숫자가 너무 크기 때문에 log를 이용하면 해결 가능할 것으로 보였다. 문제에서 요구하는 것은 p^qq^p가 800800⁸⁰⁰⁸⁰⁰ 이하인 경우를 묻고 있으므로 다음과 같이 된다. 그리고 양변에 로그를 씌워 다시 정의하면 아래와 같다.

p^qq^p <= 800800⁸⁰⁰⁸⁰⁰

log(p^qq^p) <= log(800800⁸⁰⁰⁸⁰⁰)

log(p^q)+log(q^p) <= log(800800⁸⁰⁰⁸⁰⁰)

q*log(p)+p*log(q) <= 800800*log(800800)

소수는 2부터 시작하므로 800800*log(800800)을 최대값으로 보고 이보다 크게 되는 q*log2+2*log(q)의 q값을 구해 상한선으로 두고 이중 반복문을 운영하면 답을 구할 수 있다. 파이썬의 배열 한계를 넘어갈 것을 걱정했는데, 다행히 천만~2천만 사이의 어딘가에서 최대값을 넘는 것을 확인하고, 정확한 값을 구할 수 있었지만 안전하게 해서 답을 구하기로 했다.

15분쯤 소요되었으니 빠른 것은 아니지만 문제를 해결했다는 것에 만족하기로 했다.

양의 정수 a,b,c,d가 ab=cd=N이고 a+b=c+d+1인 경우, 양의 정수 N은 은밀하다고(stealthy) 한다.

예를 들어, 36=4x9=6x6은 은밀하다.

10⁶ 이하에는 2851개의 은밀한 숫자(Stealthy Numbers)가 있다.

10¹⁴ 이하에는 몇 개의 은밀한 숫자가 있는가?

--------------------------------------------------------------------------

문제는 그리 까다롭지 않아, 문제에서 요구한 것만 구현하면 코드가 그리 길지 않다. 숫자의 약수를 구해서, 약수가 n개인 경우 n/2개까지 두 숫자를 각각 a, c로 두고, b, d를 연산을 통해 구하고, a+b=c+d+1인 경우를 찾도록 만들었다.

하지만, 예시로 나온 1백만 이하에 몇 개가 있는지 검증하는데 벌써 속도 문제를 만나게 되었다. 문제에서 요구한대로 했을때 구해지는 답을 보고 4의 배수만 나오기 때문에 그것으로 성능을 조금 개선했다. 그래도, 약수를 구하는 부분에서 시간이 많이 소요되어서, 대상 숫자를 보니 전체 약수의 가운데 부근에 있었다. 예를 들어 설명하면 약수가 10개인 경우 4,5번째 숫자 또는 3,4번째 숫자가 a,c가 되는 것이었다. 그렇게 해서 속도를 개선하니 1백만 개 이하의 은밀한 숫자 갯수를 맞게 구할 수 있어서 문제에서 요구한 대로 구현했음을 알 수 있었다.

하지만, 1백만 개에 9초의 시간이 필요했으면, 문제에서 요구한 1경 개를 대상으로 구하려면 적어도 900000000초(250000시간)의 시간이 필요한 상황임을 알 수 있었다. 그 말은 문제를 있는 대로 구현하는 것이 아니고 새로운 알고리즘을 찾는 것을 요구하는 정수론 문제라는 것이었다.

인터넷을 검색해 보니, 깃헙에 누군가가 구현한 내용에서 bipronics라는 명칭으로 x*(x+1)*y*(y+1)을 구하는 정수 배열을 활용해서 구했다고 설명했는데, 그 정수 배열이 문제에서 요구하는 답과 동일한 것이었다. 왜 약수 중에 a+b=c+d+1인 약수와 x*(x+1)*y*(y+1)이 동일한지 이해는 안되었지만 그렇다고 한다. 처음 접근한 방법으로 안되었을 때, 숫자 리스트를 만들고 a+b=c+d+1을 만족하는 경우에 flag을 바꾸는 형태로 해결할 수 있을지 고민하다가, 변수가 너무 많아 포기했는데 조금은 비슷한 접근인 것 같기도 했다.

이 개념으로 구현하니 1백만 개는 0.04초만에 구할 수 있었는데, 그래도 1경 개를 구하는 데에는 시간이 꽤나 걸렸다. 조건에 맞는 리스트를 구하는 것보다 중복을 제거하는 데 시간이 더 많이 걸린 것이 함정이었다. 파이썬의 list(set())의 조합으로 중복을 제거했는데, 7천만 개 이상 리스트에서 중복 제거하는 데 많은 시간을 필요로 했다. 대충 1분 이내에 조건에 맞는 리스트를 구했는데 거기에서 중복을 제거하는 데 10분 이상 소요되었다.

30의 약수는 1, 2, 3, 5, 6, 10, 15, 30이다.

30의 모든 약수인 d와 d+30/d는 소수이다.

100000000이하의 정수 n의 약수 d가 있을 때, 모든 d+n/d가 소수인 n의 합계를 구하시오.

--------------------------------------------------------------------------

처음에는 정직하게 접근해서 1에서 1억 사이의 숫자를 대상으로 약수(d)를 구하고 d+n/d가 소수인 숫자를 찾게 했다. 시간이 많이 걸려서 생각해 보니 d+n/d가 소수이려면, d=n일 경우 n+1이 소수이고 2를 제외하고 모든 소수는 홀수이므로 n은 짝수여야 한다. 그리고 짝수의 경우 d=2일 때 n/2가 홀수여야 하므로 4의 배수가 되면 안된다. 그러므로, 2, 6, 10으로 커지는 4i+2의 경우만 검증하면 된다. 이렇게 해서 실행시간을 많이 줄였지만 1억까지 계산하려면 여전히 많은 시간을 필요로 했다.

그래서, 접근을 바꿔서 1000이하의 숫자(d)의 반복문과, d부터 시작해서 n/d를 구하는 이중 반복문을 만들고, 두 수의 합계가 소수가 아닌 경우에는 원 숫자에 표시하도록 처리해서, 남는 수의 합을 구하도록 해결책을 다르게 접근해서 9분 이내에 답을 구할 수 있었다. 

참고로, 챗gpt의 성능 테스트겸 357번 문제를 물어봤는데 문제에서 요구하는 그대로 가장 정직하게 프로그램을 제시했다. 성능 문제만 고려하지 않으면 즉시 적용 가능하도록 구현해 내는 것이 어찌보면 대단하다 싶었다.

레온하르트 오일러는 1707년 4월 15일에 태어났다.

배열 1504170715041707n mod 4503599627370517을 생각해 보라.

이 배열의 요소는 이전에 찾은 모든 오일러코인보다 작은 오일러코인으로 정의된다.

 예를 들어, 첫 요소인 1504170715041707은 첫 오일러코인이다. 두번째 요소인 3008341430083414는 1504170715041707보다 크기 때문에 오일러코인이 아니다. 세번째 요소인 8912517754604는 새로운 오일러코인이 된다.

처음 두 오일러코인의 합계는 1513083232796311이다.

모든 오일러코인의 합계를 구하시오.

--------------------------------------------------------------------------

프로젝트 오일러의 문제가 그렇듯 문제 자체는 간단하고 프로그램으로 구현하기도 쉽다. 다만, 정수론에 대한 이해 없이 문제를 정직하게 구현하면 시간의 함정에 빠지게 된다. 문제를 보면 오일러코인이 1이 되면 끝나는데, 최악의 경우 4,500조 횟수를 반복해야 구할 수 있기 때문이다.

문제대로 정직하게 구현하면 처음 16번 오일러코인까지는 그런대로 빨리 구할 수 있지만 그 이후로는 시간이 많이 소요되며, 처음 20번 오일러코인까지 나온 특성(이전 코인과의 차이가 같거나 크게 나옴)을 이용해서 구현하면 54번째까지는 빨리 구하지만 그 뒤로는 마찬가지로 시간이 너무 많이 소요된다.

그래서 정수론의 도움을 받으려면, 나머지 함수의 나누기 특성에 대한 이해가 필요하다. 문제를 공식으로 만들어  설명하려면 우선 상수 1504170715041701=euler, 4503599627370517=divider로 정의하자.

(euler*n)%divider=x 형태가 된다.

n=(x/euler)%divider

n=(x*euler^-1)%divider가 되는데, 여기서 나머지 함수의 나누기 특성을 위해 페르마의 소 정리를 보면,

a^p-1 ≡ 1(%p), 단 p는 소수이고 a는 p의 배수가 아닌 경우

a^p-1=a*a^p-2≡ 1(%p)가 된다.

이를 위 공식에 적용하면 n=(x*euler^(divider-2))%divider가 된다.

그리고 (euler^(divider-2))%divider는 상수 형태이므로 프로그램으로 구현하면 어렵지 않게 구할 수 있다(3451657199285664). 페르마의 소 정리를 이용해서 계산했는데, 좀 더 빠른 성능을 위해서는 확장 유클리드 개념을 활용하면 된다고 한다.

이 내용을 구현하면 오일러코인 값이 1부터 시작할 때 몇번째 배열 값이 되는지 쉽게 구할 수 있고, 배열 값이 이전 값보다 큰 경우를 제외하게 되면 실제 오일러코인 합계에 포함되는 값들을 구할 수 있다.

나머지 함수의 나누기 특성만으로 구한 것으로 설명은 되어 있었지만, 정수론에 대한 이해가 부족해서인지 빠른 형태로 구현하지 못해서, 두 프로그램의 결과를 조합해서 문제에서 요구하는 오일러코인의 합계를 구할 수 있었다.