Doby's Lab

https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net Solved By: Bipartite Matching 처음으로 이분 매칭 알고리즘을 사용했습니다. DFS의 리턴형이 bool인 함수를 구현하여 각 정점이 이어질 수 있는 지를 파악합니다. Time Complexity는 O(VE)입니다. 또 다른 이분 매칭 알고리즘들이 있다는데 알아보아야겠습니다. 처음 구현을 하여서 각 코드마다 어떤 역할인지 주석으로 달아두었습니다. #include #inclu..

https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net Solved By: Euler Tour Technique, Segment Tree, Lazy Propagation #include #include #include #define MAX (500000 + 1) #define pii pair #define ll long long using namespace std; int n, m; vector adj[MAX..

https://www.acmicpc.net/problem/14268 14268번: 회사 문화 2 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net Solved By: Euler Tour Technique, Segment Tree, Lazy Propagation #include #include #include #define MAX (500000 + 1) #define pii pair #define ll long long using namespace std; int n, m; vector adj[MAX]; pii ett[MAX]; ll sgT..

https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net Solved By: Edmonds-Karp 처음으로 최대 유량 문제를 풀어보았습니다. BFS를 활용한 Edmonds-Karp를 사용했습니다. #include #include #include #include #define MAX ('z' - 'A' + 1) #define INF 1e9 using namespace std; int c[MAX][MAX]; int f[MAX][MAX]; v..

https://www.acmicpc.net/problem/2820 2820번: 자동차 공장 상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. www.acmicpc.net Solved By: Euler Tour Technique, Segment Tree, Lazy Propagation 상사와 부하의 관계는 트리 구조로 나타낼 수 있으며 업데이트마다 DFS를 사용하기엔 N, M의 범위가 커서 시간 초과가 걸릴 가능성이 큽니다. Euler Tour Technique을 사용하여 트리를 Segment Tree처럼 만들어서 구간별로 업데이트한다면 시간을 확실하게 줄일 수 있습..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Solved By: Union-Find #include #include #define MAX 201 #define pii pair using namespace std; vector edges; vector trip; int parent[MAX]; int n, m; int getRoot(int node){ if(node == parent[node]) return node; else return pa..

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net Solved By: Union-Find #include #define MAX 1000000 using namespace std; int T; int parent[MAX]; int getRoot(int node){ if(node == parent[node]) return node; else return parent[node] = getRoot(parent[node]..

예전부터 블로그 재정비를 해야 할 거 같다는 생각을 가지고 있다가 이번에 격리를 하게 되면서 다른 분들의 블로그를 보게 되는 시간들을 많이 가졌습니다. 이를 토대로 새롭게 정리를 해보려 합니다. 우선적으로 카테고리 정리입니다. 현재는 자료구조 혹은 알고리즘 별로 카테고리 되어있지만 새로운 것들을 배울수록 카테고리가 분잡한 느낌이 들어 정리를 해야겠다는 생각이 들었습니다. 아마 플랫폼 별로 문제들을 정리하여 둘 거 같습니다. >> BOJ, codeforces, Programmers 등 글을 쓰는 방식에서도 별다른 아이디어나 알고리즘을 이용한 특유의 테크닉을 이용하지 않는다면 사용된 알고리즘과 코드만 정리하여 업로드할 생각입니다. +풀었던 모든 문제를 포스팅할 생각은 없습니다. 물론, 아직은 백준이 메인이지..