알고리즘 검색 결과

해당 글 67건
functional graph 에서 사이클을 어떻게 묶어낼까요?

안녕하세요. 그래프 이론에서 functional graph는 생각보다 많이 다뤄지는 주제입니다. 이 사이트를 보셔도 좋을 듯 싶군요. 울프람 알파에도 정의가 되어 있습니다. 이 그래프에서 어떻게 사이클을 찾을까요? 예전에, scc (강한 연결 요소)를 모르던 시절에 풀었던 문제들이 몇 개 있었습니다. 그 문제들을 풀 때 써먹을 수 있는 흥미로운 것들은 2개 입니다. 여기서 노드 i와 노드 j가 같은 덩어리에 속해있다면 i에서 j로 갈 수 있는 방법이 있거나, j에서 i로 갈 수 있는 방법이 있다는 것을 의미합니다. 이 둘을 보이도록 하겠습니다. 상대적으로 보이기 쉬운 2번부터 보여봅시다. 그래프에서 cycle은 시작점 s가 있다고 해 봅시다. 여기서 출발해서 다른 노드들을 거쳐서, s로 도착하는 경로가 ..
알고리즘/ps 2021. 1. 26. 03:38
많이 언급되는 오프라인 쿼리 간단하게 훑어봅시다.

오프라인 쿼리. ps 하면서 한 번 쯤은 들어보셨을 법한 말입니다. 무엇을 오프라인으로 처리한다는 것일까요? 사실 잘 모르겠습니다. 대신에, 하나의 문제에 대해서 생각해 보면서 어떤 것이 오프라인 query 인지 대충 감만 잡도록 하겠습니다. 그냥 관점만 보셔도 됩니다. ps를 하는데 막 오프라인이 뭐냐고 묻진 않을 거니까요. 그거보다는 어떻게 효율적으로 해결할지 생각하시는 것이 더 중요하지 않을까 싶습니다. 배열이 이런 식으로 있습니다. 여기서 r1, r2, r3, r4, r5는 해당 위치로부터 얼마나 떨어진 거리까지 영향을 미치는지에 대한 것입니다. 마나커 알고리즘을 한 번 보셨다면, 이해가 가실 겁니다. 문제는, 이것이 기본적인 마나커에서 +3 ~ +4가 된 이유는, 이것을 처리하는 아이디어가 어렵..
알고리즘/ps 2021. 1. 4. 23:58
정점 분할 : 노드를 상태에 따라 여러 개로 쪼갠다.

5002번째로 푼 문제는 이 문제였습니다. 문제 상황을 간단하게 요약하면 아래와 같습니다. 1순위가 같으면 2순위를 처리하는 것은 나중에 생각해 보도록 합시다. 우리가 원하는 것은 '탑승 비용', 문제에서 설명하는 route cost를 최소화 하는 방법부터 고민해 보겠습니다. 비행기 1이 도시1에서 3을 거쳐서 목적지인 7로 간다고 해 봅시다. 대충 1에서 7로 가는데 3을 경유한다고 보시면 됩니다. 이 경로를 선택하는 비용이 10이라고 해 보겠습니다. 문제에서 설명하는 것에 따르면 1에서 3으로 가는 탑승 비용, 3에서 7로 가는 탑승 비용, 1에서 7로 가는 탑승 비용이 10으로 같습니다. 이 세 경우는 경로 1을 선택해서 갈 수 있는 경우이기 때문입니다. 문제는, 비용 10을 어느 간선에 줄 것이냐..
알고리즘/ps 2020. 12. 29. 04:01
수학적 귀납법을 활용하여 문제를 풀어봅시다.

귀납법은 이산 수학 시간에 들어보셨을 증명 방법입니다. 어떻게 쓰는지, 백준에 있는 문제를 풀어보도록 하겠습니다. 최근 USACO 실버에 나온 문제라고 하는데, 실버 같지 않습니다. 문제를 요약하면, 길이가 n인 순열이 주어집니다. 1부터 n까지의 수가 1번 등장합니다. 그리고 m개의 웜홀 정보가 (a, b, c)로 주어지는데, 너비가 c인 웜홀을 열면 a번째 원소와 b번째 원소를 바꿀 수 있다는 의미입니다. 어떻게 잘 배치해서 순열을 오름차순으로 정렬하려고 할 때, 연 웜홀들의 최소 너비를 최대화 시키는 문제입니다. 이걸 보면, 일단 이분 탐색임을 알 수 있는데, 정렬이 되어야 하는 조건이 상당히 어렵습니다. 어떻게 해 볼 것인가. 작은 집합부터 보면서, 큰 집합에서 성립하는지 보아야 겠습니다. 귀납법..
알고리즘/ps 2020. 12. 24. 00:01
백준 1060번 구간 : 후보해를 추린다.

이번 시간에는 백준 1060번 문제를 풀면서, 후보해를 어떻게 추리는지 보도록 하겠습니다. 문득 떠오르는 시스텟 페일 간단한 알고리즘을 물어보는 코딩테스트에도 이 글에서 간접적으로 설명한 것들은 나올 법 하니, 알아두면 좋을 듯 싶습니다. 사실 코테 접은 지 1년 넘어서 잘 모른다는 것은 함정입니다. 문제는 아래와 같습니다. 어떤 집합 S에는 양의 정수 L개가 있고, f(x)를 아래 조건을 만족하는 구간의 갯수로 정의합니다. 0보다 큰 정수 x, y가 있다고 한다면, f(x) < f(y)이거나, f(x) = f(y)이고 x
알고리즘/ps 2020. 12. 3. 01:21