목록Algorithm/Memo &Tips (25)
블로그 옮겼습니다
이건 확실한건아니고 들은 사실인데 모듈러를 많이하면 생각보다 속도 저하가 있다고한다. 그래서 코포에서 고수들도모듈러 연산을 줄이는 테크닉을 많이 쓴다고 들었는데 ans 를 구할 때 어떤 여러개의 답들을 곱해서 모듈러연산을 한거라면 못쓰고..더해서 구할땐 쓸 수가 있는데 더하는 것들이 둘다 mod 미만이라는 것이 보장되기 때문에아무리 더해봤자 2*mod 미만일 것이다. 그렇기 때문에ans %= mod 를 하는대신while(ans>mod)ans-=mod; 를 하면 while 문이 한번만 돌기 때문에 모듈러를 하는 대신 - 연산을 한번 하게 된다.근데 이게 꽤 성능 차이가 난다고 하는데 아직 나는 겪어 본적이없다.. 어떤 사람이 2초 제한인 문제에서모듈러를 그냥 썼을 땐 TLE 가 났는데 저렇게 while 문..
전까지는 unordered_map 를 선언하고 이 안에 없으면 새로 추가하고 있으면 지나가는 식으로 했는데 코드 줄도 길어지고뭔가 지저분해졌지만 어쩔수 없이 썼었는데 이럴 필요가 없었다.. 보다 깔끔한 방법 두가지가 있다. 첫번째는 unique 라는 함수를 사용하는 것이다.정렬되어있는 벡터의 시작과 끝 iterator 를 인자로 주면 모든 수들을 한번씩만 써서 정렬한 sequence 를 맨앞에 오도록순서를 재배치 하고 그 끝 iterator 를 반환 한다고 한다. 그래서 이렇게한다.12345678910111213#include using namespace std; int main() { vector v({1,1,1,1,2,2,2,3,3,4,4,5,6,7,7,7,7,8,8,9,9,9}); sort(v.be..
큰 수 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 도 같이 찾아주면 된..
(해싱에 대한 개념은 제 개인적인 생각이 많이 섞여있어서 틀린 내용이 있을 수도 있다는 것을 미리 밝힙니다.) 해싱은 어떤 큰 데이터(스트링, 트리 등)가 있을 때 이 것을 하나의 수로 나타내어 비교를 하기 쉽도록(그리고 빠르도록)할 때 유용하다. 기본적으로 컴퓨터에서 저장할 수 있는 수의 크기의 한계가 존재하기 때문에보통 해시값은 아무리 커도 long long 범위 내에 들어 와야 한다. 그래서 modular 연산을 사용하게 되는데그러면 문제가 생길 수 있는게 서로 다른 데이터 인데 해시값이 같은 경우가 생길 수가 있는 것이다. 그래서 원래의 해쉬테이블은해시값이 단순히 해쉬테이블의 인덱스를 나타내고 그 인덱스에 실제 데이터가 링크드 리스트와 같은 형태로 연결되어서결국 실제 데이터를 찾는 과정이 필요하기..
unordered_map, unordered_set 과 같은 해쉬맵 자료구조에서 해쉬값을 만드는데에 사용하는 해쉬 함수의 디폴트가 컴파일러 마다 다른데MSVC++ 에서는 어떤상황에서든 잘 돌아가는데G++ 에서는 디폴트 함수가 하위 16비트만 보고 해쉬값을 만들기때문에 해쉬값은같지만 실제 값은 다른 값들이 많이 존재하는 상황이 발생할 수가 있다고 한다. 이런 최악의경우에 시간 복잡도가 O(N) 이 걸리게 된다는 문제가있다..... 그러므로 입력 데이터가 골고루 나오는경우가 아니거나 hack 이 가능한 탑코더나, 코드포스와 같은 CP 환경에서는 직접 해쉬함수를 정의하여 unordered 의 세번째 인자로 넣어주거나, 굳이 O(1) 에 계산할 필요가없고 편하게 하려면 그냥 set, map 을 쓰자.. 세번째 ..