DevMemo

퀀트라는 직업을 아시는 지요? 퀀트는 일반적으로 주식이나 파생상품 등의 매매거래를 알고리즘을 만들어서 컴퓨터로 자동거래를 해서 수익을 내는 직업을 말합니다. 퀀트라는 직업이 나온지는 꽤 됐지만 그리 친숙하지 않고 실제로 어떤 알고리즘으로 자동 매매를 하는지를 알기는 어렵습니다. 프로그래머라고 해도 주식 매매를 할 때 HTS로 거래를 할 뿐 알고리즘을 만들어서 거래를 하는 사람은 소수인 듯 보입니다. 단지 가끔 알고리즘 대회 수상자 몇몇이 월가로 넘어가서 퀀트를 한다는 소문이 들리기도 합니다. 자동 매매라는 것을 찾아보면 최근에 파이썬으로 주식 자동매매을 하는 것이나 가상 화폐를 자동매매 하는 것을 찾아볼 수 있습니다. 솔직히 여기서 쓰는 매매 알고리즘은 보통 단순한 경우가 많습니다. 솔직히 저걸로 얼마나..

백준 문제 방사형 그래프에 대한 풀이입니다. 기하 관련 문제인 관계로 기하 관련 알고리즘을 몰라 관련 지식만 공부하고 풀이 알고리즘을 디자인하였습니다. 어차피 문제 풀이도 공부하고 브루트포스로 할 경우 시간이 너무 걸릴거 같아 괜한 시간 버리기 싫어 그냥 풀이를 참조하기로 하였습니다. 그래서 검색해서 아래와 같은 풀이를 보았습니다. [백준 25308] 방사형 그래프 이 풀이를 보고 결국 이 문제는 브루트포스로 하여도 된다는 것을 깨달았습니다. 이 분의 풀이는 굉장히 좋은 발상으로 푼 거 같았습니다. 하지만 이 분의 방법은 백준에 있는 힌트인 "CCW 문제와 어떤 알고리즘을 조합해야 이 문제를 풀 수 있을까요?"하고는 맞지는 않는거 같았습니다. 개인적으로는 이 분이 설명하신 알고리즘으로 모든 볼록다각형을 ..

알고리즘 수업 - 점근적 표기 1 이 문제는 실버V 수준의 어렵지 않은 문제입니다. 그런데 제출된 풀이가 계속 맞지 않아 결국 시간 절약을 위하여 풀이를 참조하였습니다. 그런데 도저히 다른 사람의 풀이가 명확히 이해가 가지 않았습니다. 답만을 맞추는 것을 실력향상에 도움이 되지 않기 때문에 결국 수학적으로 혼자 다시 풀었습니다. 이 문제의 다른 분들의 풀이에 의문을 가지실 저와 같은 사람이 있을거 같아 풀이를 적기로 하였습니다. 이 문제 풀어보지 않은 분들은 위 링크를 따라 먼저 혼자 풀어볼 것을 권장합니다. 우선 이 문제는 아래와 같은 표기 법을 검증하는 문제입니다. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 문제에서 아래..

ACM 문제를 다루고 있는 유명한 책입니다. 원래는 한국정보올림피아드 혹은 국제정보올림피아드 대회를 준비하는 분들이나 공부하실 책이었습니다. 이런 것이 구글이 뜸과 동시에 구글 면접 문제가 뜨면서 동시에 유명해지기 시작했습니다. 비슷한 시기에 비슷한 유형의 4문제짜리 넥슨의 테스트 문제도 같이 유명해졌습니다. 이 책은 심화학습용 문제지이지 초보들이 무턱대고 풀 수 있는 문제지가 아니라는 것을 알아야 합니다. 우선 자료구조와 알고리즘 기본 정도는 알고 있어야 합니다. 자료구조 학습에 관하여... 이 책에 들어가기 전에 자료구조를 탄탄히 해두는 것이 중요합니다. 자료구조는 많이 알면 알수록 프로그래밍에 도움이 많이되는 관계로 어떤 책을 사던지 끝까지 정독하는 것이 중요합니다. 저는 대학교 교재가 원서였던 관..

1. 두 자료구조체의 비교 -------------------------------------------------- Array Array의 장점은 우선 O(1)의 검색시간을 갖아 자료구조 중에 가장 빠릅니다. 대신 단점으로 크기가 고정되어 적은 크기를 잡을 경우 새롭게 메모리를 할당하고 기존 메모리의 내용을 새로운 메모리로 복사한 후 기존 메모리를 지워야 하는 문제가 발생합니다. c의 realloc 함수는 아마 이런 식으로 구현되어 있을 것입니다. 반대로 크기를 크게 잡을 경우 사용하지 않는 메모리 부분에 대한 낭비가 발생합니다. 다음 단점으로 Array의 중간에 데이터를 삽입할 경우 삽입데이터 뒤의 내용들을 모두 뒤로 복사해야 하는 문 제가 발생합니다. 메모리 복사 시간을 소모하게 됩니다. Linke..

네트워크 흐름 문제(Network Flow Problem)은 일종의 그래프를 응용한 문제입니다. Programming Challenge를 풀다가 이해가 가지 않아 찾아 보았습니다. Programming Challenge 번역판의 설명은 원서가 이상한 건지 번역이 이상한건지 읽어도 읽어도 뜻을 이해할 수 없었습니다. 혹(?) Programming Challenge 번역판의 설명만으로 모든게 다 이해되는 분...? 공감? 네트워크 흐름 문제에서 가장 중요한 것은 가중치 그래프에서 간선(Edge)의 값의 의미를 이해하는 것입니다. 일반적인 가중치 그래프 문제에서 간선(Edge)은 해당 간선을 이동하기 위한 소요 비용으로 간선의 가중치 전체를 사용합니다. 하지만 네트워크 흐름 문제에서 가중치는 허용 가능한 크기..

주기적인 두 이벤트가 동시에 일어나는 주기 구하기 -> 최소공배수 올해 생일의 요일을 알고 있을때 내년 생일의 요일을 구하기 -> 365/7의 나머지를 요일에 더해주면 된다. RSA 알고리즘 -> 메시지를 어떤 정수 m으로 코딩한 다음 k승을 구하는데, k가 공개 키또는 암호화 키이다. 그리고 결과를 n으로 나눈 나머지를 구한다. m,n,k는 모두 매우 큰 정수이다. 결과적으로 m^k mod n을 모듈러 계산을 활용하여 효율적으로 구해야 한다.

이 책은 미국 유명 SW회사 면접을 준비하기 위한 책인 듯 보인다. 내용적으로 크게 두가지로 나누어져 있다고 볼 수 있다. 한부분은 구직활동, 이력서 작성, 면접 등의 과정에 대한 서술과 다양한 팁이다. 그리고 다른 반쪽인 본론인 다양한 면접 문제의 종류와 샘플 그리고 풀이법으로 이루어져 있다. 이 책의 번역 수준은 좋으나 언어적 체계가 우리와 달라 풀이법이 언어적으로 한눈에 들어오지는 않는다. 또한 425 페이지 밖에 안되는 짧은 책이지만 수학적 혹은 논리적인 사고를 많이 요구하는 관계로 수학책을 읽는 것 만큼이나 진도는 천천히 나간다. 그럼에도 불구하고 이 책은 읽을 가치가 있는 책이다. 읽으면서 저자들에 대하여 생각하는 프로그래머들 같다라는 것이 느껴지기 때문이다. 면접 문제지만 현업을 하다보면 마..