plzrun's algorithm

[Ex준비] C++ Radix & Counting Sort

익스시험 볼 때마다 Radix Sort는 template을 사용하지 않고 그때 그때 필요할때마다 짜서 썼는데,한번 구조화 해보고 싶어서 구현해봤다. 막상 시험볼때 보면 int같은 기본타입 sorting하다가구조체 sorting하려고 하면 다시 하나 더 짜야해서 귀찮았는데,구조화를 하니 붕어빵 찍어내듯이 쓸 수 있어서 편한거 같다. ※ 해당 코드 사용하려면 내 블로그에 올린 C++ Vector.h의 코드가 필요하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include "Vector.h"#include using namespace std;template class Less{public:..

Algorithm/Sort 2018. 11. 9. 18:19

[Ex준비] Vector, MaxHeap, MinHeap → .cpp로 구현

Expert하면서 ~.h를 코딩할 일은 없으니까..그냥 한 코드에 다 넣고 코딩해봤다.이제 여러번 하니까 손에 익은 듯 하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135#include #include template str..

Algorithm/Data Structure 2018. 11. 9. 18:14

[Ex준비] C++ Heap.h (priority_queue)

이번엔 Heap.. ※ 해당 코드 사용하려면 내 블로그의 C++ Vector.h가 필요하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107#ifndef __HEAP_H__#define __HEAP_H__#include "Vector.h"template struct Less{ bool operator()(const T& lhs, const T& rhs) const { retu..

Algorithm/Data Structure 2018. 11. 9. 18:06

[Ex준비] C++ Vector.h

안녕하세요, 즈런이에요~ 오랜만에 글을 올리는데,요즘 너무 나태해져서...아무튼 오늘부터 조금씩 손에 코드도 좀 로딩해보려구요.Expert 준비해보려고 편하게 쓰던 STL 종류들 직접 짜보면서 손에 익히는 중이에요. 계속 못따는건 실력이 없어서겠죠 ㅠ한 1년 준비하다보면 되지 않을까요? 아래 코드는 아직 검증해본적이 없어요..그냥 막 짜보는 중입니다.수정해야할 부분 있으면 말씀해주세요. (2020.02.03 수정) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868..

Algorithm/Data Structure 2018. 11. 9. 18:04

삼성 SW검정 (서티/코딩/취업준비) - 자주하는 질문들

자주 하는 질문들만 모아봤어요. 바꿔말하면... 아래 질문은 안했으면 좋겠어요. 또 누군가가 질문하면 계속 추가하겠습니다. Q.1. 저 Java 쓰는데 코딩 테스트 준비하려면 C++을 해야할까요? A.1. 네, C++쓰세요. Java로도 할 수 있는데, Java로도 잘 하는 사람 많은데, Java도 안되는게 아닌데.. 이런 얘기 필요없는것 같네요 그냥 C++쓰세요. 다른 언어는 언급조차 필요가 없어요. 1. 잘짠 대부분의 코드가 C++로 되어있다. 즉, C++로 PS하는게 배우기도 쉽다. 2. 속도가 Java랑 어마무시하게 차이난다. PS에서는 Java의 속도를 어느정도 고려하여 채점하지만 채점자가 사실 그럴 의무도 없고, 사용자도 굳이 느린걸 쓸 이유가 없다. 3. 알고리즘에 필요한..

Tip/이것저것 2018. 10. 11. 22:08

함수 템플릿과 템플릿 함수, 클래스 템플릿과 템플릿 클래스의 차이

What is the difference between a template class and a class template? What is the difference between a template function and a function template? 출처: http://www.comeaucomputing.com/techtalk/templates/#terms 출처에 대한 내용을 간단하게만 적어본다.green house라고 하면 여기서 주체는 house다.다시 말해, 초록색 집이라고 말하면 [초록색깔의 "집"]을 의미하는 것이지 [집이 보유하고 있는 "초록색"]을 의미하는 것은 아니다. 그러므로 template function이라 함은 "함수"를 의미하는 것이고,function template이라..

Programming Languages/C++14 2018. 8. 15. 02:13

구간 업데이트와 구간 합이 모두 O(logN)에 가능한 펜윅트리 (Fenwick Tree Lazy Propagation)

(2019.08.11 수정)요즘 이 글의 검색량이 많아져서 조금 수정을 했다. 일반 펜윅트리(Fenwick Tree)에 관한 설명은 어디에나 많이 찾아볼 수 있다.오늘은 구간 업데이트(Range Update)와 구간 합(Range Sum)이 O(lgN)에 가능한 특별한 Fenwick Tree에 대해서 포스팅해볼 것이다. 제목에 Fenwick Tree Lazy Propagation이라 작성했지만실제로 Segment Tree Lazy Propagation처럼 update시에 점만 찍어뒀다가 query시에 한꺼번에 update하는 방식은 아니다.다만 Segment Tree Lazy Propagation처럼 구간합과 구간쿼리가 모두 O(logN)에 가능하다는 뜻으로 썼다. 일반 펜윅트리: https://www...

Algorithm/Data Structure 2018. 8. 4. 18:08

Codility Award

오늘 회사 동기 형에게 Codility라는 사이트를 처음 알게되어서 문제를 풀게 되었다.사실 형이 이전부터 몇번 얘기했기 때문에문제푸는 또 다른 사이트가 있다는건 이전부터 알고 있었지만,직접 문제를 풀어본건 오늘이 처음이었다. 아무튼 이 사이트는 아주 멋있는 Certificate을 주는데,Linked In에 자격 증명같은 것으로 기재할 수 있어서 좋은 것 같다. https://app.codility.com/cert/view/certW7DBE5-B9Y3AJDA2SFJW7YT/ 뭔가 매번 풀어서 저 증명서 같은걸 받고 싶다는 생각이 든다.

PS - OJ/Codility 2018. 7. 8. 22:44

에라토스테네스의 체를 이용한 빠른 소인수분해

에라토스테네스의 체(The Sieve of Eratosthenes)를 아직 모른다면 저의 이전 포스팅을 참고하시기 바랍니다.(http://plzrun.tistory.com/entry/폐구간1n-소수-구하기-에라토스테네스의-체-The-Sieve-of-Eratosthenes) [1,N]값에 대해 소수인지 판별하는 방법인 '에라토스테네스의 체'를 이용하면,[1,N]값에 대해 소인수분해를 빠르게 할 수 있다. 방법은 매우 간단하다.1부터 N까지 가장 작은 인수(factor)를 에라토스테네스의 체를 이용하여 구하는 것이다.이 값을 minFactor라 하자. (어떤 값 x의 minFactor는 minFactor[x]로 나타낸다.)그러면 임의의 x값을 소인수 분해하..

Algorithm/Mathematics 2018. 7. 1. 23:15

폐구간[1,n] 소수 구하기 (에라토스테네스의 체 - The Sieve of Eratosthenes)

소수를 일반적인 방법으로 구한다면 아래와 같이 구할 수 있다.어떤 값 N이 소수임을 판별하기 위해서는 2부터 N-1까지의 수로 나눠보면 된다.이는 O(N)의 시간복잡도를 갖는다. 만약 1부터 N까지의 숫자가 소수임을 판별하기 위해서는위와 같은 방법으로는 만큼의 시간이 걸린다. 이보다 빠른 방법은 없을까?그 방법이 '에라토스테네스의 체'이다. (시간복잡도는 이다.) 1부터 10만까지의 숫자중에 소수인 숫자를 골라내려고 할 때,에라토스테네스의 체를 이용하여 구하는 방법은 아래와 같다. 2부터 시작한다.2는 소수인데, 2x (x>1)는 소수가 아니다.그러므로 우리는 2를 약수로 갖는 모든 숫자를 체크할 수 있다.이는 소수가 아닌 숫자를 체크하는 것인데,간단하게 C++..

Algorithm/Mathematics 2018. 7. 1. 22:59