어쨌든 공부하는 블로그

정렬되어 있는 배열에서 이진 탐색으로 원하는 key의 인덱스를 반환해 주는 함수들이다lower_bound: 원하는 val 값과 같거나 큰 값(이상)이 최초로 등장하는 인덱스를 반환한다upper_bound: 원하는 val 값보다 큰 값(초과)이 최초로 등장하는 인덱스를 반환한다 lower_bound와 upper_bound의 코드는 아래와 같다사실상 다른 건 다 동일하고 if문에서 이하인지 초과인지를 체크하는 부분만 다르다// lower_boundtemplate ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val){ ForwardIterator it; iterator_traits::differenc..

주의할 점.중복 요소를 제거할 배열이 정렬된 상태여야 한다v.erase(unique(v.begin(), v.end()), v.end());코드부터 보자면 위와 같이 작성해 주면 중복된 요소가 제거된 상태가 된다 erase 함수는 첫번째 인자로 들어간 위치부터 두번째 인자로 들어간 인자까지의 요소를 제거한다unique 함수는 중복되는 요소를 없애는 함수이다 unique 함수의 코드를 알아보자template ForwardIterator unique (ForwardIterator first, ForwardIterator last){ if (first==last) return last; ForwardIterator result = first; while (++first != last) { if ..

https://www.acmicpc.net/problem/9095풀이일단 그냥 무턱대고 값을 구해보면dp[1] = 1dp[2] = 2dp[3] = 4dp[4] = 7dp[5] = 13으로, 규칙성을 발견할 수 있다dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]과 같은 점화식을 찾을 수 있다 5를 만드는 경우의 수를 구할 때4를 만드는 모든 경우의 수에 +1를 해주면 5를 만들 수 있고3을 만드는 모든 경우의 수에 +2를 해주면 5를 만들 수 있고2를 만드는 모든 경우의 수에 +3을 해주면 5를 만들 수 있다(4 이상의 차이부터는 하나의 숫자만 더해서 목표 숫자에 도달할 수 없음)따라서 4, 3, 2를 만들 수 있는 모든 경우의 수를 더해주면 그것이 곧 5를 만들 수 있는 모든 ..

https://www.acmicpc.net/problem/2579풀이n번째 계단을 밟았을 때의 최대 점수를 구하는 방식을 반복하면 된다 dp[n]은 n번째 계단을 밟았을 때 최대 점수를 뜻하고, arr[n]은 n번째 계단의 점수라고 치자 dp[1] = arr[1]이다dp[2] = arr[2] + arr[1]이다dp[3] = arr[3] + arr[2] 또는 arr[3] + arr[1] 둘 중 큰 값이다dp[4] = arr[4] + arr[3] + arr[1] 또는 arr[4] + arr[2] + arr[1] 둘 중 큰 값이다dp[5] = arr[5] + arr[4] + arr[2] + arr[1] 또는 arr[5] + arr[3] + arr[2] 또는 arr[5] + arr[3] + arr[1] 중 큰 ..

https://www.acmicpc.net/problem/2667 제출 코드#include #include #include using namespace std;int n;string arr[26];int dx[4] = { 1, -1, 0, 0 };int dy[4] = { 0, 0, 1, -1 };int dfs(int x, int y){ // 배열 범위를 초과하거나 0일 경우 리턴값 0 if (x = n || y = n || arr[x][y] == '0') return 0; arr[x][y] = '0'; int cnt = 1; // 인자로 들어온 좌표의 상하좌우를 체크해서 cnt 세기 for (int i = 0; i > n; for (int i = 0; i..

https://www.acmicpc.net/problem/11724제출 코드(DFS)#include #include using namespace std;vector vec[1001]; // 연결된 정점들을 vector에 저장bool visit[1001]; // 방문 여부 체크용void dfs(int node){ visit[node] = true; // 연결된 노드들을 체크 for (int i = 0; i > n >> m; while(m--) { int u, v; cin >> u >> v; // 방향 없는 그래프이기 때문에 u와 v 양쪽에 push vec[u].push_back(v); vec[v].push_back(..

https://www.acmicpc.net/problem/11660 풀이1우선 누적합을 이용해 2차원 배열에 값을 채워넣는다(배열의 (i, j)에는 (0, 0)부터 (i, j)번째까지의 모든 값이 담긴다. 즉, (i + 1, 0) 위치에는 (i, n)까지의 합에 (i + 1, 0) 번째 수가 더해진 값이 들어가게 된다)답은 각 행의 x2의 누적합 - x1의 누적합을 행의 갯수만큼 반복하여 더해주면 된다위 배열이 주어졌다고 가정했을 때, 누적합을 이용해 배열을 채우면 아래와 같다제출 코드#include using namespace std;int ps[1025][1025];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ..

https://www.acmicpc.net/problem/14929 풀이출력값은 x1 * x2 + x1 * x3 + ... x1 * xn + x2 * x3 + x2 * x4 + ...x2 * xn ... x(n-1) * xn 이므로정리해서 x1(x2 + x3 + ... xn) + x2(x3 + x4 + ... xn) 와 같이 표현할 수 있다이때 xi부터 xn까지 하나하나 더하는 과정을 n번 반복하면 시간초과가 되기 때문에 누적합을 이용한다 제출 코드#include using namespace std;int arr[100001];int ps[100001];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; ..

https://www.acmicpc.net/problem/3474 풀이오른쪽 끝에 나오는 0의 개수는 10이 얼마나 곱해졌는가를 구하면 된다그렇다면 10이 얼마나 곱해졌는가는 2와 5가 몇 개 곱해졌는가를 구하면 된다이때 2가 곱해진 횟수와 5가 곱해진 횟수 중 더 작은 횟수가 10이 곱해진 횟수라고 보면 되는데, 2는 모든 짝수가 해당되므로 팩토리얼 연산에서는 무조건 5가 곱해진 횟수보다 많다 따라서 5가 곱해진 횟수를 세면 되는데, N!을 계산하기 위해 1부터 N까지 루프문을 돌며 5가 등장하는 횟수를 세면 시간초과가 된다(N의 최댓값이 10억이기 때문) N이 125라면, 1부터 125까지를 곱해주어야 한다. 1부터 125까지의 수 중에 5의 배수가 등장하는 횟수는 125를 5로 나누어 쉽게 구할 수..

우선 두 수의 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눠주면 구할 수 있다따라서 최대공약수(GCD)를 구하는 것이 중요하다 a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다1. a % b = r, 나머지의 값을 구한다2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다3. r을 r'로 나눈 값의 나머지(r'')를 구한다... 1. 재귀함수로 구현int gcd(int a, int b){ if (a % b == 0) return b; return gcd(b, a % b);} 2. 반복문으로 구현int gcd(int a, int b){ int r = a % b; while(r) ..