책 이야기

날짜: 2025. 3. 7.
저자: Steven Levitsky, Daniel Ziblatt 저, 박세연 역
출판사: 어크로스
이미지: 예스24
정가: 16,800원

유튜브에서 김부겸 전 총리가 유시민 전 장관의 책을 읽으라는 권유에 응답하면서 들었던 책이어서 (유 전 장관은 책을 잘못 선택했다고 다시 응수했지만)  호기심이 생겨 보게 되었다.

최근 우리나라가 정치적으로는 양극화가 심해지는 상황이어서 많은 우려를 하고 있는 상황인데, 이 책을 보니 미국도 양극화 측면에서는 우리와 크게 다르지 않은 상황인 것 같았다.

미국은 공화당은 내륙+시골에서 많은 지지를 받는 보수성향이 강한 정당, 민주당은 해안+도시에서 많은 지지를 받는 진보성향이 강한 정당이라는 인식을 가지고 있었는데, 건국 이후, 남북전쟁 시점까지는 민주당이 더 보수적이었고, 공화당이 상대적으로 진보적인 입장이었다는 것은 처음 알게된 흥미로운 사실이었다.

무솔리니(이탈리아), 히틀러(독일), 바르가스(브라질), 후지모리(페루), 차베스(베네수엘라) 등 권위주의자들은 처음에 민주적인 과정을 통해 지도자가 되었고, 그 이후 심판을 사로잡고(위법행위를 묵인, 허용), 주요 인물을 제쳐두고(반대하는 사람을 배제), 규칙을 바꾸는(자신에게 유리하게 제도 변경) 과정을 통해 권력을 가지고 권위주의 정권을 완성할 수 있었다는 점은 시사하는 바가 컸다. 그리고,독재자가 될 가능성이 높은 사람을 판별하는 방법으로 민주주의 게임 규칙에 대한 약한 헌신, 상대방의 정통성을 부정, 폭력에 대한 관용 또는 격려, 경쟁자와 비판자의 시민적 자유를 제한하려는 것을 들었는데 남의 이야기가 아닌 것처럼 느껴졌다.

미국에도 그럴 가능성이 있는 사람이 여럿 있었지만, 과거에는 정당에서 자체적으로 문지기(gatekeeper) 역할을 해서 문제가 될 사람을 걸러냈지만 지금은 그런 과정이 없어졌으며, 외부 자금의 가용성이 높아지고, 케이블 뉴스와 소셜 미디어의 폭발적 증가 등의 이유로 권위주의자가 권력을 가질 가능성이 높아졌다고 보고 있었다. 그러면서도, 일반인의 삶이 경제적으로 어려워지고, 비슷한 시기에 유색인종의 비중이 증가하면서, 백인, 복음주의자가 중심이 되는 공화당, 소수 인종의 비중이 높은 민주당으로 양극화되는 현상이 벌어지고 있다고 분석했다.

이에 대해 저자는 많은 분량을 들여서 미국이 민주주의가 잘 작동되던 이전의 시기에는 상호 관용(mutual tolerance), 제도적 인내(institutional forbearance)가 작동했기 때문에 가능했던 것으로 분석하고, 양극화가 심화된 지금은 정치적 당파성 보다는 개별 사안에 대한 의견으로 이견을 좁혀 나가면서 당파성을 탈피하고 스펙트럼을 넓혀, 인종적 다양성의 시대애 예전 규범을 다시 살려야 한다는 조금은 원론적인 내용을 제시하고 있다.

단순히 트럼프를 비판하는 책일거라 생각하고 봤는데, 그것보다는 몇십년의 역사와 함께 현재의 미국 내 정치적 양극화가 만들어졌다고 분석하는 것은 새로웠고, 저소득 등 자격이 되는 사람을 지원하는 미국 방식보다는, 사회보장, 포괄적 건강보험, 최저임금 인상, 보편적 기본소득, 보육 지원 등 지금 우리나라에서 많이 논의되고 적용되고 있는 방법들이 정치적 양극화를 완화하는 수단으로 보고 있어서, 우리는 이런 측면에서 이미 선진국이가 싶기도 했다.

우리나라의 경우, 민주주의도 많이 발전하고 사회도 성숙해지고 있는데 최근에 생기고 있는 정치적 양극화 현상에 대해 걱정이 많았는데 이를 해결하는 방법을 찾는데 도움이 되지는 않았지만, 이런 현상이 우리만의 일은 아니라는 것을 알게되고 조금 위안을 받았다.

날짜 : 2025. 2. 6.

저자 : Yuval Noah Harari 저, 김명주 역

출판사 : 김영사

이미지 : 예스24

정가 : 27,800원

사피엔스, 호모 데우스 등 그의 전작을 재미있게 읽었기 때문에 망설이지 않고 선택했는데 기대를 저버리지 않고 새로운 시각을 많이 얻을 수 있게 되었다. 저자는 의도하지 않았겠지만 지금 우리나라 상황과 연결시켜 생각할 이야기들이 많았기 때문에 관료제, 종교, 민주주의, 정보, 인공지능 등 저자가 다룬 키워드에 대해 많은 생각을 하면서 읽었다.

우리가 당연하게 받아들이고 있는 위의 키워드들이 역사적으로 보면 계속 변화하고 있었고, 역사 전반에 걸쳐 정보 네트워크는 진실보다는 질서를 더 선호해 왔다는 말은 많이 의미심장한 것이었다. 정보기술의 발달로 소수에게 있던 권력이 민주화되면서 진실을 공유하기 더 쉬워졌다 생각하고 있었는데, 그 정보기술의 발달이 반드시 진실을 공유하는데 도움되지는 않는다는 말이, 정보의 홍수 속에서 무엇이 진실인지 고민하고 있는 현상을 잘 설명해주는 말로 느껴졌다.

인공지능 기술이 인공 일반 지능이라 부르는 AGI수준으로 진행되는 현재에는 어떠한 변화를 가져올 지 가늠할 수 없는데, 이것을 역사학자의 입장에서 잘 분석하고, AGI가 대두되기 전에 이미 작업을 시작해서, 인공지능이 인류를 멸망시킬지도 모른다는 비관론과 모든 문제를 해결해 줄것이라는 낙관론 사이에서 강력한 자체 교정 메커니즘을 갖춘 균형 잡힌 정보 네트워크를 만들기를 권고하는 그의 혜안이 감탄스러웠다.

저자가 제안한 것이 잘 받아들여져서, 제국주의 시대와 같이 AI기술력에 의한 국가간 약육강식의 시대가 펼쳐지지 않았으면 하고, 단기적으로는 사회 체계를 통해서든 기술을 통해서든 가짜뉴스는 사라졌으면 한다.

날짜 : 2024. 5. 31.

저자 : 이시한 저

출판사 : 북모먼트

이미지 : 예스24

정가 : 19,000

알파고가 이세돌을 이겼을 때에도 컴퓨터가 생각보다는 빠르게 발달하고 있지만, 아직까지 특정 용도에서만 능력을 발휘할 수 있다는 면에서는 한계가 있을 수 밖에 없다고 보고 있었다.

그리고, 그것이 동작(내지난 판단)하게 만든 이유는 알 수 없지만 스스로 학습하여 그렇게 동작하는 방식의 딥러닝이라는 기술에 기반했다는 것을 보고, 원리를 설명할 수 없는 기술에 기반해서는 인공지능의 3대 원칙을 준수하는 것을 보장할 수 없어 AI 겨울이 다시 올지도 모른다는 우려깊은 시선으로 바라보고 있었다.

그런데, 2년 전 오픈AI가 챗GPT라는 거대 언어 모델(LLM) 기반의 대화형 인공지능을 공개하면서 전문가(내지는 딥러닝을 이해하는 똑똑한 사람) 사이에서 확산되고 있던 AI가 일반인에게도 매우 빠른 속도로 대중화되었다.

포털이라는 이름으로 광고가 섞인 많은 것들을 검색결과로 제시하던 네이버나 다음에 비해, 간결하게 원하는 결과를 보여주던 구글에 만족하고 검색을 했지만, 이제는 구글마저도 광고성 게시물(심지어는 검색내용과 관계없이 키워드를 메타데이터 속에 잔뜩 늘어놓은 광고사이트)을 걸러내지 못하고 보여주는 것에 피로감이 컸는데 좋은 대안이 나온 것으로 판단되었고, 이 말은 검색광고로 성장한 구글의 미래 성장에 큰 위협이 나타난 상황으로 보인다.

몇시간 걸려 만든 코딩도 몇초만에 끝내는 모습을 보면서 창의력과 전문성이 필요한 소수의 전문 인력 이외에 이들을 지원하며 전문가로 성장해오던 단순(내지는 반복성) 작업을 하던 이들은 설자리가 없어질 수도 있겠다 싶다. 며칠전부터 Claude 3.5 Sonnet을 이용하면 코딩할 필요가 거의 없다는 이야기가 나오기 시작하는데, 이것이 무엇인지 알아봐야 할 것이 하나 더 늘어난 것 같다.

책에 대해 이야기하면, 저자는 챗GPT로 나타나는 전세계의 변화를 빠르게 파악하고 잘 정리해 뒀으니 어떤 형태의 변화가 있는지, 나는 어떻게 이것을 잘 활용할 것인지 아이디어를 구하기에 좋다. 개인의 상황에 따라 만족도에 차이가 있을 수 있지만, 현재의 나로써는 만족할 만한 수준의 내용을 잘 담은 것 같다.

날짜 : 2024. 5. 12.

저자 : Frans De Waal 저, 장대익, 황상익 역

출판사 : 바다출판사

이미지 : 예스24

정가 : 18,000원

찾아보니 이 책이 처음 발간된 때가 42년 전인 1982년이고, 읽고 있는 책은 2007년에 출간된 25년 기념판이다. 50년쯤 전에 아른헴 동물원에서 침팬지를 관찰하면서 쓴 책이지만, 지금 읽어도 오래되었다는 느낌이 전혀 들지 않는 것이 가장 흥미로웠다.

직전에 읽었던 '차이에 관한 생각'은 저자의 의견을 뒷받침하기 위해 보노보노, 침팬지 등 여러 종류의 유인원에 대한 이야기를 하면서 공통점과 차이점을 제시하고, 젠더에 대해 이야기하는 형태로 되어 있어 그리 재미있게 읽히지 않았는데, 이 책은 특정 동물원의 침팬지 집단만을 대상으로 이야기하고 있어 더 편하게 읽을 수 있었다.

마지막 장에 공식화, 영향력, 연합, 균형, 안정, 교환, 술수, 합리적 전략, 특권의 9가지 제목으로 침팬지가 정치적인 행동을 하는 이유를 잘 분석해놓고 있어 저자가 내린 결론 또한 쉽게 이해할 수 있었다.

그리고, 사람의 고유한 특성이라고 했던 도구를 사용하는 것을 비롯한 기억과 전략적 사고 등 여러가지 것들이 사람만이 가지고 있는 것이 아니라는 것을 다시금 알 수 있게 해줬고, 제한되어 있는 침팬지 사회에서 발견된 여러가지 정치적 행동을 사람들 사이에서도 발견가능한 것 같다는 생각도 들었다.

날짜 : 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부터 시작할 때 몇번째 배열 값이 되는지 쉽게 구할 수 있고, 배열 값이 이전 값보다 큰 경우를 제외하게 되면 실제 오일러코인 합계에 포함되는 값들을 구할 수 있다.

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

A를 잔여 특성 p를 갖는 근을 적분하는(radically integral) 적분된 로컬 필드를 가로지르는 아핀 평면(affine plane)이라 하자.

정규화 된 하르 척도(Haar measure)를 사용하여 A의 개방형 선 부분을 U라 (고려)한다.

U를 A에 직교 커널로 임베딩하는 자코비안(Jacobian)의 최대 가능한 판별식으로 f(m,p)를 정의한다.

f(20230401,57)을 구하시오. 굵은 글씨로 표현된 단어의 첫 글자를 연결하여 답하시오.

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

수학 배경이 없으면 알지도 못하는 단어들이 많이 나오는 문제여서 보류했다가 나중에 풀어보는데, 앞에서 나온 어려운 문제는 이해할 필요가 없고(문제를 한글로 바꾸는 것도 매끄럽게 못할 지경이다) 마지막 줄만 읽어보면 되는 것이었다.

즉, 영어로 된 문제에서 굵은 글씨로 표현된 단어의 첫 글자를 연결해서 답을 하면 된다. 답이 3단어여서 띄어쓰기, 기호 추가 등을 통해 제대로 된 단어를 만들었는데 그럴 필요 없이 그냥 글자를 쭉 연결해서 1개 단어 형태로 답하면 된다.

제목은 대단한 제안이지만 쉬어가기 문제였다.

항아리에 일곱 가지 무지개 색의 공이 각각 10개씩, 총 70개의 공이 항아리에 있다.

랜덤하게 20개의 공을 선택할 경우 몇 가지의 색이 있겠는가?

소숫점 9자리까지 답을 구하시오(a.bcdefghij형태).

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

처음에는 조합(combination)을 이용해서 나오는 각 경우의 수에 대한 색상 종류를 구해서 전체 평균을 구하는 형태로 접근했는데, 가능한 조합인 ₇₀C₂₀의 값이 161,884,603,662,658,000이어서 코딩을 정확하게 한 것은 자신있지만 시간 내에 답을 구하리라는 장담을 할 수 없는 상황이었다.

그래서 다른 형태의 접근이 필요한 상황이었는데, 구글의 도움을 받아 해결할 수 있었다. 특정 색이 있지 않을 확률은 70개 중 60개에서 20개의 공을 꺼내는 경우이므로(₆₀C₂₀/₇₀C₂₀), 특정 색이 있을 확률은 정반대가(1-₆₀C₂₀/₇₀C₂₀) 되며, 7개 공 각각에 대해 구하면(7*(1-₆₀C₂₀/₇₀C₂₀)) 된다.

이렇게 접근하는 논리를 생각해 내는 것이 쉽지 않은 문제이지, 이 논리를 구현하는 것은 정말 간단하다.

이차원 평면에 다음 랜덤 숫자 생성기를 이용하여 좌표의 배열인 P_n을 생성하자:
S₀=290797
S_n+1=S_n² mod 50515093

P_n=(S_2n,S_2n+1)

P₀,⋯,P_k-1 중 임의의 (서로 다른) 두 좌표의 최단 거리를 d(k)라고 하면, d(14)=546446.466846479이다.

소숫점 9자리까지 나오도록 반올림하여  d(2000000)을 구하시오.

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

번호가 높은 문제여서 해결한 사람이 많지 않지만, 5% 난이도 문제여서 그렇게까지 까다롭지는 않다.

초기값과 값을 구하는 공식, 해당 값을 이용한 좌표를 구하는 공식이 있으므로 요구하는 대로 값을 계산하면 된다.

다만, 예시를 보고 정확하게 프로그램을 작성하지 않아 한가지 실수가 있었는데, mod함수를 사용해서 연속된 두 좌표의 거리 중 가장 짧은 것을 계산한 것이었다. n개 좌표가 있으면 n-1번 계산했는데, 하필이면 예시가 12번째, 13번째 사이가 최단거리인 경우여서 잘못된 프로그램으로도 예시의 답이 나와서 잘못된 부분을 찾는데 애먹었다.

하지만, 곰곰히 생각해 보면, 문제에서는 임의의 두 좌표에 대한 거리를 묻고 있으므로 생성가능한 모든 조합에 대해 거리를 계산해야 되어서 시간이 매우 많이 필요하다. 복잡도가 O(n)에서 O(n²)이 되면서 시간이 기하급수로 늘어나는 문제가 있었다.

몇시간이 걸려도 해결되지 않아 코드를 일부 개선해봤지만 시간이 더 걸리는 등 알고리즘에 대한 근본적인 해결책이 필요했다. 관련 내용을 검색해보다 복잡도를 낮출 아이디어를 구했다. 2백만개의 좌표가 mod 함수에 의해 구해져서 들쑥날쑥이어서 모든 좌표 간의 거리를 계산했는데, 원점을 기준으로 정렬하면 앞뒤 좌표간의 거리만 계산해도 해결 가능하게 되어 복잡도가 줄어든다.

전체 실행시간을 보면, Pn 좌표를 생성하는데 3.6초, 원점 기준으로 정렬하는데 6초, 좌표 간 거리를 계산하는데 10초가 걸려 20초 만에 답을 구할 수 있었다.

169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.

다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:

1. 회문(palindrome)이 아니며,
2. 소수의 제곱이며,
3. 반대로 한 것도 소수의 제곱이다.

169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.

처음 50개 reversible prime square의 합계를 구하시오.

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

프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.

50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.

100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.

문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.

일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.

그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.

추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.

작아지지 않는 정수의 수열인 a_n은 다음 과정을 통해 양의 실수 θ에서 만들어 낼 수 있다.

    b₁=θ

    b_n=└b_n-1┘(b_n-1-└_bn-1┘+1) , n>=2일 때

    a_n=└b_n┘

└ ┘은 버림을 나타낸다.

예를 들어, θ=2.956938891377988...는 피보나치 수열(2, 3, 5, 8, 13, 21, 34, 55, 89, ...)를 생성한다.

양의 정수의 수열인 a_n을 연결하면, τ로 표기하는 a₁에서 시작해서 소숫점 아래의 연속된 요소를 결합한 a₁.a₂a₃a₄...모양의 실수가 된다.

예를 들어, θ=2.956938891377988...에서 나오는 피보나치 순열을 연결하면 τ=2.3581321345589...가 되며, θ 값에 대해 θ와 τ는 다르다.

a₁=2에서 시작해서 수열을 결합했을 때 τ=θ가 되는 유일한 값 θ를 찾으시오. 답안은 반올림하여 소숫점 24자리까지 구하시오.

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

처음에는 고민을 많이 하고 접근했는데, 생각보다 어렵지 않게 해결 가능했다.

처음에는 θ=2로 시작해서, 공식을 소숫점 25자리까지 반복 적용해서 나온 숫자(τ)를 다시 θ로 설정하는 작업을 τ=θ가 나올때까지 반복하면 되는데 몇 번 반복하지 않고 답을 구할 수 있었다.

피터는 (피라미드 모양) 4면 주사위 9개를 가지고 있고, 각 주사위 면에는 1,2,3,4가 적혀 있다.

콜린은 (정육면체 모양) 6면 주사위 6개를 가지고 있고, 각 주사위 면에는 1,2,3,4,5,6이 적혀 있다.

피터와 콜린이 주사위를 굴려 합계를 비교해서 합계가 큰 사람이 이긴다. 둘의 합계가 같으면 무승부이다.

4면 주사위를 가진 피터가 콜린을 이길 확률은 얼마인가? 정답을 소숫점 7자리까지 반올림으로 나타내어 0.abcdefg 형태로 제시하시오.

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

처음에 랜덤 함수를 이용하여 둘의 주사위를 생성하고, 합계를 비교하는 몬테카를로 시뮬레이션 방법을 활용하여 천만번 게임을 운영한 승패를 구했는데 답이 맞지 않았다.

그래서 어쩔수 없이 단순하게 전체 경우를 구하는 형태로 접근을 바꿨다. 파이썬 라이브러리의 중복순열(from itertools import production)을 이용하여 피터와 콜린의 경우의 수를 각각 구하고, 그것을 합계로 바꿔 반복문을 통해 두 사람의 모든 경우를 비교하는 형태로 구현했다. 이렇게 설명하면 간단하지만 두 사람의 경우를 곱하면 122억이 넘기 때문에 보기보다 많은 시간이 걸리는 문제였다(몬테카를로 시뮬레이션을 활용하더라도 100억 번은 넘어야 결과에 가까운 답이 나올 수 있다는 뜻으로 이해되었다).

다시 생각해보니, 피터는 9~36, 콜린은 6~36의 합계가 나올 수 있지만 경우의 수는 각각 262,144, 46,656이므로 많은 경우 중복되어 나온다. 앞의 방식처름 122억 회 이상 비교하는 것 보다는 각 값에 대한 발생횟수를 가중치 형태로 만들어서 계산하니 2초 내외에 답을 구할 수 있었다.

문제를 잘못 이해해서 답을 abcdefg 형태로 구했는데 계속 틀리게 나와 알고리즘을 다시 검토하는 등 시간을 많이 소모했는데, 답은 이미 맞게 구했고 '0.abcdefg' 형태로 답을 쓰면 되는 것이었다.

이항계수 (n k)는 위 그림과 같이 파스칼 삼각형이라 불리는 삼각형 형태로 나타낼 수 있다.

파스칼 삼각형의 첫 8줄은 12개의 서로 다른 수로 구성된다: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35.

n이 제곱수로 나눠지지 않으면 양의 정수 n을 squarefree라 부른다. 파스칼 삼각형 첫 8줄의 서로 다른 12개 숫자 중에서 4와 20을 제외하고는 squarefree이다. 첫 8줄에서 sqarefree인 숫자의 합계는 105이다.

파스칼 삼각형 첫 51줄의 서로 다른 squarefree 숫자의 합을 구하시오.

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

생각가능한 몇 개의 단계로 나눠 답을 구했는데 그래도 25초 내외 시간 안에 답을 구할 수 있었다.

처음에는 파스칼 삼각형 모양의 리스트를 만들어가면서 서로 다른 숫자의 리스트를 구했다. 파스칼 삼각형 자체를 만들려고 했는데, 그것이 뒤에 다시 쓰이지 않기 때문에 파스칼 삼각형의 현재 행을 구하면서 서로 다른 숫자는 별도 리스트에 추가하는 형태로 했다.

서로 다른 숫자 리스트를 정렬하고, 그 최대값 이하의 제곱수 리스트를 만들었다. 서로 다른 숫자 리스트의 각 숫자에 대해 제곱수 리스트 숫자로 모듈러 연산(%)을 수행하고, 나머지가 0인 경우는 sqaurefree가 아니므로 해당하는 숫자의 리스트를 만들었다.

마지막으로, 서로 다른 숫자 리스트에서 squarefree가 아닌 숫자를 제외한 숫자를 모두 더해서 합계를 구했다.

그렇게까지 까다로운 문제는 아니었는데 2가지 오류때문에 해결하는데 시간이 좀 걸렸다. 하나는 51줄을 55줄로 잘못 설정해서 발생한 것이었는데 문제를 다시 읽고 해결할 수 있었다. 다른 하나는 2번째 단계에서 처음에는 나머지가 0인 경우에 서로 다른 숫자 리스트에서 해당하는 숫자를 삭제하는 형태로 해서 바로 결과를 구하도록 구성했는데, for문 대상 리스트에서 숫자가 삭제되면서 인덱스 값이 모두 바뀌어서 엉뚱한 연산을 하는 상황이 생겼다. 상황을 보고도 어떤 문제 때문에 생기는 것인지 빨리 인지하지 못해서 오류를 해결하는 데 많은 시간이 걸렸다.

적어도 2개의 소수를 약수로 가지고 있는 수를 합성수라 한다. 예를 들어, 15=3x5, 9=3x3, 12=2x2x3이다.

(서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 30이하에 10개가 있다:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26

10⁸보다 작은 n에 대해, (서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 몇 개인가?

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

1억 이하의 숫자 중에 2개 이상의 소수의 곱으로 구성된 합성수가 몇 개인지 묻는 문제이다. 문제에서 (서로 다를 필요가 없는)으로 설명된 부분은 동일한 소수로 곱해도 된다는 뜻이므로, 예시와 같이 9=3x3을 허용하게 구현하면 된다.

빠른 계산을 위해서 1억 이하의 소수 목록을 구하고, 2중 반복문에서 소수끼리 서로 곱하게 해서 목록을 구하고, 파이썬의 집합을 이용해서 중복을 제거해서 구했다. 1억 이하의 소수가 5백만 개 이상 나오더니 목록을 구하면서 메모리 에러가 발생했다. 생각보다 리스트가 커져서 문제가 생긴 것 같았다.

그래서, 결과값 리스트를 만들지 않고, 생성되는 합성수의 갯수를 구하도록 바꿔서 답을 구할 수 있었다. 소수 2개의 곱을 구하는 것이어서 다른 약수가 있을 수 없기 때문에 중복을 제거하는 과정이 필요없었다.

2⁷=128은 "12"로 시작하는 첫번째 2의 거듭제곱수이며, "12"로 시작하는 다음 2의 거듭제곱수는 2⁸⁰ 이다.

p(L,n)을 L로 시작하는 십진수 중 2^j가 n번째 가장 작은 j를 나타낸다고 정의하면, p(12,1)=7이고 p(12,2)=80이다.

또한 p(123,45)=70이다.

p(123,678910)을 구하시오.
--------------------------------------------------------------------------

문제에서 요구하는 대로 구성하면 프로그램의 구조는 간단하다. 2를 계속 곱해가면서 L로 시작되는 n번째 숫자를 찾아 거듭제곱수를 알려주면 된다.

이렇게 구현하면 예시로 나와있는 p(12,1), p(12,2), p(123,45)는 어렵지 않게 구할 수 있다. 하지만, 2의 거듭제곱수 중에서 123으로 시작하는 678910번째 숫자가 2의 몇 거듭제곱인지 찾는 것은 데이터 허용범위가 넓은 파이썬으로도 어려운 일이었다. (이번에는 4300자릿수 이상을 넘을 수 없다는 에러메시지를 봤던 것 같다)

프로젝트 오일러의 높은 번호 문제는 난이도가 낮아도, 간단히 해결 가능한 것이 아니라 (주로 상상도 못한 크기의 숫자로) 한계가 숨어 있고, 이것을 어떻게 해결해내는 것인지가 추가로 포함되어 있는 것 같다.

이번 문제에서는 앞의 3자리만 동일하면 되기 때문에, 일정크기 이상으로 커지면 앞의 3자리에 영향을 미치지 않을 아랫쪽 수를 10000으로 나눠 없애는 형태로 계산했는데, 정확한 숫자를 구하는 것이 아니어서 살짝 걱정되었지만 맞출 수 있었다.

0~9 사이의 숫자 d로 채워지는 4x4 크기의 격자가 있다.

그 격자는 위와 같이 나타낼 수 있으며, 예시에서 각 열과 행의 합은 12이고, 대각선의 합 또한 12이다.

0~9 사이의 숫자 d로 구성되는 4x4  격자에서 각 행, 열, 두 대각선의 합계가 동일한 경우는 몇가지가 있는가?

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

처음에는 기계적으로 중복순열을 만들어서 해결하려 했으나, 10¹⁶크기의 중복순열을 만들면서 메모리 에러가 발생했다.

그래서 격자의 (0,0)에서 (4,4)까지 a부터 p까지 자리기호를 매기고, (16차) 반복문으로 생성되는 숫자를 기준으로 첫 행의 가로 합계(sum=a+b+c+d)가 나머지 가로 합계(e+f+g+h, i+j+k+l, m+n+o+p), 세로 합계(a+e+i+m, b+f+j+n, c+g+k+o, d+h+l+p), 대각선(a+f+k+p, d+g+j+m)과 동일한 지 확인하도록 구성을 했는데, 10¹⁶ 크기만큼 반복을 하면서 시간이 대책없이 오래 걸리는 문제가 발생했다.

그래서, 고민을 하다 다른 사람이 해결한 방법을 검색해 봤는데, 변수 갯수를 줄이는 형태로 접근해서 실행시간을 개선하는 방법을 제시한 것이 있어 그 방법을 적용해 봤다. 앞 문단에서 설명한 것과 마찬가지 상황에서 sum=a+b+c+d로 했을 때,  가로 세로 합계 공식을 바꿔, h=sum-e-f-g, l=sum-i-j-k, p=sum-m-n-o, m=sum-a-e-i, n=sum-b-f-j, o=sum-c-g-k를 구할 수 있고, 대각선 공식을 이용하면 j=sum-d-g-m이 된다.

a, b, c, d, e, f, g, i, k에 대해 반복문을 구성하여, h, o는 반복문의 값으로 구하고, m을 먼저 구해서 j를 구하고, 그 값을 이용해서 l, p, n를 구할 수 있다. 대각선의 합계가 맞는지 확인하고(sum=a+f+k+p), 연산에 의해 구해진 값(h,j,l,m,n,o,p)이 0~9 사이의 값인 경우에 문제의 조건을 만족하는 경우가 된다.

이것을 반복문을 활용해서 계속 구해나가면 복잡도가 10¹⁶에서 10⁹로 1/10⁷이 줄어들어, 이전보다는 훨씬 빠르지만 그래도 답을 구하는 데는 시간이 좀 필요했다. 다만, 스스로 생각해서 끌까지 해결하지 못하고 다른 사람의 아이디어를 봐야 해결가능하다는 것이 씁쓸했다.

분자가 분모보다 작은 양의 분수를 진분수(proper fraction)라 한다.

어떤 분모 d에 대해 d-1개의 진분수가 있다. 예를 들어, d=12일때 진분수는 다음과 같다.
1/12,2/12,3/12,4/12,5/12,6/12,7/12,8/12,9/12,10/12,11/12.

약분되지 않는 분수를 탄력분수(resilient fraction)이라 부르자.

특정 분모 d에 대해 약분되지 않는 분자의 비율을 R(d)라 정의한다. 예를 들어, R(12)=4/11이다.

실제로, d=12는 R(d)<4/10인 가장 작은 분모이다.

R(d)<15499<94744인 가장 작은 분모 d를 구하시오.

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

약분되지 않는 분수를 학교에서는 기약분수(inreducible fraction)로 배웠는데, 여기에서는 무슨 차이가 있는지 모르겠지만 탄력분수로 정의하고 있다.

처음에는 모든 숫자를 대입해서 계산을 시도했는데, 시간이 너무 많이 걸렸다. 기약분수가 적은 경우를 찾는 형태여서 생각해보니 69번 문제를 변형한 문제처럼 보였다.

일단 많이 나눠주는 수의 곱으로 분모가 되어야 작아질 것이기 때문에 처음에는 짝수를 대상으로 시도했는데, 결과값 패턴을 보니 2와 3의 공배수인 6의 배수가 값이 작은 것이 보였다. 가만히 생각해보니 작은 소수의 곱으로 구성되는 숫자일수록 나눠지는 숫자가 많아 정답에 근접하게 나오게 되는 패턴을 찾았다.

그래서, 일단은 2에서 시작해서 나오는 소수의 곱을 대상으로, 배수를 5번씩 계산해서 정답보다 낮은 경우를 찾도록 했다.(예를 들어, 2의 경우 2,4,6,8,10, 2와3의 곱인 6의 경우 6,12,18,24,30, 2와3과5의 곱인 30의 경우 30,60,90,120,150 등을 계산하도록 했다)

소수의 곱은 생각보다 기하급수로 커졌고, 그 덕분에 정답 또한 생각했던 것 보다는 엄청 큰 값이었고, 답에 근접한 값만 계산하게 했어도 상당한 시간이 필요했다.