자료알고 검색 결과

해당 글 130건
백준 팰린드롬 진법 : 후보해는 생각보다 많이 적다.

오늘 풀어볼 문제는 백준 팰린드롬 진법이라는 문제입니다. 난이도는 솔브드 기준으로 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
우선순위 큐 : 부모가 자식들보다 rank가 높다.

우선순위 큐는, 삽입과 삭제가 일어날 때, 가장 우선순위가 높은 것을 빠르게 찾을 수 있는 구조입니다. 일단, 이것의 특징 먼저 간단하게 잡고 넘어가 봅시다. 먼저, 부모들은 자식들보다 rank가 높습니다. 예를 들어서, A의 자식이 B, C라고 해 봅시다. 그러면, A >= B이고 A >= C입니다. 그러면 A의 모든 child들 (자식의 자식이라던지)은 무조건 A보다 rank가 같거나 낮을까요? 위 그림을 봅시다. B(1)의 직계 child는 B(2), B(2)의 child는 B(3), ... 이런 식으로 가고 있어요. 그러면 A >= B(1) >= ... >= B(n)이 성립합니다. 연쇄입니다. 따라서, A >= B(n)입니다. 부모에서 자식으로만 연결된 간선이 있고, x가 A로부터 도달 가능할 때..
자료알고/자료구조 2019. 12. 16. 21:56
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