자료알고 검색 결과

해당 글 130건
등차수열에서 중간에 빠진 수 구하기 : binary search 기법으로 풀면 된다.

오늘 새벽에 들어온 문제 하나 보겠습니다. 당연하게도, brr은 오름차순으로 sort가 된 상태입니다. 쉬운 문제는 아닙니다. 다만, 아이디어를 얻을 수 있는 것 중 하나는 이진 검색이라는 것이 있어요. 링크 들어가셔도 좋을 듯 싶어요. 이것을 아신다는 전제하에 설명을 드리도록 하겠습니다. 먼저, 등차 수열 {a(1), a(2), ... , a(n)}이 있다면 임의의 1= 0일 때, a = 0이고 b = 1이거나, 혹은 a = 1이고 b = 0이여야 합니다. 그러면, 좌측에서 수가 빠지지 않았다면, 우측에서 탐색을 해야 하고, 반대로, 좌측에서 수가 빠졌다면, 왼쪽 구간을 탐색해야 할 거에요. 데이터를 볼까요? 문제를 보면, arr[mid] - arr[le]의 값은 8입니다. ..
자료알고/알고리즘 2019. 12. 10. 03:43
k번째 숫자 구하기 : 트라이(Trie) 구조를 이용해 봅시다.

수 x가 추가되고 제거됩니다. k번째로 작은 수를 구해야 하는 쿼리가 있습니다. 아니면, 수 x가 있는지 찾아야 합니다. 어떻게 해야 할까요? 물론, offline이 가능하면 정렬하고 좌표 압축한 다음에 세그먼트 트리를 돌릴 수 있어요. 하지만, online으로 해결해야 하는 경우, 정렬 후 좌표압축 스킬이 통하지 않습니다. 이 때, 우리는 수 x를 32bit 범위 내라면 32, 64bit 범위 내라면 길이 64의 2진수 문자열로 변환할 수 있습니다. 이 때, 우리는 Trie라는 자료구조를 생각할 수 있습니다. 이 Trie는 올해 카카오 4번에 나왔던 structure 이기도 합니다. Skip List는 상대적으로 구현하기 까다로우니, 논외로 합시다. 예를 들어서, 13을 넣는다고 생각해 봅시다. 그러면..
자료알고/자료구조 2019. 12. 5. 20:12
프로그래머스 크게 만들기 : 쿼리 특징을 잡아봅시다.

자료구조는 어떻게 공부해야 하는가? 사실 명확하게 답을 드리지는 못하겠습니다. 문제 상황이 다르게 바뀌었을 때, 어떤 구조로 어떻게 optimize를 시켜야 하는지 생각해 보면, 생각보다 도움이 많이 될 듯 싶어요. 프로그래머스에는 '큰 수 만들기' 라는 문제가 있는데요. 이것을 어떻게 해결해야 하는지. 그리고 들어올 수 있는 문자 집합이 커지면 또 어떻게 해결해야 하는지 천천히 보도록 하겠습니다. 문제는 아래와 같습니다. 단, 남은 수들의 순서는 바뀌면 안 됩니다. 이 문제의 조건만 조금 바꿔서, 소문자로만 이루어진 길이 ? 이하의 문자열에서 ?개를 지워서, 사전순으로 가장 앞선 것을 만들라는 문제가 코테에 출제 되었습니다. 문자 집합만 다를 뿐이지, 풀이 자체는 동일하다는 거 보이시나요? k개를 일일..
자료알고/자료구조 2019. 11. 27. 18:52
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