블로그 이사 중입니다 >> gumgood.github.io

원문 : https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ Following are the steps to find all prime factors. 1) While n is divisible by 2, print 2 and divide n by 2. 2) After step 1, n must be odd, Now start a loop from i=3 to square root of n. While i divides n, print i and divide n by i. After i fails to divide n, increment i by 2 and continue. 3) If n is a prime number and..

원문 : https://cs.stackexchange.com/questions/48649 Q. Complexity of union-find with path-compression, without rank Wikipeda says union by rank without path compression gives an amortized time complexity of \(O(\log n)\), and that both union by rank and path compression gives ans amortized time complexity of \(O(\alpha(n))\) (where \(\alpha\) is the inverse of Ackerman funcion). However, it does n..

H. 15606 High Score 일반성을 잃지 않고 a 2xc + x^2는 만족해야 이 경우가 답이 될 수 있습니다. x의 해는 7-2c미만에 존재할 수 있는데 c>=1이므로 x < 5일 때만 살펴보면 됩니다. 따라서 모든 토큰에 각각 0~4까지 더해보면서 최고 점수를 구했습니다. 처음 문제를 봤을 때, 쉬운 문제 같아서 빨리 풀어야겠다는 조바심이 생겼나봅니다. min(a,b,c) > a인 경우를 생각하지 못해 2번의 WA를 받았고, 1시간 쯤 지났을 때 woonikim이 준 힌트를 받아 해결했습니다. B. 15600 Boss Battle 보스가 있을 수 있는 기둥들의 집합을 '후보 기둥'이라고 합시다. 처음 임의의 기둥에서 폭탄을 터뜨리면 후보 기둥은 n-3개가 됩니다. 다음, 보스가 이동하므로 후..

원문 : https://stackoverflow.com/questions/1506078 permutation of n elements가 있을 때, integer로 mapping하는 방법에 대해 설명한다. n!의 permutation이 있을 수 있고, 이를 n!가지의 정수에 1:1 mapping하는 것이 목적이다. n개의 원소로 이루어진 permutation을 설명할 때, 첫 번째 원소가 있을 수 있는 위치는 n가지가 있다. 따라서 이 원소의 위치를 0~n-1 사이의 수로 나타낼 수 있다. 그 다음 원소가 있을 수 있는 위치는 남은 n-1가지이다. 그래서 이 원소의 위치를 0~n-2 사이의 수로 나타낼 수 있다. 이를 위치를 나타내는 n개의 수를 얻을 때까지 계속 반복한다. n=5인 경우를 예로 들어, '..

Today I want to introduce you some very very useful data structures. Trees Trees are one of the most useful data structures. A tree is a connected-acyclic graph. Ther are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc. Partial sum There are two types of problems solvable by partial sum. 1. Problems which you are asked to answer some queries about the sum..

원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속된 부분에 대한 query들을 처리할 때 사용한다. 첫번째 예로 다음 두 명령어를 생각해두자. 1. 배열에 있는 한 원소를 수정한다. 2. 어떤 범위에 대한 원소들의 합을 찾는다. Perfect binary tree 다음은 segment tree를 도식화한 것이다. 표기법은 node_index: corresponding segment [left border included, right excluded)이다, 트리의 leaf에 해당하는 맨 밑에 행은 우리의 배열에 해당한다. Perfect..

양의 정수 N이 2의 지수라고 하자. 길이가 N인 배열 \(a\)의 각 원소를 \(a_i\)라고 하자\((i \in [0, N-1])\). 어떤 원소 \(a_i\)를 수정하는 규칙이 있을 때, 이것을 \(a_x\)와 \(a_y\) 사이 모든 원소들에 적용시킨다고 생각하자. 이것을 Range modification이라고 부를 것이다. 결합법칙(Associative property)과 교환법칙(Commutative property)을 만족하고 항등원(identity element)를 가지는 어떤 이진연산을 예를 들어 \(\times\)로 나타내자. \(a_x\)와 \(a_y\) 사이 모든 원소들간에 연산을 적용한 결과\((a_x \times a_{x+1} \times ... \times a_{y-1} \ti..

Binary Search(이분 탐색)는 일반적으로 간단한 알고리즘에 속한다. 막상 문제를 풀다보면 'exit conditions'나 'midpoint calculation'에 있어서 헷갈릴 여지가 있다. 풀려는 문제의 조건에 따라 미묘한 구현의 차이가 존재하기 때문이다. 이를 명확하게 정리해두고자한다. Algorithm Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. - If the target value matches the middle element, its position in the array is return. - If..