분류 전체보기 검색 결과

해당 글 904건
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
바빌로니아 법 알고리즘 : 어떻게 sqrt 함수를 구현할까요?

sqrt를 어떻게 계산하면 좋을까요? 사실 어셈블리 명령에 fsqrt가 있긴 합니다. 그리고 추후에, 오늘 설명한 방법하고 Compare를 해 볼 겁니다. 우리는 sqrt(k)의 값을 구하는 것이 목표입니다. 어떻게 하면 좋을까요? 2차 방정식을 생각해 봅시다. 위 그래프는 f(x) = x^2 - 2의 그래프입니다. f(x)와 x축이 만나는 두 점을 (a,0), (b,0)이라고 둡시다. a
자료알고/알고리즘 2019. 11. 20. 23:41
mysql timediff 함수 : 두 시간의 차이를 계산한다.

DATETIME, TIME의 차이를 계산할 수 있는 방법이 없을까요? mysql에는 timediff 함수가 있습니다. 이것은 2개의 datetime/time의 차이를 time 자료형으로 리턴해 주는 함수입니다. 당연하게도, 2개의 자료형은 같아야 합니다. timediff(T1,T2); T1과 T2의 차이를 돌려줍니다. 만약에 T1보다 T2가 더 나중에 있는 시간이라면 -hh:mm:ss를 돌려줍니다. 먼저 아래 쿼리를 봅시다. 이것은 time형 2개를 받았습니다. T1이 2시 3분 4초, T2가 2시 3분 2초입니다. T1이 T2보다 나중에 있는 시간이므로, 결과 값에 -가 붙지 않습니다. T1이 T2보다 얼만큼 나중에 있나요? 2초만큼 나중에 있습니다. 따라서, 00:00:02가 출력이 됩니다. 출력에 ..
코딩/Sql 2019. 11. 19. 17:27
c언어 명령행 인자 argc argv : 옵션을 어떻게 처리할까?

이번 시간에는 명령행 인자인, argc와 argv를 해 보도록 하겠습니다. 사실, 이것이 무엇인지 생소할 수도 있습니다. 아래 ls 명령어를 봅시다. Linux에서 ls는 디렉토리에 있는 파일들에 대한 정보를 출력해 주는 명령어인데요. ls 명령어를 썼는데, 여기서 -a라는 옵션을 추가로 주었어요. 즉, 실행 파일을 실행할 때 옵션을 추가로 받을 수 있다는 의미입니다. 오늘은 이것들을 가지고 간단하게 놀아보도록 하겠습니다. 먼저, 다음과 같이 실행을 했다고 생각해 봅시다. 초록색으로 칠한 것은 실행 파일 명입니다. work를 실행을 한 것입니다. 그리고 보라색으로 칠한 것은 옵션을 의미하는데요. 보라색의 갯수는 5개임을 알 수 있습니다. argc는, 이 보라색의 갯수 + 1과 같습니다. 실행 파일명, 명..
코딩/C 2019. 11. 17. 22:27