PS와 개발을 공부하자

큰 수 N의 모든 약수를 구하는 방법.큰 수라는 것은 int 의 범위를 넘으면서 long long 의 범위는 넘지않는 정도의 크기를 가진 수라고 생각하면 된다.약수를 구하는 가장 쉬운 방법은 1부터 N 까지 모두 돌며 N 을 나눈 나머지가 0인 것을 모두 찾으면 된다.하지만 N이 매우 크기 때문에 O(N) 으로는 구할 수가 없다. 그렇다면 어떻게 할까약수들의 특성중의 하나는 서로 짝을 이룬다는 것이다. 다시말해서N의 약수 i 가 있으면 N/i 도 약수라는 것이다. 그렇기 때문에 i가 N^0.5 를 넘어가면, 만약 약수가 존재하더라도 어차피 앞에서 봐준 것이기 때문에 또 봐줄 필요가 없다. 즉, N^0.5 까지만 반복하면서 N 을 나눈 나머지가 0인 수 i를 찾고i 를 찾았다면 N/i 도 같이 찾아주면 된..

http://codeforces.com/contest/803/problem/C N,K = K*(K+1)/2 냐 라는 말이 같고먼저 GCD를 정해주고 이 GCD로 strictly increasing 하는 K개로 분리가 가능한지즉, 고정된 GCD로 K개의 수를 각각 나눠서 모두 더한 값이 K*(K+1) 보다 크거나 같은지를 판단하기만하면되기 때문에GCD를 최대로 하기위해 가능한 가장 큰 GCD부터 가장 작은 GCD까지 반복하며 가장 큰 GCD를 찾은 뒤N을 그 GCD로 나눠서 strictly increasing 한 K개의 수를 만들고(1,2,3,... 처럼 1씩 증가시키다가 마지막 K번째 수에 다 때려박으면됨)K개의 수에 모두 GCD를 곱해주면 답이 될 것이다.만약 N/GCD >= K*(K+1)/2 가 되는..

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3148 K

BOJ 9359번 : 서로소 1

(해싱에 대한 개념은 제 개인적인 생각이 많이 섞여있어서 틀린 내용이 있을 수도 있다는 것을 미리 밝힙니다.) 해싱은 어떤 큰 데이터(스트링, 트리 등)가 있을 때 이 것을 하나의 수로 나타내어 비교를 하기 쉽도록(그리고 빠르도록)할 때 유용하다. 기본적으로 컴퓨터에서 저장할 수 있는 수의 크기의 한계가 존재하기 때문에보통 해시값은 아무리 커도 long long 범위 내에 들어 와야 한다. 그래서 modular 연산을 사용하게 되는데그러면 문제가 생길 수 있는게 서로 다른 데이터 인데 해시값이 같은 경우가 생길 수가 있는 것이다. 그래서 원래의 해쉬테이블은해시값이 단순히 해쉬테이블의 인덱스를 나타내고 그 인덱스에 실제 데이터가 링크드 리스트와 같은 형태로 연결되어서결국 실제 데이터를 찾는 과정이 필요하기..

이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이 검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인 트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다. 격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고 새로생긴 격자를 흰색으로 채운 뒤 쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고 그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데 압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다. 이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의 노드의 수를 구하는 것이 두번째 요구되어지는 답이다. 우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자. 격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이..

http://codeforces.com/contest/681/problem/E 바퀴벌레의 좌표와 속도, 시간이 주어지고 N개의 접시에 대한 정보(좌표와 반지름)가 주어질 때 바퀴벌레가 접시 안에 들어가면 살 수 있는데 처음에 정한 방향으로만 갈 수가 있을 때, 바퀴벌레가 살 수 있는 확률을 구하는 문제 우선 바퀴벌레의 속도와 시간을 곱하면 바퀴벌레가 갈 수 있는 최대 거리가 되며, 바퀴벌레의 위치를 중심으로하고 반지름이 최대 거리인 원을 그렸을 때 접시들과 겹치는 방향들의 seq 들의 합집합의 각도들의 합에 대해 2π 로 나눠 주면 답이 된다. 일단 하나의 접시에 대해서만 생각해 보자. 우선 바퀴벌레의 이동가능 범위 원과 접시가 겹치지 않는다면 이 접시는 살 수 있는 확률을 전혀 증가시켜 주지 않는다. ..

https://community.topcoder.com/stat?c=problem_statement&pm=11476 N

https://community.topcoder.com/stat?c=problem_statement&pm=11500 우선 문제는 흔히 알고있는 '사천성' 이라는 게임을 최소한의 턴 수로 클리어 하기 위해 필요한 턴 수의 기대값이다.그냥 그때 그때 최적의 선택을 할 때 클리어 하는 데 필요한 턴 수의 기대값이라고 생각하면 될 것 같다. 처음에 실수할 수 있는 것이 뭐냐면.. 실제로 게임을 할 때 뒤집혀 있는 두개의 칸을 선택하면 이 두개가 동시에 뒤집히는것이 아니라 하나씩 선택을 하는데, 하나를 선택하면 이것이 뒤집하고 이 정보를 바탕으로 더 최적의 선택을 할 수가 있기 때문에 답이 다르게 나온다는 사실이다. 문제에서 플레이어는 한번 뒤집었던 칸의 모양은 평생 기억한다고 되어있기 때문에 클리어 까지 필요한..

이 문제는 M개의 트리가 주어지고 각각의 트리에 대해 하나의 엣지를 선택하여 오른쪽 트리에게 주었을때(마지막 트리는 맨 처음 트리에게 준다.) 각 M개의 트리가 여전히 모두 트리가 되도록 간선을 선택하는 모든 경우의 수를 계산하는 문제이다. 우선 이 문제는 dp 로 풀 수가있다. 그래서 내가 처음 생각해낸 풀이는 dp[i][u][v] : i-1번째 트리에서 엣지 u-v 를 선택했고 i번째 트리부터 엣지들을 잘 선택했을때 M개의 트리가 여전히 트리인 경우의수 이렇게 하면 각각의 트리의 모든 엣지에 대해 없애보고 이전 트리에서 넘겨준 u-v 를 추가했을 때 여전히 트리가 된다면 선택하고 다음트리로 넘어가는 식으로 구현하면 되고 기저 케이스는 M번째 까지 왔을 때 0번째 트리에서 삭제한 엣지를 저장해 두었다가..