알고리즘 검색 결과

해당 글 73건
왜 위상 정렬을 이용하면 그래프 사이클이 있는지 판단할 수 있을까요?

그래프에 사이클이 있는지 없는지 판단하는 방법 중 하나는 위상 정렬을 이용하는 것입니다. 어떻게 이용한다는 것일까요? 방향성이 있는 그래프에서, indegree가 0인 게 하나도 없다면 사이클이 있다고 판단합니다. 물론, indegree가 0인 노드가 있는데 사이클이 있는 경우도 있습니다만, 이건 글의 말미에 잠깐 다루겠습니다. 먼저, 아래와 같이 조건을 제한해 보겠습니다. 방향성이 있는 그래프에서 아래 조건이 성립합니다. 이 경우, indegree 값이 0인 노드가 존재하지 않는 그래프에 대해서 판단하는 것 보다는 조금이나마 더 쉽습니다. 사이클이란, i에서 i로 가는 경로를 의미합니다. 제한된 조건을 만족하는 노드 갯수가 n인 그래프를 생각해 봅시다. 일단 indegree 값이 1이므로, 나가는 것이..
알고리즘/ps 2021. 5. 3. 06:45
트리 dp : 스크루지 민호 문제로 간단한 것만 풀어 봅시다.

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

배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요? 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부..
알고리즘/ps 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을 한다. 이런 것들이 들어올 수 있어요. 트리를 구간으로 어떻게 펴는 것이 가능할까요? 해당 쿼리에서 중요한 것은 부모와 거기에 딸려..
알고리즘/ps 2021. 3. 7. 20:31