※우선순위 큐를 이용한 위상정렬의 방법※ 1.모든 일의 선행 필요조건 관계를 따라 그래프를 그린다.(방향 그래프 완성)2. 각 일에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)3. indegree가 0인 일을 모두 찾아 우선순위 큐에 넣는다4. 우선순위 큐에서 일 하나를 꺼낸다.(위상정렬의 결과 출력을 위해 이때 꺼내진 일을 출력하면 된다.)5. 방금 꺼낸 일에 연결된 모든 일들의 indegree를 1씩 감소시킨다.6. indegree가 감소된 일들 중 indegree가 0인 일이 있으면 우선순위 큐에 넣어준다.7. 우선순위 큐가 빌 때까지 4~6을 반복한다. ※bfs와 dfs를 이용한 위상정렬의 방법※ 공통적으로 먼저 사이클이 있는지 없는지를 판단해야 위상정렬이 생기게 된다.하지만 위..
참고) 32bit integer 이내 답이다 가 들어갈시에 만약 최소값의 범위를 잡을시 그냥 큰값이 아닌 99999999999999999와 같이 정말로 엄청나게 큰 수를 넣는다 #include#include#include using namespace std; //우선순위 큐//방법 3가지//1. 배열 기반//2. 연결리스트 기반//3. 힙 기반 - min heap 기준 //int가 안되서 longlong으로 바꿈 queue arr[101];int result[101]; int main() {int K, N;scanf("%d %d", &K, &N);int a; for (int i = 0; i < K; i++) {scanf("%d", &a);arr[i].push(a); result[i] = a;} // 자료..
우선순위큐
큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐를 구현하는 방법 3가지 1. 배열을 기반으로 구현하는 방법2. 연결리스트를 기반으로 구현하는 방법3. 힙(Heap)을 이용하는 방법 배열을 사용하는 경우 단점 - 데이터 삽입 및 삭제과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 한다. - 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.이 경우 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생할 최악의 경우임 연결리스트를 사용하는 경우 단점 - 삽입의 위치를 찾기 위해 첫번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위를 비료를 진행할지..
백준 문제 가기 분할 정복법을 배운 후 푼 문제 #include#include#includeusing namespace std; long long n, arr[100001];long long histogrm() { long long i, ret = 0; stackst; // 스택에 왼쪽 끝 인덱스 값을 미리 삽입 st.push(-1); for (i = 0; i < n; i++) { // 스택이 비어있지 않고 while (!st.empty() && arr[i] < arr[st.top()]) { //right는 i int tmp = st.top(); st.pop(); if (!st.empty()) { //left는 st.top //left-right-1 너비, 높이 arr[tmp]의 직사각형 넓이 ret =..
1. 체코 2박3일 하면 바로 프라하 공항 -> 베니스 -트레비소 공항 비행기로 걸리는 시간 : 1시간 10분 1인당 비행기 값 9만원 ~ 10만원 (skyscanner 기준) 2. 체코 1박 오스트리아 1박 기차 걸리는 시간 4시간 10분 8시간 체코 여행 체코 여행 1일차 ( 5일) 밤에 도착 체코 여행 2일차 이탈리아 여행 베니스 -> 피렌체 -> 시에나 -> 로마 -> 나폴리-> 바르셀로나 시에나 이탈리아의 소도시 여행 – 토스카나의 시에나 & 산 지미냐노 산 지미냐노 에가면 와인과 치즈를 맛볼수 있다. http://blog.koreadaily.com/view/myhome.html?fod_style=B&med_usrid=nounkwak&cid=859660&fod_no=28 우리가 가는 루트로 짜놓..
프라하의 스카이다이빙 예약 홈페이지 => http://skydivekolin.co.kr 한국어 공식 홈페이지임 한화로 272 196원 혜택 A코스 한화로 272 196원 스카이다빙 + 영상 + 사진 기념티셔츠 제공+ 수료증 제공 만약 200czk 추가시 usb로 제공받음 B코스 3800czk 스카이다이빙 + 수료증 + 기념티셔츠 제공 예약 절차 예약 문의 -> 예약금 입금 -> 날짜와 시간 확정 -> 바우처 발급 -> 미팅 포인트 집결 예약금 35,000원(700코루나) 입금 후 나머지 잔액은 현장에서 지불하시면 됩니다. 입금계좌 안내 : 우리은행 1002-948-889930 유영민(콜린임팩트) 예약금 카드결제하기 Notice1.결제는 코루나(czk)로 가능합니다(유로 결제 가능) 2.예약금을 입금하신 ..