세그멘트 트리 레이지 프로퍼게이션 문제. 이것 역시 겨울학교에서 복붙했다 ㅋㅋ www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 레이지세그는 갱신을 필요할때만 하게끔 따로 propergate()라는 함수를 작성해주는데, 이것이 구간쿼리를 더 빠르게 처리할 수 있게 해준다. #include #include #include #define MID ((s+e)/2) using namespace std; int seg[456789..
겨울학교에서 풀었던 문제 깔끔하게 날로 먹었다 원래는 2차원 세그트리로 접근해야 하는 문제이지만, 묻는것이 그냥 누적합이기 때문에 2차원 펜윅 트리를 사용해서도 해결할 수 있고, 나는 펜윅으로 해결했다. www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net 펜윅 설명은 다른 수많은 분들이 더 깔끔하게 해주실거라 믿는다. ㅎㅎ #include typedef long long int ll; ll fenwick[2048][2048..
최초 글 발행일 2021. 01. 15.마지막 업데이트 일자 2023. 08. 10. https://blog.koder.page/solvedac-guideline/ 알고리즘 입문자를 위한 백준/솔브닥(solved.ac) 사용백과본 글은 솔브닥 시즌 업데이트마다 갱신되고 있습니다. 마지막 업데이트 일자 2024. 07. 07. 21년 언저리 즈음 백준에 solved.ac (편의상 솔브닥이라 칭하겠습니다.) 가 정식으로 편입되어서 24년 현재blog.koder.page 최신 버전 글을 재발행하였습니다.
기본적인 BFS 문제 bfs만 짜면 AC받을수 있다. www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net #include #include #include using namespace std; vector v[123]; queue q; int visit[123] = {0}; void bfs(){ while(!q.empty()){ int node = q.front(); q.pop(); for(int i=0; i
정올 너무 맵다 ㅗㅜㅑ www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 각 회원들에 대하여 전부 bfs를 돌려본 다음 bfs의 결과 중 최대값이 점수가 된다. #include #include #include #include using namespace std; vector v[56]; queue q; int visit[56] = {0}; vector ans; void bfs(){ while(!q.empty()){ int node = q.front(); q.p..
정올 초등부 문제. 아니 초등학생이 이런거 풀수 있어요....? 너무 무섭다 ㄷㄷㄷ www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 이 문제는 사이클의 갯수를 세는 문제이다. 문제에 주어진 케이스의 경우, 1에서 시작하는 사이클 한개, 3에서 시작하는 사이클 한개, 5에서 시작하는 사이클 한개. 이 세가지 케이스에서 나오는 갯수 3이 정답이고, 사이클을 이루는 원소들은 1 3 5이다. 이를 구현하면 #include int arr[123] = {0..