블로그 이사 중입니다 >> 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개가 됩니다. 다음, 보스가 이동하므로 후..

가로변, 세로변을 분리시켜서 생각하면 편하다. 세로 변의 길이의 합를 구하는 함수가 있으면 직사각형들을 y=x 축에 대칭시켜 같은 함수로 가로 변의 길이의 합도 구할 수 있다. 세로 변의 길이의 합를 구하는 함수를 생각해 보자. Plane sweeping 방법과 비슷하게 진행하는데 직사각형을 추가하거나 삭제하면서 생기는 변의 길이를 센다. 직사각형을 추가했는데 segtree의 query가 늘어났다면 해당 길이에 해당하는 직사각형이 생겨 새로운 변이 생긴 것이고 직사각형을 삭제했는데 segtree의 query가 줄어들었다면 그 길이에 해당하는 직사각형이 끝나 새로운 변이 또 생길 것이다. 주의해야할 점은 직사각형이 삭제됨과 동시에 추가하는 경우 (즉, 같은 크기의 직사각형이 같은 변을 맞대고 있는 경우) ..

작성일 기준 BOJ에서 채점 가능한 문제만 풀어보았습니다. 1번. BOJ 5819 열대 식물원 공식 풀이는 \(O(QN)\)입니다. 이 안에 절대 안될거라 생각했는데 시간 제한을 너무 보수적으로 생각했나봅니다. 아무튼 제 풀이는 \(O(N+M\log M + Q)\)이긴 하지만 대회 문제는 쉬운 풀이가 좋은 풀이라 생각하기 때문에 관심 있으신 분만 읽으셔도 됩니다. 각 연못을 node로 하고 각 산책로에 대해 아름다운 정도를 가중치로 갖는 edge로 directed graph를 구성합니다. 철수가 한 연못에서 다음 연못으로 이동 중인 상태를 '어떤 node \(u\)에서 edge를 거쳐 다음 node \(v\)로 가는 상태'로 볼 수 있습니다. 즉, 철수의 현재 연못과 상태(어느 연못에서 왔는지)는 하나의..

https://www.acmicpc.net/category/detail/1935 A. BOJ 16282 Black Chain 첫 번째 접근법은 'n개의 고리가 연결된 체인에서 m개의 고리를 풀 때 1g부터 ng까지 모든 무게를 생성할 수 있는지' 여부를 판단하는 함수 f를 만들어 풀어야 할 고리의 최소값을 binary search로 찾는 것이었습니다. f를 만들어낸 방법은 다음과 같습니다. m개의 고리를 풀면 1g 고리가 m개가 생성되므로 일단 이것만으로 1g부터 mg까지 모두 생성이 가능합니다. 남은 (n-m)g의 체인은 m+1개 이하의 체인들로 나눌 수 있습니다. 여기서 나눈 체인들은 앞에서 푼 고리 사이에 들어간다고 생각하시면 됩니다. 1g ~ mg의 무게를 만들 수 있을 때, (m+1)g의 체인이..

COCI(Croatian Open Competition in Informatics) 2009/2010 contest #2 https://www.acmicpc.net/category/detail/84 1. BOJ 2914 저작권 앨범의 수록곡의 개수 A와 수록곡 당 멜로디의 개수의 평균값 I이 주어질 때, 적어도 몇 개의 멜로디가 있는지를 묻는다. 이 문제에서는 평균값을 구할 때 올림을 사용하므로 실제 평균 avg.는 I-1 < avg.

원문 : 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인 경우를 예로 들어, '..