자료알고/알고리즘 검색 결과

해당 글 87건
트리 dp : 스크루지 민호 문제로 간단한 것만 풀어 봅시다.

tree dp는 최근에 코테에 나왔습니다. 그래서 트리 dp 2 문제를 준비해 보았습니다. 스크루지 민호 시리즈는 이들을 연습하기 좋은 셋트이기 때문입니다. 트리 탐색이나, dfs에 대한 기본적인 이해가 있다고 가정하고 진행하겠습니다. 먼저, 이 문제부터 보겠습니다. 왜 1부터 안 푸냐. 사실 해당 방법으로 풀기는 2가 1보다는 쉽기 때문입니다. 트리가 이렇게 있어요. 문제 조건을 잘 보시면, 양방향 간선에 연결되어 있는 도시 2개 중에 최소 하나 이상은 경찰서가 있어야 함을 알 수 있어요. 그러면 현재 cur에 경찰서를 세운 경우와 그렇지 않은 경우로 나눌 수 있음을 알 수 있어요. 먼저, cur에 경찰서를 세우지 않은 경우를 생각해 봅시다. 그러면, 자식 도시들은 모두 경찰서를 세워야 합니다. 만약에..
자료알고/알고리즘 2021. 4. 25. 20:24
백준 배열 돌리기 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
여러 트릭에 응용되는 트리에서의 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