전체 글 검색 결과

해당 글 904건
평방 분할 (Sqrt Decompositon) : 루트로 쪼개보자.

세그먼트 트리를 모를 때, k번째로 빠른 수를 어떻게 찾아야 할 지 모를 때, 어떤 방법을 쓰면 좋을까요? n이 적당히 크다면, 우리는 이런 아이디어를 생각해 볼 수 있습니다. 구간이 n개가 아닌 sqrt(n)개. 그리고, 구간 별 원소 갯수도 sqrt(n)개. 사실, 이것을 응용한 알고리즘이 Mo's algorithm인데, 여기까지 다루지는 않겠습니다. 예를 들어, 배열의 임의의 원소가 구간 [1,9]에 속하는 자연수라고 해 봅시다. 이 때 배열 [1, 3, 3, 4, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9]에서, 13번째로 작은 수를 찾기 위해서 어떻게 하면 좋을까요? 일단, co[x]는 x가 나타나는 빈도수를 나타낸 겁니다. 그러면 단순하게 생각하면, 누적 값을 더해가면서, 1이 출현하..
자료알고/자료구조 2019. 9. 22. 00:18
mysql unix timestamp 함수 : 기준 시간으로부터 몇 초나 흘렀을까?

어제, datetime에 대해서 잠깐 언급을 했었습니다. 어떻게 하면 두 시간의 차를 잘 계산할 수 있을까요? 예전에 time 함수를 이야기 할 때, 1970년 1월 1일 UTC+0일 때부터 현재까지 흐른 시간이 몇 초인지를 리턴해 준다고 했었습니다. mysql도 이와 동일한 일을 하는 함수가 있습니다. 그 함수는 unix_timestamp입니다. 사용 방법은 아래와 같습니다. 인자로 Date나, Datetime과 같은 것을 넘겨주거나, 아니면 인자를 넘기지 않는 방법이 있습니다. 이 글에서 말하는 기준 시간은 1970년 1월 1일 0시 0분 0초 UTC+0인데요. 제 timezone이 KST+9로 설정이 되어 있어요. 그러면, 실제로 UTC+0 시간대를 쓰는 지역에서는 1970년 1월 1일 0시 0분 ..
코딩/Sql 2019. 9. 20. 19:52
mysql datetime형 : 어떤 타입일까?

mysql에서, 시간을 다루는 데이터 형도 꽤 많습니다. 프로그래머스에, 이런 문제가 나왔었습니다. 테이블 2개가 주어집니다. 입양을 간 동물에 대한 Table이 주어지고, 보호소에 온 동물들에 대한 Table이 주어집니다. 그런데 오늘 제가 날짜에 대해서 합니다. 그러면. 대충 어떤 쿼리가 들어왔는지 감이 오시나요? datetime이 어떤 형인지 봅시다. 먼저, 아래 쿼리를 생각해 봅시다. '2019-09-19 00:00:00'이라는 데이터는 varchar형입니다. 문자열입니다. 저는 이것을 datetime 형으로 변환을 할 건데요. 이를 위해서 cast 함수를 씁니다. 그러면, 이 값이 datetime으로 들어갔을 건데요. Binary가 어떻게 들어갔는지 봅시다. 헥사로 32, 30, 31, 39. ..
코딩/Sql 2019. 9. 19. 21:49
c언어 strtok 함수 : 구분자를 기준으로 문자열을 자른다.

C언어로 코딩하실 때, 파싱 문제를 만날 때 가장 많이 쓰는 함수는 strtok입니다. 물론, 저는 strchr 조합을 더 많이 쓰긴 합니다만. 익혀두면 편한 쪽은 오늘 소개하는 함수입니다. 함수 원형을 소개하지 않겠습니다. 거의 정석처럼 사용되는 패턴 정도만 소개하도록 하겠습니다. 먼저 '#'을 구분자로 끊어내 봅시다. 보시면 strtok의 1번째 인자에는 parsing을 할, 대상체가 들어가 있습니다. 예를 들자면, "abcd#efg#hijk"와 같은 것들입니다. 그리고, 2번째 인자에는 구분자 집합이 들어가는데요. 여기에서 우리는 '#'을 기준으로 자를 것이므로 '#'만 넣었음을 알 수 있습니다. 12번째 줄이 핵심인데요. strtok는 문자열의 포인터를 리턴해 줍니다. 문자열의 끝에 도달하면, N..
레퍼런스/예제 2019. 9. 19. 00:47
생산자 소비자 문제 : 공유 변수를 어떻게 동기화 시킬까?

스레드 동기화 문제 중에, 생산자 소비자 문제가 있습니다. 문제는 매우 간단합니다. 생산자는 물건을 생산합니다. 소비자는 원하는 상품이 있으면 가져갑니다. 그렇지 않으면 기다립니다. productor는, 생산된 물품이 없으면 만듭니다. 이런 문제를 어떻게 해결하면 좋을까요? 일단, 물품이 있는지 없는지 관리하는 변수는 state입니다. 이 값이 1이면 있다는 것이고, 0이면 없다는 것입니다. 이것은 두 쓰레드가 동시에 접근해서 read, write를 하면 안 되는 변수라고 할 수 있어요. 즉, 물건이 있을 때, 꺼내 가려고 할 때, lock을 걸어야 하고, buffer에 집어넣으려고 할 때에도 lock을 걸어야 합니다. 그러면, 소비자 Thread는 다음과 같이 설계할 수 있습니다. 생산자 Thread는..
OS/이론 2019. 9. 18. 15:56