컴공생 일상 블로그 컴공생 일상 블로그

가끔 풀다보면 간간히 보이는 Lazy Segment 문제세그먼트 트리에서 특정 구간에 대해 업데이트를 Lazy하게 해준다. 나중에 시간나면 따로 정리하면 좋을 듯 문제https://www.acmicpc.net/problem/16975 코드#include #include #include #include #include #include #include #include using namespace std;int N, M;long long arr[100000];vector tree;vector lazy;long long Make(int node, int start, int end){ if (start == end) { tree[node] = arr[start]; return tre..

N이 3 또는 5인 경우밖에 없는 문제라 다양한 방법으로 풀이가능할 것 같다.요즘에 DP익숙해지려고 하는 중이라, DP로 풀었다. 그래도 풀다보니 익숙한 애들은 풀만한듯그리고 여러모로 바빠서, 그냥 매일매일 랜덤 골드 적당히 푸는 중 문제https://www.acmicpc.net/problem/17265 DP, 근데 다 돌려도 상관 없을 듯, 또는 깡구현으로 풀어도 될듯 코드#include #include #include #include #include #include #include using namespace std;int N;char arr[5][5];int dp[5][5];int dp2[5][5];int dy[3] = { 0, -1 , -2 };int dx[3] = { -2, -1, 0 };int..

생존신고겸 쓰는 문제 풀이 글오전에 심심해서 시뮬레이션 하나 풀고, 오후에는 요거 품각 SCC그룹을 구하고 각 그룹끼리 연결(물을 흘려보낼 수 있는지) 체크해주면 된다. 코드 오타났었는데, 예제 케이스는 다 통과해서 찾는라 고생한 문제 문제https://www.acmicpc.net/problem/18133강한 연결 요소 + 유니온 파인드 + BFS? 코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M;vector graph[100001];vector rev[100001];bool visited[100001];bool check[100001];stack s;v..

잡담대회나갈건 아니고, 취미로만 푸는 거라 대충대충 푸는데, 문제 맞힌 사람이 적어지니 다양한 풀이를 참고가 힘든게 단점 같다.틀렸을 때 잘못된 부분 찾는게 시간이 너무 걸리는 듯가끔 이왜틀 당하면 한 두 시간 훌쩍 감... 심심할 때 마다 알고리즘 폭을 넓이고 싶은데,현생 이슈들도 있고, 싸피 프젝에 영어도 해야해서 시간이 없어서 평일 스트릭은 실버-골드로 연명하는 중 문제https://www.acmicpc.net/problem/1258네트워크 플로우, MCMF 문제 그래도 이 문제는 쉬운편source와 sink에 대해 간선 용량을 잘 설정해주고, 유량 돌려주면 된다. 코드#include #include #include #include #include #include #include #include u..

시작하기에 앞서...보통은 다른 알고리즘 + 그래프 탐색으로 나올듯, 구현력 업을 위한 시뮬+그래프 탐색도 섞어 놨음구현을 잘하자! 아이디어가 떠올라도 구현을 못하면 쓸모가 없음 이론그래프의 특징정점과 간선으로 이루어져 있음(Node정점, Edge간선이라고 함)그래프는 순환 or 비순환 구조를 이룸 (문제에서 사이클이 존재하는지에 대한 여부)그래프는 방향이 있는 유향 그래프와 방향이 없는 무향 그래프가 있음 (무향 그래프의 경우 양방향 이동이 가능)간선이 방향을 가지는지에 따라 그래프를 잘 입력 받아야 함그래프에 가중치(비용, 시간 등등)이 더해진다면 최소 비용(최단 거리) 문제가 됨 트리의 특징사이클이 없음하나의 루트(최상위 노드)를 가짐부모 노드와 자식 노드의 관계가 존재함방향이 있는 비순환 그래프라..

조합, 순열, 중복 조합 등 (실버)N과 M(1) https://www.acmicpc.net/problem/15649 ✅ 07.15N과 M(2) https://www.acmicpc.net/problem/15650  ✅ 07.15N과 M(3) https://www.acmicpc.net/problem/15651  ✅ 07.16N과 M(7) https://www.acmicpc.net/problem/15656  ✅ 07.16N과 M(9) https://www.acmicpc.net/problem/15663  ✅ 07.17N과 M(11) https://www.acmicpc.net/problem/15665  ✅ 07.17 백트래킹 활용 (실버)스타트와 링크 https://www.acmicpc.net/problem/1..

문제https://www.acmicpc.net/problem/11408 MCMF문제, 최대유량 + SPFA기존의 flow문제에 대해서 mcmf를 추가해 탐색하는 느낌SPFA에서는 음의 사이클 존재에 대해 체크하기 위한 코드가 있는데, MCMF문제에서는 필요 없는듯?(그렇다고 한다. - https://www.acmicpc.net/board/view/1291) 코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M;int capacity[808][808];int flow[808][808];int cost[808][808];//0 source//1 ~ 400 pers..

SCC, 강한 연결 요소(Strongly Connected Componet)방향이 존재하는 유향 그래프에서 서로 강하게 연결된 부분 집합을 의미, 강하게 연결되있다 -> 사이클이 형성된다.설명보다 아래 그림을 보면 쉽게 이해된다. 각각의 영역이 SSC를 이룬다. 코사라주 알고리즘(Kosaraju's Algorithm)1. 입력된 그래프에 대해 역방향 그래프를 만듬2. 그래프에 대해서 DFS를 수행하고, 끝나는 순서대로 스택에 push3. 스택을 하나씩 pop하면서 역방향 그래프에서 DFS를 수행- 이미 방문한 정점의 경우 pop만 수행- 방문하지 않은 정점에 대해 DFS를 수행하고, 이 때 탐색되는 정점들이 하나의 SCC 동작 방식0.  Input, 그래프와 역방향 그래프를 생성해준다.# Input7 9..