본문 바로가기

분류 전체보기414

백준 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.
[SWEA] 1266. [S/W 문제해결 응용] 9일차 - 소수 완제품 확률 D6(python) 문제 URL: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Sx36IwACFAZN&categoryId=AV18Sx36IwACFAZN&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 접근법 :  수학문제입니다.2명의 작업자가 18번을 시행해서 둘중하나가 적어도 소수번 실행할확률= 1 .. 2025. 1. 15.
백준 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.

티스토리툴바