Algorithms (24) 썸네일형 리스트형 Algorithm 라이브러리 [C++ 코딩테스트 대비] * 이 글은 단순 개인 참고용으로 작성한 글입니다 * Primitive Integer 최소값 최대값 min(상수 a, 상수 b) : 작은 상수 max(상수 a, 상수 b): 큰 상수 Vector 최소값 최대값 *min_element(v.begin(),v.end()): a vector element *max_element(v.begin(),v.end()): a vector element C++ STL::Queue::Priority_Queue 오늘은 Queue 헤더파일에 포함되어있는 우선순위 큐(Heap)에 대해서 포스팅합니다~ Heap은 Insertion과 Deletion에 최적화되어있는 자료구조입니다. 데이터를 특정 기준에 맞춰 정렬된 상태로 보관하기 때문에 복잡한 문제에서 이용하기 정말 좋아요. ★ 기본 우선순위 큐(내림차순) ★ 아무것도 명시하지 않은 우선순위 큐는 내림차순으로 작동합니다! #include #include #include using namespace std; priority_queue pq; int main() { pq.push(10000); pq.push(10); pq.push(100); pq.push(1000); pq.push(1); while (pq.empty() != true) { cout C++ ::string 으.. c++로 문자열처리를 하게될줄이야.. 오늘 포스팅은 문자열 처리를 다루는 포스팅입니다~ 자세한 내용은 http://www.cplusplus.com/reference/string/string/ string - C++ Reference www.cplusplus.com 위 사이트를 참조하세요! 문자 삽입(push_back함수) string 객체 마지막에 character형 문자를 삽입해주는 경우입니다. character형을 삽입해준다는점 반드시 기억해두세요! 예제 출력결과 ASCII CODE 48은 '0'에 해당하는 문자값이므로, push_back()함수에 의해 맨 마지막부터 삽입이 되었습니다. ※ 문자 수정의 경우는 [] 연산자를 이용해 접근, 수정해줄 수 있습니다. ※ 문자열 삽입(append함수).. 백준 알고리즘 2188번 문제 : 축사배정 문제는 백준 사이트에서 확인하세요! https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 John씨는 그의 소 축사를 갓 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, John씨는 축사를 N개의 칸으로 구분하여 두고, 한 칸에는 한 마리의 소만을 들어가도록 하였다. 첫 주에는 소들을 임의적으로 칸에 배정하여 축사를 운영하였으나, 곧 문제가 발생하게 되었다. 자신들이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다. 농부 John씨를 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번 www.acmicpc.net 오늘 포스팅할 문제는 최대 유량과 관련된 문제입니다. milk scheduling 문제를 풀때도 그.. 강한 연결 요소 - Strongly Connected Component 안녕하세요. 오늘 포스팅할 내용은 강한 연결 요소입니다. 강한 연결요소란 일종의 Cycle인데요. 일반적으로 생각하는 Cycle보다는 조금 더 큰 범위를 다룹니다. 정점 u에서 v로 가는 간선이 존재할때, 임의의 정점 j(v에서 도달가능한)이 u로 가는 간선이 존재하면 이때의 경로 u->v->...->j->u는 강한 연결요소가 됩니다. 강한 연결요소를 찾아서 그래프를 DAG(Directed Acyclic Graph)로 바꿀 수 있습니다. 위상정렬(Topological Sorting)을 통해 주어진 문제를 해결 할 수 있도록 할수도 있고, 각각의 SCC간의 관계에서 정답을 구하는 문제도 있습니다. 자세한 내용은 위키피디아를 참조하세요! https://en.wikipedia.org/wiki/Strongly_.. Ford - Fulkserson 최대 유량 알고리즘 Ford - Fulkerson 알고리즘은 3단계로 이루어져 있습니다. 그래프 순회 알고리즘(DFS/BFS)을 이용해 Augmenting path 찾기 Augmenting path의 V1, V2, V3, ... , Vn 사이에 존재하는 residual capacity의 최소값 찾기. residual capacity의 최소값만큼 Skew Symmetry 성질을 이용해 지나온 path상의 flow 들을 f(u,v)=-f(u,v)해줍니다. 이때 residual capacity는 capacity[u][v] - flow[u][v]이고 u,v 사이의 간선에 흐를 수 있는 유량의 양이라고 생각하면 됩니다. #include #include #include #define INF 999999999 using namespac.. Flow Network - 유량 네트워크 참고자료 wikipedia https://en.wikipedia.org/wiki/Flow_network Flow network - Wikipedia In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a en.wikipedia.org 유량 네트워크가 성립하기 위한 3가지 조건 1 Capacity Constr.. 백준 알고리즘 2512번 문제 : 예산 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. www.acmicpc.net binary search를 이용한 문제입니다! 문제 분석 국가예산을 여러 지방에 분배하려 한다. 모든 예산요청을 배정해 주기는 어렵다. 정해진 총액 이하에서 가능한 한 최대의 총 예산을 배정하려 한다. 가능한 최대로 분배할 수 있는 예산의 금액은? 1. 모든 요.. 이전 1 2 3 다음
