자료알고 검색 결과

해당 글 130건
백준 배열 돌리기 5 : 전략적인 브루트 포스로 풀어봅시다.

배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요? 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부..
자료알고/알고리즘 2021. 4. 4. 03:29
알고리즘 시간 복잡도 대강 분석하는 방법을 예제를 통해 알아봅시다.

시간 복잡도를 어떻게 대강 분석할까요? 실행 시간을 보고, 추정을 하시면 됩니다. 정말 괴랄한 복잡도가 아니라면, O(n), O(n^2), ... 등은 어느 정도 맞아 떨어집니다. 저는 java에서 메서드를 실행하는 데 걸린 시간을 측정할 때, System.nanoTime()을 이용하는 편입니다. 이것은 정밀한 시간 측정을 해 주지는 못합니다만, 어느 부분에서 시간 초과가 날 수 있는지 후보해를 추릴 수 있습니다. 질문이 하나 들어왔습니다. M자리 수와 N자리 수를 BigInteger로 곱하였습니다. M, N은 30만 자리 정도 되었다고 합니다. 10진수로 M자리 수라면, 32bit 2진수가 10진수 9자리와 대응이 됩니다. 그래서, bit 연산을 잘 이용하면 M과 N이 최대 30만자리까지 나오니까, (..
자료알고/알고리즘 2021. 4. 3. 02:24
펜윅 트리 (fenwick tree) : 구간합을 빠르게 구한다.

펜윅 트리는 구간합을 구할 때 상수를 줄이기 위해 이용할 수 있는 구조입니다. 유성 문제는 세그먼트 트리 대신에 펜윅을 써야 풀리는 문제로 유명한데요. 시간 복잡도의 특성상 상수를 줄여야 하는데, 레이지를 이용한 세그 트리는 느리기 때문입니다. 이게 어떤 식으로 동작하는지 보고, 간단하게 코드를 작성해 보도록 하겠습니다. 펜윅 트리는 다음과 같이 그릴 수 있습니다. 이들은 각각 [1], [3], [5], [7]을 담고 있는 노드입니다. 규칙을 찾아보면, 1, 3, 5, 7은 1의 배수이지만 2의 배수는 아닙니다. 다음에 1, 3, 5, 7과 비교했을 때 구간의 크기가 2배인 2와 6이 있습니다. 이들의 구간 크기는 2이고요. 각각 구간 [1, 2], [5, 6]을 담고 있습니다. 이 둘의 공통점은 2의 ..
자료알고/자료구조 2021. 3. 14. 00:37
여러 트릭에 응용되는 트리에서의 dfs ordering을 알아봅시다.

ps를 하시다 보면, 이런 말은 한 번쯤 들어보셨을 겁니다. 트리를 일렬로 펴기, 트리를 구간으로 바꿔서 풀기. 자동차 공장 트릭. 이들의 기반이 되는 것은 dfs ordering입니다. 그리고 이를 응용해서, HLD, LCA와 같은 것에도 쓸 수 있습니다. 이 글에서는 HLD, LCA는 다루지 않을 겁니다. 대신에, 트리를 구간으로 바꾸기 위해서 사용하는 전처리에 대해서 알아보도록 하겠습니다. 먼저, 예시로 쓰이는 트리는 아래와 같습니다. 여기서, 이런 쿼리들이 들어온다고 생각해 보겠습니다. 3을 root로 하는 서브 트리에 속한 노드들에 +3을 더한다. 혹은 xor 3을 한다. 이런 것들이 들어올 수 있어요. 트리를 구간으로 어떻게 펴는 것이 가능할까요? 해당 쿼리에서 중요한 것은 부모와 거기에 딸려..
자료알고/알고리즘 2021. 3. 7. 20:31
백준 최소 환승 경로 : 허브와 노드를 생각하자.

백준에는 5214번 환승 문제와, 2021번 최소 환승 알고리즘을 구하는 문제가 있습니다. 이 두 문제 중에서 후자를 풀어보겠습니다. 역의 갯수 n과 노선 갯수 L은 둘 다 10만 이하라는 조건은 꽤 무시무시하게 다가옵니다. 각 노선 길이의 합은 100만을 넘지 않는다는 조건을 잘 이용해 봐야 할 듯 싶네요. 여기서 핵심은 '환승을 한다'는 것을 어떻게 그래프로 표현을 할 것인지입니다. 학교 과제에서도 왕왕 나오는 편이니, 이야기를 해 보도록 하겠습니다. 노선 1과 노선 2가 만나는 환승 역 j를 생각해 봅시다. 그래프는 요렇게 그려질 수 있습니다. 여기서 핵심은, j번 역을 통해서 노란색에서 파란색으로, 혹은 파란색에서 노란색 노선으로 건너갈 수 있다는 것입니다. 3개 노선이 만나는 j역이면 어떨까요?..
자료알고/알고리즘 2021. 2. 7. 01:48