분류 전체보기
-
네트워크 유량(Network flow)알고리즘/백준 2024. 6. 16. 16:23
네트워크 유량 문제Network flow네트워크 유량문제는 최대 유량(Maximum flow)라고도 한다.방향이 있는 그래프에서 각 간선에 흐를 수 있는 용량이 정해져 있을 때, 출발점에서 도착점까지 보낼 수 있는 최대 유량을 계산하는 문제 용어= Source(시작점)에서 Sink(도착점)으로 동시에 보낼 수 있는 최대 양을 구하는 알고리즘Source: 시작점Sink: 도착점Capacity: 용량(각 간선에 흐를 수 있는 최대 용량)Augmented Path: 증가 경로(최소 1 이상의 유량이 흐를 수 있는 시작점에서 도착점까지의 경로)Flow: 유량, 해당 간선에 실제로 흐르는 용량 네트워크 유량 문제의 특징1. 용량의 제한, 각 간선에 흐르는 유량을 그 간선의 용량을 넘을 수 없음2. 유량의 보존, ..
-
[OPIC] 공부를 위한 사이트공부/Opic 2024. 6. 16. 01:54
자면서 듣는 mp - ILhttps://www.youtube.com/watch?v=6ghh4sIz1yg&list=PLLy4lTdwFGd0pFYGRZmASM1DVwhm1mkEP&index=1 자면서 듣는 mp - IM1https://www.youtube.com/watch?v=Plc2Sq7jDQ8&list=PLLy4lTdwFGd0pFYGRZmASM1DVwhm1mkEP&index=2 자면서 듣는 mp - IM2https://www.youtube.com/watch?v=OWYGBBG2hys&list=PLLy4lTdwFGd0pFYGRZmASM1DVwhm1mkEP&index=3 여우오픽 모의고사https://www.youtube.com/watch?v=-kapDJVUUD0&t=1189s 해커스 모의고사https://y..
-
회전하는 캘리퍼스(Rotating Cailpers)알고리즘/백준 2024. 6. 14. 14:44
회전하는 캘리퍼스...?가장 먼 두 점을 찾는 방법보통 볼록 다각형에 관련된 문제 풀이에 사용된다. 문제 코드 참고회전하는 캘리퍼스 증명https://stonejjun.tistory.com/140 로테이팅 캘리퍼스의 증명이 글을 쓰게 된 동기는 굉장히 재미있다. 증명을 원하시는 분이 있었고 누군가가 내 글을 링크해주신 것을 알게 되었지만 그 글에서는 증명이 없었고, 그래서 관심을 가지게 되었다. 어느 정도stonejjun.tistory.com 회전하는 캘리퍼스 활용https://m.blog.naver.com/dudals5018/222496272677 회전하는 캘리퍼스 (rotating calipers)0. 도입 회전하는 캘리퍼스는 볼록 다각형(convex pol..
-
[SQLD] SQLD 보수 교육공부/DB 2024. 6. 12. 16:50
SQLD 보수 교육취득 시, 자격증 기한 만료 6 개월 전부터 보수 교육을 들을 수 있다.듣지 않으면, 자격증의 효력이 일시정지된다. (약 4 시간)https://www.dataq.or.kr/www/sub/a_04.do 데이터자격시험SQL(Structured Query Language)은 데이터베이스를 직접적으로 액세스할 수 있는 언어로, 데이터를 정의하고(Data Definition), 조작하며(Data Manipulation), 조작한 결과를 적용하거나 취소할 수 있고(Transaction Conwww.dataq.or.kr 데이터 전문가 지식 포털https://dataonair.or.kr/home/%eb%8d%b0%ec%9d%b4%ed%84%b0%ec%97%90%eb%93%80/%eb%8d%b0%ec..
-
[백준] 14003 - 가장 긴 증가하는 부분 수열 5알고리즘/백준 2024. 6. 12. 16:47
가장 긴 증가하는 부분 수열 5: https://www.acmicpc.net/problem/14003 알고리즘: LIS - O(nlogn) + LIS - 경로 추적 코드#include #include #include #include using namespace std;int N;int arr[1000011];int dp[1000011];vector path;int main(){ cin >> N; for (int i = 0; i > arr[i]; } dp[0] = -1111111111;// int level = 0; for (int i = 0; i ans; for (int i = N - 1; i >= 0; --i) { if (level
-
-
[백준] 2550 전구, 비슷한 유형알고리즘/백준 2024. 6. 11. 22:40
문제전구: https://www.acmicpc.net/problem/2550 가장 긴 증가하는 부분 수열 5: https://www.crocus.co.kr/681전기줄2: https://www.acmicpc.net/problem/2568 전구 문제 자체는 N LIS 경로추적을 처음 풀어봐서 고생했다.vector path로 LIS 추가 시 마다, 같이 기록하면서 LIS의 길이를 구하고, 역추적 해주면 된다. 코드#include #include #include using namespace std;int N;int a[10011];int b[10011];int bb[10011];int ab[10011];vector dp;vector path;vector ret;int main(){ cin >> N; ..
-
볼록 껍질(Convex Hull)알고리즘/백준 2024. 6. 10. 20:14
볼록 껍질, Convex Hull?2차원 평면 위에 N개의 점들이 있을 때, N개의 점을 모두 에워싸는 가장 작은 볼록 다각형으로 그림과 같다.일반적으로 Convex Hull을 구하기 위해, 모든 점들을 서로 비교해가면서 모든 경우를 구해 볼 수 있다.하지만 이 경우 점의 개수가 10,000 개만 넘어가도 엄청난 시간이 소요된다. 그레이엄 스캔, Graham Scan 볼록 껍질을 구하는 알고리즘으로, O(nlogn)의 시간에 Convex Hull을 구할 수 있다.* 선행 알고리즘 : CCW, Counter Clockwise3개의 점의 위치 관계를 알아내는 기하 알고리즘, 세 점이 일직선 상에 있으면 0, 반시계 방향이면 양수, 시계 방향이면 음수를 반환한다. 그레이엄 스캔 알고리즘 과정1. 주어진 점들을..