알고리즘 검색 결과

해당 글 51건
c++ unique 함수 : 정렬을 먼저 해야 중복이 제거된다.

좌표 압축이라는 기술이 있다고 들었습니다. 물론, 저는 ps를 하지 않아서 잘 모르겠습니다. 좌표 압축을 위해서, 중복을 제거해야 하는데요. 그 때 많이 쓰는 함수가 sort + unique + erase 조합입니다. 아마도 그러리라 생각이 듭니다. 물론 set, map도 됩니다만. 이것은 제 전문이 아니니 논외로 하겠습니다. 이 중, unique가 어떻게 동작하는지 이해해 보도록 하겠습니다. cpp reference 코드에 나온 코드는 아래와 같습니다. 아. 보기만 해도 힘드네요. 일단, result, first, last 세 개가 있습니다. 이 셋을 기준으로 보도록 하겠습니다. 보통 unique를 쓰실 때, unique(v.begin(),v.end()) 이런 식으로 쓰실 거니, last는 자료구조의 ..
레퍼런스/분석 2019. 11. 28. 18:36
leetcode 898 bitwise ors of subarrays : 집합이 추가만 되는 상황을 생각해 봅시다.

크기가 5만 이하인 배열 array가 있습니다. 여기서, 연속적인 부분 배열들을 생각할 수 있습니다. 이 부분 배열에 속해있는 수들을 모두 bit or을 합니다. 그렇게 해서 나온 결과값들을 벡터 res에 담습니다. 벡터 res의 중복을 제거했을 때, res에는 몇 개의 수가 들어 있을까요? 즉, 연속적인 부분 배열들의 결과값이 될 수 있는 수의 갯수는 몇 개일까요? 단, 배열 안에 있는 수는 0이상, 10^9 이하의 정수 입니다. 예를 들어, [1, 3, 2]를 생각해 봅시다. 이 경우, 결과값이 될 수 있는 수는 1, 2, 3. 이렇게 3개입니다. 어떻게 풀면 좋을까요? 일단, 0이상, 10^9 이하의 정수라는 것은, 있을 수 있는 최대 상태 수가 30개라는 것입니다. 그러면, lo번째 위치에, 어떠..
자료알고/알고리즘 2019. 11. 23. 00:51
그리디 알고리즘 : 매 순간 최적의 해를 선택한다.

greedy는, 욕심쟁이라는 뜻입니다. 이름에 걸맞게, 매 순간 제일 매력적인 해를 택하는 방법입니다. 그런데 그게 best한 답일까요? 답은 그럴 수도 있고 아닐 수도 있다는 것입니다. 오늘은 이러한 approach로 풀 수 있는 문제 중에서 쉬운 문제만 소개해 드리도록 하겠습니다. 작업 n개가 주어집니다. 이들을 끝내는 데 걸리는 시간이 있습니다. 각각 T(1), ... ,T(n)이라고 합시다. 우리는 제한시간 limit 내에 최대한 많은 작업을 끝내려고 합니다. 어떻게 하면 좋을까요? 직관적으로 생각했을 때, 선택하지 않은 작업들 중에서, 소요 시간이 제일 짧은 작업들을 매 순간마다 선택하면 될 거 같습니다. 그러면 T 배열을 정렬하면 될 겁니다. 예를 들어 T = [2, 5, 1, 3, 7] 이라..
자료알고/알고리즘 2019. 10. 26. 18:58
셀 정렬 : 갭을 줄여가면서 해결한다.

삽입 정렬의 복잡도는 O(n^2)입니다. 물론 평균 복잡도 또한 O(n^2)입니다. 물론, memcpy 등으로 실행 시간을 빠르게 할 수 있는 여지는 있지만, 거기까지일 뿐입니다. 다만, insertion sort의 장점도 있는데요. 거의 정렬된 데이터에 대해서는 상당히 빠르게 동작한다는 장점이 있어요. 하지만, 한 번에 한 요소씩. 비교 1번 할 때 마다, 1요소씩만 move 하기 때문에 효율적이지 않은데요. 이를 보완하기 위해서 gap이라는 변수를 둡니다. 그러면 먼저 init 함수를 봅시다. 먼저, si 라는 벡터가 있습니다. 여기에 무슨 값들이 들어있는지 봅시다. 1, 4, 13, 40, 121, 361, 1093, 3280, ... 네. 이런 값들이 들어 있는데요. gap으로 쓸 겁니다. 예를 ..
자료알고/알고리즘 2019. 10. 14. 01:24