전체보기141 페르마의 소정리 $ p $가 소수일때, 임의의 정수 a에 대해서 $ a^p - a $는 p의 배수이다. 이를 모듈러 연산으로 표현하면 다음과 같다. $ a^p \equiv a \pmod p $ 괄호 안의 의미는 양 변에 mod p 가 생략되었다는 뜻이다. 예를 들어, a = 3 이고 p = 7이면 $ 3^7 = 2187 - 3 = 2184 mod 7 = 0 $ 을 성립한다. 만약 a가 p로 나누어지지 않으면, 양변을 a로 나누어 동치인 식을 만들 수 있다. $ a^{p-1} \equiv 1 \pmod p $ 위 성질을 이용해서 임의의 x에 대해서 다음과 같이 일반화할 수 있다. $ a^x \equiv a^{x \mod (p-1)} \pmod p $ 이 성질을 이용해서 나머지를 매우 빠르고 쉽게 구할 수 있다. 예제 ww.. 2020. 9. 20. [알고리즘 분류] - 세그멘트 트리 세그멘트 트리 문제를 연습하기 위해 다양한 문제를 찾아 시도해봤지만, 정말 어려운 것 같다.. 기본 세그멘트에서 조금이라도 응용을 뻗어나가면 방법을 모르겠는.. 구간 곱, 구간 합, 최소값 이런 것들은 단순히 init과 update의 함수를 조금씩 수정해주면 되는 부분이라 충분히 해결 가능하다. 플레 5 정도 문제는 가장 기초적인 세그먼트 트리를 이용해서 푸는 문제인데, 그 이후로부터는 Lazy Propagation 등의 추가적인 스킬과 응용 능력이 필요한 것으로 보인다. (어려움..) 2020. 9. 20. [1] Segment Tree Segment Tree 는 다양한 유형의 문제를 빠르게 해결해주는 자료구조이다. 구간에 대한 정보를 구하는 경우, 단순히 정렬한 후 Prefix Sum 을 이용해서 구간합을 빠르게 구할 수 있지만 만약 개별 쿼리 도중 배열에서 특정 요소의 값이 변경되야 하는 경우엔 매번 다시 정렬을 해야 되어 비효율적이다. 이러한 경우, 구간에 대한 정보를 담는 Tree를 구성할 수 있는데, 이를 세그먼트 트리라고 한다. 세그먼트 트리는 기본적으로 Complete Binary Tree이고, 모든 Element에 대한 정보가 트리의 Leaf Node에 포함된다. 그리고 그 위 node들은, 자식 node를 포함하는 구간에 대한 정보를 담는 것이다. 간단하게, 세그멘트 트리를 이용해서 구간합을 구하는 코드의 예시를 보자. .. 2020. 9. 13. [2] Faas Platform이 동작하는 방식 (1) Apache Openwhisk 이 문서에서는 어떤 과정으로 서버리스 플랫폼이 동작하는지에 대해 이해해보는 문서입니다. 다양한 프레임워크가 서로 다른 방식으로 동작하겠지만, 큼직한 Flow만 이해하는 것을 목적으로 작성하였습니다. 위 글은 이 동영상을 중심으로 작성되었습니다. 동영상에 대한 발표 자료 링크는 다음과 같습니다. What is Serverless Computing? 여러번 짚어본 이야기지만, 서버리스 컴퓨팅이란 Cloud Provider가 사용자에게 컴퓨팅 리소스와 스토리지를 동적으로 할당하여, 사용자가 리소스를 유지하고 프로비저닝 할 필요 없게, 어플리케이션의 비즈니스 로직만 고민할 수 있게끔 편의를 제공하는 서비스이다. 서버리스 함수는 이벤트 기반으로 동작하고, 이는 요청이 왔을 때 Trigger 되는 것이다. 서비스 .. 2020. 9. 11. 이전 1 ··· 16 17 18 19 20 21 22 ··· 36 다음
