백준215 백준 17410 수열과 쿼리 1.5 문제 URL : https://www.acmicpc.net/problem/17410 문제 접근법: 이전글 수열과 쿼리 18 문제와 동일합니다.https://congsoony.tistory.com/423 백준 14504 수열과 쿼리 18문제 URL : https://www.acmicpc.net/problem/14504 문제 접근법 : 제곱근 분할법을 공부하다가 문제를 풀게됐네요제곱근 분할이란게 데이터를 루트n개로 분할해서 관리하는형태이더군요그안에서 데이터congsoony.tistory.com 그치만 그대로 코드를 조금 바꿔서내면 런타임에러가나올겁니다.대체 무슨 이유인지 계속 찾아봤는데제곱근분할이란게 반드시 제곱근형태로 분할할 필요는 없더군요적당한 사이즈를 설정해서 분할해주도 상관이없습니다. 소스코드:.. 2025. 2. 10. 백준 14504 수열과 쿼리 18 문제 URL : https://www.acmicpc.net/problem/14504 문제 접근법 : 제곱근 분할법을 공부하다가 문제를 풀게됐네요제곱근 분할이란게 데이터를 루트n개로 분할해서 관리하는형태이더군요그안에서 데이터를 정렬된 형태로 저장하여upper_bound를 이용한 데이터개수 찾는 알고리즘으로해결한다는게 참 인상깊었습니다.이번건의 문제는여러 블로그를참고했고 코드는:https://david0506.tistory.com/57 [ Query ] Sqrt Decomposition (제곱근 분할법)Sqrt Decomposition 구간 쿼리를 Segment Tree를 이용해서 처리하면 시간복잡도가 $O(logN)$이다. 이는 트리의 깊이에 비례하는데, 각 노드의 자식 노드의 수를 밑으로 가지는 로그.. 2025. 2. 10. 백준 4013 ATM 문제 URL : https://www.acmicpc.net/problem/4013문제 접근법 : scc + topology or bfs를 이용한문제입니다. scc를 구성한후 새로운 그래프를 다시만들어준후topology or bfs를 이용해서 최종답을 구해주면 됩니다. 자세한 건 소스코드 주석에 달았습니다. 소스코드:#include using namespace std;#define ll long longvector> v,scc_v;vector check,st,finished,atm,restaurant,scc_atm,dp;vector scc_restaurant,scc_indegree;int n,m;int s,p;int cnt,scc;void input(){ cin>>n>>m; v= vector>.. 2025. 1. 15. 백준 2152 여행 계획 세우기 성공 문제 URL : https://www.acmicpc.net/problem/2152 문제접근법 : scc를 이용한문제입니다.scc를 구하고 나서 새로운 scc를 이용하여 그래프를 다시만들어줍니다.그리고 q를 이용한 다익스트라를 이용하는것처럼이용할수있는 최대이용을 구합니다.즉 scc+ bfs or dijkstra 소스코드 : //By 콩순이냉장고#includeusing namespace std;#define ll long longint n,m,s,t;vector> v,sccv;int cnt,scc;vector sccid,check,st,sccnum,scc_indegree;void input(){ cin>>n>>m>>s>>t; v =vector>(n+1); sccnum= check = sc.. 2025. 1. 15. 이전 1 2 3 4 ··· 54 다음
