자료알고 검색 결과

해당 글 130건
슬라이딩 윈도우 알고리즘 : 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
스택계산기 구현 : 연산자 우선순위와 결합 순서만 생각해 봅시다.

안녕하세요. 오늘은 간단하게 스택 계산기 프로그램을 만드려고 합니다. 일단 괄호가 없는 유효한 식은 숫자 (연산자 숫자)* 이런 패턴으로 들어올 겁니다. 예를 들어 3도 유효한 계산 식입니다. 그리고, 3*7-2도 유효한 식입니다. 연산자는 *과 +, -만 들어온다고 가정해 보겠습니다. 먼저 우선순위부터 set 하도록 하겠습니다. *는 +, -보다 우선순위가 높으니, *의 priority를 0으로, +과 -를 1로 설정하였습니다. 11번째 줄이 그러한 일을 수행합니다. 그리고, ArrayList인 num과 op는, 수식으로부터 들어온 수와 연산자를 순서대로 넣어놓았습니다. 예를 들어서 2-3+7이 들어왔다면, num에는 2, 3, 7 순서대로 들어가고, op에는 -와 +이 순서대로 들어가 있습니다. 이제..
자료알고/자료구조 2020. 7. 2. 02:21
java에서 STL의 multimap 구조를 구현해 봅시다.

C++의 STL에서 multimap은 상당히 유용하게 쓰입니다. Java에서는 그렇게 쓸 수 없을까요? 저는 Key값이 중복되는 경우에도, Map 계열에 저장하고 싶습니다. 어떻게 하면 좋을까요? 그 전에 Java의 Map 계열이 어떻게 동작하는지 간단하게 정리하고 가겠습니다. map.find(K)를 호출했을 때 개략적인 흐름을 보겠습니다. 먼저, map 계열이 키가 K인 값을 찾는 구조입니다. 그러면, 자료구조에서 Key가 K인 것을 찾는데, 이 작업을 하기 위해 내부적으로 호출되는 메서드가 equals입니다. put(K,V')가 호출되었을 때, Key가 K인 것이 존재했다면, 데이터 를 가 같이 저장될 수 없습니다. 예를 들어, K가 가수이고, V가 발매한 앨범이라고 해 보겠습니다. Key dupli..
자료알고/자료구조 2020. 6. 24. 02:12