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

해당 글 87건
0-1 bfs 알고리즘 : 가중치가 0과 1만 있을 때 최단거리는 어떻게 구할까요?

가중치가 0과 1만 있는 그래프에서 최단 거리는 어떻게 구할까요? 얼핏 들어서는 그냥 다익스트라를 잘 이용하면 될 거 같습니다. 그런데, deque나 Queue 구조만을 이용해서 코딩을 할 수 있습니다. 이게 어떻게 가능할까요? 먼저, 가중치는 0과 1만 있어요. 그리고 알고리즘 1은 위와 같습니다. 해석해 보면 그렇게 복잡하지 않아요. 시작 지점을 s라 합시다. 처음에는 s까지 최단 거리가 0이다. 라는 정보를 dq에 넣을 겁니다. 그리고, 자료 구조 dq의 앞 부분에서만 정보를 뺍니다. 이 정보는 to까지 min_dist가 cost다. 입니다. to와 인접한 지점을 a라 합시다. 이 때, to로부터 a까지 거리가 0이라면, a까지 거리에 대한 정보를 dq의 앞에 넣고, 아니라면 dq의 뒤에 넣습니다...
자료알고/알고리즘 2019. 12. 12. 20:28
등차수열에서 중간에 빠진 수 구하기 : 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
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
leetcode 338 counting bits : 마지막 켜진 비트만 알면 된다.

leetcode 338번, Counting bits를 풀어보도록 합시다. 1부터 n까지 켜진 비트의 수를 구하려고 합니다. 그런데 이것을 O(n)에 구하려고 합니다. 어떻게 하면 좋을까요? n이 100만까지 있을 때, 20개의 비트를 일일히 보는 것은 꽤 큰 낭비입니다. 이를 어떻게 하면 좋을까요? 이전에 계산했던 정보를 다시 재사용하는 방법은 없을까요? 먼저 dp[x]를 위와 같이 정의합니다. 그러면, dp[0]은 0일 겁니다. 0을 2진수로 표현하면 00..00입니다. 비트 값이 1인 것이 없습니다. 따라서, dp[0]의 값은 0으로 초기화를 합니다. 그러면, dp[x]의 값은 어떻게 구하면 좋을까요? 6을 생각해 봅시다. 이것은 2진수로 0110로 나타낼 수 있습니다. 켜져 있는 비트 1의 수가 몇..
자료알고/알고리즘 2019. 11. 22. 04:02