1. 반복문으로 구현하는 세그먼트 트리 세그먼트 트리 기본 버전은 재귀함수로 구현되어 있다 import math def create_segment(A,tree,tree_index,start,end): if start == end: tree[tree_index] = A[start] else: mid = (start+end)//2 create_segment(A,tree,2*tree_index,start,mid) create_segment(A,tree,2*tree_index+1,mid+1,end) tree[tree_index] = tree[2*tree_index] + tree[2*tree_index+1] def query_sum(tree,tree_index,start,end,left,right): if lef..
1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..
1. 문자열의 부분 문자열 중 가장 긴 palindrome의 길이 찾기 abaccaba와 같이 뒤집었을 때 결과가 동일하다면, 그러한 문자열을 palindrome이라고 부른다. 문자열이 하나 주어졌을때, 해당 문자열의 부분 문자열 중 가장 긴 palindrome의 길이를 구하고자 한다. 예를 들어 bananac의 부분 문자열 중 가장 긴 palindrome은 anana로 길이가 5이다. 1-1) 완전탐색($O(N^{3})$) 이 문제를 가장 쉽게 해결하는 방법은 문자열을 순회하면서 가능한 모든 경우에 대해 완전탐색을 수행하는 것이다. 문자열을 앞에서부터 순회하면서, 시작점 후보를 정하고, 나머지 모든 문자 각각을 끝 점 후보로 설정할 때, 좌우대칭인지 여부를 판별해서 길이가 가장 긴 후보를 구하는 방법 ..
1. 문제 18869번: 멀티버스 Ⅱ (acmicpc.net) 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 2. 풀이 문제 이해하는것부터 쉽지 않았다 m개의 줄마다 리스트 A를 입력받아서 전체 리스트 universe에 저장해두고, universe에서 i,j 2개를 선택해서, (i universe[j][b]를 만족해야한다. -----..
1. 문제 25342번: 최대 최소공배수 (acmicpc.net) 25342번: 최대 최소공배수 $N = 3$인 경우, $1, 2, 3$을 선택하면 최소공배수는 $6$이다. $N = 4$인 경우, $2, 3, 4$를 선택하면 최소공배수는 $12$이다. www.acmicpc.net 2. 풀이 3개의 수의 최소공배수가 최대가 될려면 어떻게 해야할까 두 수 a,b의 최소공배수는? a = Gn이고 b = Gm으로 표현할 수 있다면(G는 a,b의 최대공약수, n,m이 서로소) a,b의 최소공배수는 L = Gnm이다. 이 최소공배수가 가장 클려면 어떻게 해야할까? L = Gnm이므로, L = am이거나 L = bn으로 표현할 수 있다. 이 둘은 모두 ab보다 작거나 같다. 따라서, L
1. 문제 17427번: 약수의 합 2 (acmicpc.net) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 2. 풀이 문제를 요약하면 1부터 n까지 각각 약수의 합을 전부 더한 값을 출력하는 문제 시간이 0.5초라서 당연히 1부터 n까지 소인수분해하고 약수의 합을 구한다면 시간초과겠지 약수의 합을 구하는 공식은... https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
