Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다. 나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다. 나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다. 나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다.
나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

가장 먼저 구현한 자료구조는 아니지만 가장 간단하여 첫 게시물로 어울릴 것이라 생각한 pair 입니다.
문제 풀이에 활용도가 매우 높으며 header 내에 있습니다.

This is short(?) summary of the textbook “Art of Multiprocessor Programming” by Maurice Herlihy & Nir Shavit.
A complete set of lecture slides & sample code is available at the textbook’s companion page
This work is licensed under a Attribution-ShareAlike 3.0.

Wait-free Bounded Queue는 atomic fetch_add() 함수를 사용하여 bounded된(사이즈가 정해진) 배열 내에서 값을 enqueue, dequeue 함으로서 작동하는 자료 구조입니다.
여러 enqueue/dequeue 요청이 병렬적으로 들어왔을 때에도 순차적인 처리를 위하여 배열 내부의 원소는 flag를 두고 있으며 해당 flag를 사용하여 enqueue/dequeue 요청을 순차적으로 처리할 수 있기 때문에 wait-free의 성질을 가지고 있습니다.

문제보기

• LIS (Longest Increasing Subsequence) : 최장 증가 부분수열
  LIS란 임의의 수열이 주어졌을 때, 해당 수열에서 몇 개의 수들을 뽑아 만든 부분수열 중 오름차순으로 정렬된(strictly increasing) 가장 긴 수열을 뜻합니다.

이 때 LIS의 길이를 구하는 방법은 크게 세가지가 있습니다.

• DP O(n²)
• Binary Search O(nlogn)
• Segment Tree O(nlogn)

오늘은 이 중 Binary Search, 즉 이분 탐색을 이용해 LIS의 길이와 수열을 찾는 방법을 알아보겠습니다.