알고리즘 검색 결과

해당 글 51건
다익스트라 알고리즘 : 이미 결정된 노드의 인접 노드를 또 탐색하면 어떻게 될까요?

이 글을 읽기 전에 잘못 구현된 다익스트라 글을 보고 오시는 것 추천드립니다. 저는 그 글을 읽으셨고, 그 글에 나온 저격 데이터가 어떠한 원리로 작성되었는지 30% 정도 이해했다는 전제 하에 진행하도록 하겠습니다. 보통 이 알고리즘을 구현하실 때 Priority Queue를 이용하는 경우가 많습니다. 저는 그것을 기준으로 작성하였습니다. min_cost와 where_is_from, visit와 con이 있습니다. 이 중에서 con은 graph를 구축하는데 쓰이는 자료구조 정도로 생각하시면 됩니다. C++의 STL에서 vector con과 같습니다. min_cost를 inf로 초기화 합니다. 그리고, where_is_from을 -1로, visit를 false로 초기화를 합니다. 다음에 pq에 시작점을 넣..
자료알고/알고리즘 2020. 8. 11. 23:50
슬라이딩 윈도우 알고리즘 : 2개의 커서가 중요하다.

제가 응원하는 롯데랑 키움 경기 보느라 지금 글을 씁니다. 둘이서 경기하면 어떻게 하냐고요? 그건 좀 난감한 질문이네요. 뜬금없이 야구 이야기를 하다니. 오랫만에 ps에서 쓸 법한 알고리즘을 해 보겠습니다. 슬라이딩 윈도우라고, 코테에서 은근히 나오는 친구가 하나 있습니다. 톡에서도 질문을 받았었고요. 그것만 잠깐 해 보도록 하겠습니다. 아래의 문제를 생각해 보겠습니다. 길이가 n인 배열이 있습니다. 이 중에서 (부분 순서하고는 다른) 부분 배열을 뽑을 건데 제가 좋아하는 팀인 롯데는 1번 이상, 키움은 2번 이상 나와야 합니다. 그러한 조건을 만족하는 최소 부분 배열의 길이는 어떻게 될까요? 라는 문제를 생각해 보겠습니다. 일단 brute한 해결책을 먼저 생각해 보겠습니다. 0번 인덱스를 기준으로 보면..
자료알고/알고리즘 2020. 7. 29. 01:09
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
카카오 호텔 방 배정 : map 을 이용해서 깔끔하게 처리합시다.

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