이번 시간에는... 이번 시간에는 본 시리즈를 시작하게 된 계기가 된 뤼카의 정리를 한번 살펴보고자 한다. 시작하기에 앞서, 이 정리는 아래 링크를 기반으로 내가 이해한 내용을 덧붙여 작성했음을 밝혀 둔다. 틀린 부분, 내가 잘못 이해한 부분 혹은 논리적 비약이 생기는 부분이 있을 수 있으니 의문점이 생긴다면 댓글로 알려주면 매우매우매우 감사하겠다! https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC 뤼카의 정리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 뤼카의 정리(Lucas' theorem, -定理)는 수론과 조합론에서 이용되는 정리로, 프랑스인 수학자 에두아르 뤼카(Édouard Luca..

이번 시간에는... 이번 시간에는 시도해 볼 수 있는 방법중 하나로 확장 유클리드 호제법을 사용해보자. 사실 조합을 구할 때 확장 유클리드 호제법이 쓰이는 일은 잘 없다(대부분 모듈러 연산을 위해 소수를 제시하고, 페르마 소정리를 이용해 풀 수 있기 때문이다). 하지만 확장 유클리드 호제법 역시 다양한 상황에서 사용될 수 있고, 특히 CS에서는 현대 암호학의 근간인 RSA 알고리즘에도 사용되므로 깊게 이해하고 넘어가보자. 확장 유클리드 호제법 이 포스팅에서도 정리된 바 있지만.. 2023.12.05 - [알고리즘 문제/백준] - [백준/3955] 캔디 분배 (Python) [백준/3955] 캔디 분배 (Python) Problem : https://www.acmicpc.net/problem/3955 39..

들어가기에 앞서.. 사족이라 접은 글로 남깁니다 :) 더보기 백준 온라인 저지를 풀면서, 내가 모르던 알고리즘과 수학 공식들을 종종 보게 된다. 그 때마다 구글링과 위키피디아를 뒤적거리면서 알고리즘을 찾아내고, 그걸 적용시키며 "아, 나는 이 문제를 이해했구나!" 라고 자만하게 된다. 하지만 사람 기억이 원체 시원찮아야지. 그 알고리즘을 적용해야 하는 다른 문제를 맞닥뜨리면, 어느 새 금붕어마냥 알고리즘을 다 까먹고 다시 똑같은 과정을 반복하게 된다. 실제로는 풀이하는 흉내만 냈을 뿐인 셈이다. 두 번째로, 이러한 새로운 정리를 문제 풀이 과정 중에 포스팅하면 나도, 그리고 어쩌다 이 블로그에 들어오는 사람들도 헷갈리기 시작한다. 제대로 정리되지 않은 셈이다. "나는 유클리드 호제법을 알고 싶은데, 알고..

다시 한 번 시작하기 전에 지난 포스팅에 이은 비정기 연재로 이를 이어나가보고자 한다. 이번에는 리스트에 대해 다루어볼 예정이다. 파이썬에서 두 리스트를 합치는 방법은 다양하다. 크게 다음과 같은 방식으로 이루어질 것이다. 함수를 통해 리스트 1에 리스트 2를 합치기 (extend) + 연산을 통해 리스트 1에 리스트 2를 합치기 (+=) 일일히 리스트 2의 원소를 리스트 1에 넣어주기 (append) 셋 모두 공통적으로 O(len(리스트2))의 시간복잡도를 갖지만, 우리는 지난 번 min vs. if 포스팅에서 파이썬의 함수 호출에 대한 오버로딩이 성능 저하를 보여주는 것을 실험을 통해 보인 적이 있다! 2023.05.08 - [CS/기타 정리] - [파이썬] Min vs. If, 좀 더 빠르게 (실행..

시작하기 전에 본 포스팅은 파이썬 알고리즘 문제풀이 도중 생각난 의문들을 해결하기 위한 정리를 수행한 기록이다. 파이썬은 매우 느린 언어로, 연산자 지정, 함수 호출 여부 등에 따라 실행시간이 TC를 판가름할 정도로 천차만별의 결과를 낳는다. 어떤 전략, 어떤 코딩을 해야 주어진 시간 자원 속에서 문제를 풀이할 수 있을지 고민한 흔적이라고 볼 수 있겠다. 오늘은 골치를 가장 많이 썩였던 min / max 함수에 대해 실험해보고자 한다. 1. Min vs If, 최솟값 탐색 전체 중 최솟값 혹은 최댓값을 구할 때가 종종 있다. 파이썬의 경우 min, max 함수를 통해 이를 지원하지만, if문을 통해 갱신하는 경우도 존재한다. 둘 중 어떤 경우가 더 시간적으로 좋은 결과를 낼지 테스트해보자. 총 10000..