어쨌든 공부하는 블로그

정렬되어 있는 배열에서 이진 탐색으로 원하는 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..