2020-2021 동계 모각코 (12) 썸네일형 리스트형 [붕어빵 꼬리먼저 팀] 6회차 - 학습 마무리 2021/02/13 동계 모각코 6회차 오늘 공부하고자 했던 정점 분할에 대한 이해와 문제 풀이를 마쳤습니다. [정점 분할] www.acmicpc.net/problem/2316 최대 유량에서 정점의 중복마저 제거하는 문제입니다. 정점 분할은 하나의 알고리즘이라기보다는 최대 유량 문제에서 그래프를 구성하는 하나의 스킬입니다. 일반적인 최대 유량 문제에서는 간선의 용량만 신경 써줘도 문제가 해결이 가능했으나 위 문제처럼 정점의 중복을 예방하기 위해서는 정점 분할이 필요합니다. 우선 최대 유량 문제에서는 간선을 선택하는 순서에 상관없이 최적의 선택을 하기 위해 음의 유량이라는 개념을 도입하였습니다. 단순하게 최대 유량을 흘릴 때에는 간선을 선택하는 순서에 따라 최적이 달라지는 문제가 발생합니다. 그러나 그런 .. [붕어빵 꼬리먼저 팀] 6회차 - 학습 계획 2021/02/13 동계 모각코 6회차 오늘 학습할 주제는 정점 분할입니다. www.acmicpc.net/problem/2316 해당 문제 풀이를 목표로 하겠습니다. [붕어빵 꼬리먼저 팀] 5회차 - 학습 마무리 2021/01/28 동계 모각코 5회차 오늘 공부하고자 했던 최대 유량에 대한 이해와 문제 풀이를 마쳤습니다. [최대 유량] www.acmicpc.net/problem/17412 최대 유량을 이용하여 두 도시를 얼마나 많이 왕복할 수 있는지를 구하는 문제입니다. 우선 해당 문제에서는 정석적인 최대 유량 문제라기보다, 간선이 추가됨에 따라 용량이 1씩 늘어나는 방식으로 생각합니다. 1번 도시에서 2번 도시까지 흘릴 수 있는 유량의 최대를 구한다면 자연스럽게 1번 도시와 2번 도시를 왕복할 수 있는 횟수를 구할 수 있게 됩니다. 간선이 중복될 수 있으므로 용량을 계속 더해줄 수 있도록 합니다. N의 값이 작으므로 2차원 배열을 사용하였습니다. 사용 가능한 알고리즘 중 Edmonds-Karp 알고리즘을 사용하.. [붕어빵 꼬리먼저 팀] 5회차 - 학습 계획 2021/01/28 동계 모각코 5회차 오늘 학습할 주제는 네트워크 플로우입니다. www.acmicpc.net/problem/17412 해당 문제 풀이를 목표로 하겠습니다. [붕어빵 꼬리먼저 팀] 4회차 - 학습 마무리 2021/01/21 동계 모각코 4회차 오늘 공부하고자 했던 회전하는 캘리퍼스에 대한 이해와 문제 풀이를 마쳤습니다. [회전하는 캘리퍼스] www.acmicpc.net/problem/10254 회전하는 캘리퍼스를 사용하여 가장 먼 두 점을 구하는 문제입니다. 우선 존재하는 모든 점들에서 가장 먼 두 점을 찾기 위해서는 볼록껍질을 사용합니다. 주어진 점 중에 가장 먼 두점이 볼록껍질 위에 존재함은 직관적으로 떠올릴 수 있습니다. 그러나 볼록껍질을 구한 후에 볼록껍질에 해당되는 모든 점들에 대해서 가장 먼 거리를 찾는 것도 $O(N^2)$입니다. N의 크기가 줄었을 뿐, 시간복잡도 면에서는 여전히 부족합니다. 이런 문제를 해결하기 위해 회전하는 캘리퍼스라는 알고리즘을 사용하는데, $O(N)$에 볼록껍질에서 .. [붕어빵 꼬리먼저 팀] 4회차 - 학습 계획 2021/01/21 동계 모각코 4회차 오늘 학습할 주제는 회전하는 캘리퍼스입니다. www.acmicpc.net/problem/10254 해당 문제 풀이를 목표로 하겠습니다. [붕어빵 꼬리먼저 팀] 3회차 - 학습 마무리 2021/01/19 동계 모각코 3회차 오늘 공부하고자 했던 머지 소트 트리에 대한 이해와 문제 풀이를 완료하였습니다. 원래 계획했던 문제는 수열과 쿼리 1 (www.acmicpc.net/problem/13537) 였습니다. 그러나 해당 문제는 오프라인 쿼리를 활용하여 머지 소트 트리 없이도 해결이 가능한 문제였기에, 입력에 이전 쿼리의 정답을 요구하여 온라인 쿼리를 강제한 수열과 쿼리 3 (www.acmicpc.net/problem/13544) 를 풀기로 하였습니다. 해당 문제는 온라인 쿼리를 강제하여 오프라인 쿼리를 사용한 세그먼트 트리 풀이를 막았기 때문에 머지 소트 트리로만 풀어야 합니다. [머지 소트 트리] www.acmicpc.net/problem/13544 머지 소트 트리를 사용하여 특정 구.. [붕어빵 꼬리먼저 팀] 3회차 - 학습 계획 2021/01/19 동계 모각코 3회차 오늘 학습할 주제는 머지 소트 트리입니다. www.acmicpc.net/problem/13537 해당 문제 풀이를 목표로 하겠습니다. 이전 1 2 다음