코딩못하는사람

세그먼트 트리란? 세그먼트 트리(Segment Tree) 또는 인덱스 트리(Index Tree)는 다음 두 연산을 어떻게 더 효율적으로 할까에 대한 고민에서 출발한다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i] = v 두번째 연산은 O(1)에 해결할 수 있겠지만 첫 번째 연산은 l-r의 길이만큼의 시간 O(NM)이 쿼리가 요청될 때 마다 소요될 것이다. (쿼리 m번 구간크기 n) 따라서 우리는 M과 N이 클때를 위한 자료구조인 세그먼트 트리를 알아야한다. 가장 기본적인 2,3,7,4,5,9,6,1의 구간합을 구하는 세그먼트 트리를 보자. 트리는 완전 이진 트리로 구성된다. 또한 트리의 ..

피보나치 수를 구하는 3가지 방법. 피보나치 수는 알다시피 다음과 같이 정의되는 수열이다. 이렇게 이전 2개의 합이 다음 오는 수가 되는 수열이다. 조금 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...이 된다. 가장 기본적인 문제를 풀어보자 10826 피보나치 수 4 www.acmicpc.net/problem/10826 1.접근 n은 10,000보다 작거나 같은 자연수 또는 0이다. 쉬운 피보나치 수이다. 2.풀이 우리는 DP느낌의 방법으로 쉽게 O(N)시간에 답을 구할 수 있다. 3.코드 4.배운점 사실 dp로 구현했었는데 메모제이션 할 필요없이 for 문을 돌리면 가장 간단했다. 2749 피보나치 수 3 www.acmicpc.net/problem/27..

페르마 소정리 보안 수업에서 자주 봤던 정리이다. 여기서 한번더 나아가면 다음과 같은 식을 유도할 수 있다. 이말은 모듈러 p에 대해서 a의 역원이 a^p-2가 된다는 뜻이다. 이걸 알고 문제를 들어가야 풀 수 있다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1.접근 n이 너무 크기때문에 이항계수 성질을 이용한 O(n^2)의 풀이는 불가능 할 것이라고 생각했다. 2.풀이 이 문제의 궁극적 목표인 이항계수의 식을 써보자면 N!/(N-K)!*(K)이다. 이것을 %P로 나눈값을 ..

1.2 핵심 기능 1.2.1 reindex 재색인 Series객체에 대해서 reindex를 호출하면 데이터를 새로운 색인데 맞게 재배열하고 존재하지 않는 색 이 있다면 NaN을 추가 obj = pd.Series([4.5, 7.2, -5.3, 3.6], index=['d', 'b', 'a', 'c']) obj2 = obj.reindex(['a', 'b', 'c', 'd', 'e']) #원하는순으로 출력한 것 a -5.3 b 7.2 c 3.6 d 4.5 e NaN #e는 없었으므로 method='ffill'을 추가하면 여 누락된 값(NaN)을 직전의 값으로 채워 넣을 수 있다 칼럼과 인덱스 둘다 reindex가 가능하다. 1.2.2 하나의 로우나 컬럼 삭제 하기 drop 메서들를 사용하여 선택한 값들이 삭제..