자료알고/알고리즘 검색 결과

해당 글 87건
amortized 복잡도 : average complexity와 뭐가 다른가요?

링크는 c++의 vector의 push_back에 대해서 설명한 문서입니다. Complexity가 constant라고 되어 있는데요. 괄호가 떡하니 쳐져 있습니다. amortized time이라고요. 이게 왜 나왔는지부터 예를 들어서 이야기 보겠습니다. vector의 초기 size가 무한대이지 않는 이상 (기본적으로 적절한 size) 최악의 경우에는, O(vector의 size) 만큼 나올 겁니다. 만약에 n개가 있으면 O(n)이 나올 겁니다. 더 정확하게 말하면 linear time 입니다. worst case인 경우에는 그게 맞습니다. 기존에 n개의 item이 있었습니다. capaity 역시 n이였고요. 만약에 grow rate가 2인 경우에, 이 시점에서 push_back이 호출된 경우에, 2배로 ..
자료알고/알고리즘 2020. 7. 16. 01:42
median of median : 피벗을 중앙의 중앙값을 선택한다.

Quick sort, selection을 할 때 pivot을 선택하는 전략을 찾아보면 꽤 많이 나온다는 것을 알 수 있습니다. 이번 시간에는 median of median을 해 보도록 하겠습니다. 중간값의 중간값? sort 구현체를 찾아보면 Median of Median으로 하는 거 같지 않은데, 이건 또 왜 그럴까요? 중앙값부터 보겠습니다. [5, 3, 6, 4, 7]의 중앙값은 무엇인가요? 5입니다. 왜냐하면, 이것을 sort를 하면 [3, 4, 5, 6, 7]입니다. 5가 딱 중간에 있기 때문입니다. 크기가 n인 배열을 생각해 보겠습니다. 이것을 우리는 5등분을 하겠습니다. 예를 들어, 배열이 [2, 5, 3, 2, 7, 2, 7, 3, 6, 4, 7, 5, 7, 2, 3, 6, 6, 4, 35, ..
자료알고/알고리즘 2020. 7. 9. 21:44
lis 알고리즘 : lower_bound 이용해서 그리디하게 해결해 봅시다.

lis 알고리즘은, 최장 증가 수열을 구하는 알고리즘입니다. 길이가 n인 수열이 있을 때, 이것을 O(nlogn)에 구할 수 있는 방법은 일종의 그리디를 이용한 것입니다. 물론, 조금 더 어려운 응용 문제를 풀기 위해서는 세그먼트 트리라는 자료구조를 알아야 하지만, 여기에서는 논외로 하도록 하겠습니다. 먼저 전체 소스 코드를 보겠습니다. res는 최장 증가 수열의 길이를 구하기 위한 벡터입니다. v는 문제에 주어진 수열입니다. 문제에 주어진 수열 전체를 돌면서, 먼저 lo 값을 구하고 있습니다. 이 lo 값은 res에서 v[i]보다 크거나 같은 최초의 위치를 찾습니다. 그 위치가 res의 크기와 같다면, res의 뒤에 추가합니다. 그렇지 않다면, res[lo]값에 v[i]를 갱신합니다. 일단 전체 시간 ..
자료알고/알고리즘 2020. 6. 17. 02:19
카카오 호텔 방 배정 : map 을 이용해서 깔끔하게 처리합시다.

카카오 호텔 방 배정 문제를 보겠습니다. 우리는 이 쿼리에 대한 답을 효율적으로 처리해야 합니다. 단, 방의 갯수는 10^12개 이하입니다. 10^12개에 대한 정보를 모두 담을 수는 없습니다. 어떻게 해야 할까요? 대신에 우리는 이런 아이디어를 하나 생각해 볼 수 있습니다. 그러면, 구간 정보를 어떻게 담아야 할까요? 방이 총 5개가 있다고 생각해 보겠습니다. 먼저, 초기 상태는 모든 방이 비어 있을 겁니다. 그러면, [1,5]가 비어 있었다는 정보를 넣습니다. 이제, 3보다 크거나 같은 비어 있는 방 중에서, 가장 작은 번호를 가지는 방을 빼 보겠습니다. 이를 K=3인 쿼리라 하겠습니다. 그러면 이 때 어떻게 나누어 질까요? 구간이 [1,2] [4,5]로 나누어 집니다. 이것을 어떻게 관리해 볼까요?..
자료알고/알고리즘 2020. 5. 9. 15:37
event driven : ps 문제에서 간단하게 활용해 봅시다.

이벤트를 넣어두고 그것을 활용한다. 작년에 스터디를 하면서 처음 들어본 말이였습니다. 사실, Java에서 mouse event listener와 같은 것이나 call back 패턴에서만 쓰이는 줄 알았기 때문입니다. 그런데, 특정 문제에서 이것을 잘 활용하면 생각보다 간단하게 풀 수 있습니다. Egg라는 문제를 보도록 하겠습니다. 이 문제를 간단하게 설명하면 아래와 같습니다. 생각보다 쉽지 않습니다. 그런데, 점들이 삭제되거나, 생성되는 이벤트가 주어지지 않으므로, 다음의 발상을 생각해 볼 수 있습니다. 사실, 이것만 계산을 하면, 문제에서 요구하는 쿼리도 해결할 수 있습니다. 이것을 어떻게 해결하면 좋을까요? 보라색 영역에 점이 있다고 해 보겠습니다. 우리는 x좌표가 A 이하이고, y 좌표가 B 이하인..
자료알고/알고리즘 2020. 5. 1. 17:58