분류 전체보기 검색 결과

해당 글 904건
비트 배열 : 공간을 1/8, 1/32, 1/64로 압축한다.

제목이 꽤 도발적인 거 같네요. ps를 하시다 보면 종종 듣는 이야기 중 하나는, 상수 최적화, 혹은 O(n/32)나 O(n/64)입니다. 그것이 공간이 될 수도 있고, 시간이 될 수도 있는데요. 32와 64. 무언가와 연관이 있는 듯 싶습니다. 환경에 따라 다르겠지만, 보통 우리가 흔히 알고 있는 int형, long long형의 bit 수이기도 합니다. 공간을 n/32나, n/64로 compress 하는 문제를 생각해 봅시다. 사실, trie나 set, map을 쓰셔도 됩니다. 그런데 STL을 직접 구현해야 하는 경우, 2번째 것과 3번째 것은 구현하는 데, 상당히 어렵습니다. 1번은 시도해 볼 만 합니다. 그런데 메모리 제한이 128M로 꽤 넉넉하다면 어떨까요? 이 때는 이야기가 달라질 수도 있습니다..
자료알고/자료구조 2019. 12. 24. 05:39
리눅스 diff 명령어 : 파일이나 폴더의 다른 부분을 체크한다.

폴더나 파일이 같은지 다른지 출력하려면 어떻게 해야 할까요? 다른 내용까지 보려면 어떻게 해야 할까요? 리눅스의 diff 명령어는 그것을 위한 명령어입니다. 이런 유틸은 인터넷에도 꽤 많이 있을 정도인데요. 저 같은 경우, 백준에서 (흔히 올라오는 질문 중 하나인) 2개의 소스코드 중 하나는 맞고 하나는 틀리다고 할 경우에 어느 부분이 어떻게 다른지부터 체크하는 편입니다. 이 때 쓸 수 있습니다. 먼저 diff가 어떻게 구현되었는지에 대한 것은, 아니면 그에 대한 알고리즘들은, 나중에 살펴보기로 하고, 이번 시간에는 폴더가 어떻게 다른지, 그리고 파일이 어떻게 다른지 알아내는 방법을 알아보도록 하겠습니다. 먼저, 1과 2 디렉토리가 있습니다. tree 명령어로, 폴더 내에 어떠한 것들이 있는지 출력해 봅..
OS/리눅스 2019. 12. 23. 14:47
백준 팰린드롬 진법 : 후보해는 생각보다 많이 적다.

오늘 풀어볼 문제는 백준 팰린드롬 진법이라는 문제입니다. 난이도는 솔브드 기준으로 G3 ~ G1 정도 되는 문제입니다. x의 범위는 10^9입니다. 어떻게 풀어야 할까요? 먼저, x가 적당히 작은 수일 때에는 굉장히 쉽습니다. 이 때 난이도는 S5에서 S4 정도 됩니다. 그냥 2부터 n까지 z진법이 팰린드롬인지 검사하면 됩니다. zinbup 내부를 봅시다. yuki는 32개짜리 크기의 int형 배열입니다. zinbup 함수가 호출이 될 때 마다, 32개짜리 int형 배열을 초기화 시킵니다. 그리고 cur를 z로 나눠가면서 나머지 값만 계속 취합니다. 59 ~ 62번째 줄이 그러한 일을 수행합니다. p는 z진법으로 나타냈을 때 자릿수인데요. 팰린드롬이라면, 거꾸로 읽으나, 올바르게 읽으나 값이 같습니다. ..
자료알고/알고리즘 2019. 12. 21. 23:07
스파스 테이블 (sparse table) : 2의 거듭제곱 단위로 점프한다.

이런 문제를 생각해 보겠습니다. 뭔가 많이 본 거 같은데, 효율적으로 풀기는 쉽지 않아 보입니다. 왜냐하면 naive하게 구하면, 최악의 경우에, dQ만큼이나 수행해야 하기 때문입니다. 이걸 어떻게 하면 좋을지 먼저 생각해 봅시다. 일단, 자연수 k의 2진수 표현은 유일합니다. 이것부터 보여 봅시다. 귀류법을 써 보겠습니다. 간단하게 상위 비트부터 쭉 저장이 되어 있다고 가정해 봅시다. 만약에 k의 2진수 표현이 2가지 이상이라고 한다면, 분명하게도, 비트가 다른 부분이 존재할 겁니다. 그러면 이 둘의 차이의 절댓값은 2^x보다는 크거나 같을 겁니다. 이제 보라색 부분을 봅시다. 가정이 성립하려면, 보라색 부분을 어떻게 잘 채워서, 2^x만큼 상쇄해야 할 건데요. 상쇄를 하려면, 보라색 부분의 차이의 절..
자료알고/자료구조 2019. 12. 20. 10:11
힙 정렬 (heap sort) : 최악의 경우에도 O(nlogn)이다.

오늘은 힙 정렬, Heap sort에 대해서 배워보도록 하겠습니다. 어렵지 않으니, 천천히 따라오시기만 하면 됩니다. 저번에, 우선순위 큐라는 자료구조를 배우셨을 거에요. 이 구조를 이용해서 정렬한 것입니다. 이게 끝입니다. 어렵지 않죠? 제가 우선순위 큐를 설명했을 때, 깜빡 잊은 것이 하나 있어요. 이것은, 이진 포화 트리를 만족한다는 것입니다. 그렇기 때문에, 트리의 깊이는 log(들어간 원소의 갯수)에 비례합니다. 그러면, 이것을 어떻게 구축할지가 문제입니다. Root를 0번 인덱스라고 합시다. 그리고 0번의 자식은 1, 2번이라 합시다. 그리고 1번의 자식은 3, 4번이라 합시다. 즉, 어떠한 노드 k가 있다면, 그들의 child는 2k+1과 2k+2가 됩니다. 그러면, 우선 순위 큐에 들어가는..
자료알고/알고리즘 2019. 12. 19. 21:17