겨울학교에서 풀었던 문제 깔끔하게 날로 먹었다 원래는 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..
간단한 dfs문제 1번부터 순회하면서 출력해주면 반드시 사전순을 충족하게 짤 수 있다. www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net arr[]은 출력할 답을 저장하는 배열이고, visit[]은 방문여부를 저장해준다. ( 같은 수가 중복으로 나오는것을 방지하기 위해서 ) #include #include using namespace std; int n,m; int arr[10] = {0}; int visit[10] = {0}; void dfs(int k){..