어쨌든 공부하는 블로그

https://www.acmicpc.net/problem/1697풀이 (BFS)3가지 선택지(*2, -1, +1)가 존재하므로 3갈래로 계속 나눠지는 그래프를 BFS로 탐색한다고 생각하면 된다총 몇 초가 흘렀는지를 체크해야 하기 때문에 queue를 pair로 설정해주었다 제출 코드 (BFS)#include #include using namespace std;bool visited[100001];int bfs(int start, int target){ queue> q; q.push(make_pair(0, start)); visited[start] = true; while (!q.empty()) { int cur = q.front().second; int ..

https://www.acmicpc.net/problem/1389문제를 읽어보면 모든 정점에서 모든 정점까지의 거리를 전부 구해야 하므로 플로이드 워셜 알고리즘을 쓰면 되는데, 우선은 BFS로 풀이해 보았다 풀이 1 (BFS)평범한 BFS 알고리즘 기반이나, 몇 단계를 거쳐서 도달했는지 체크해야 하기 때문에 queue를 pair로 만들어 주었다처음 시작은 0단계로 시작하고, 단계를 거칠 때마다 pair의 first 부분에 +1씩 해서 계산해 준다 제출 코드 (BFS)#include #include #include using namespace std;vector v[101];int bfs(int start, int target, bool visited[101]){ queue> q; q.push..

https://www.acmicpc.net/problem/30804풀이투 포인터 알고리즘을 활용하여, 시작점을 고정시켜놓고 끝점을 늘려나다가, 과일의 개수가 2개를 초과하면 시작점을 하나씩 앞으로 당겨오는 방식을 반복과일의 개수가 2개를 초과하거나 주어진 배열 밖으로 벗어날 경우 구간의 길이를 구하여 max값을 업데이트해 준다 제출 코드#include using namespace std;int fruit[200001];int fCount[10];bool check(){ int cnt = 0; for (auto& f : fCount) if (f > 0) cnt++; return cnt > n; for (int i = 0; i > fruit[i]; while(start

https://www.acmicpc.net/problem/17626 풀이dp(제곱수의 개수)로 풀이했을 때, dp[i - 1]의 값에 +1을 하거나, 어떤 dp 값에 제곱수를 하나 더하는dp[x] + 1 중 가장 작은 값을 선택해 나가는 식으로 진행하면 된다만약 13의 제곱수의 개수를 구해야 한다고 했을 때, 제곱수로 13을 만들 수 있는 경우의 수는3^2 + 1 + 1 + 1로 표현되는 12에 +1 하거나또는 3^2으로 표현되는 9에 +2^2 또는 2^2로 표현되는 4에 +3^2 하는 식으로 제곱수를 하나 더함으로써 만들 수 있다따라서 가능한 경우 중 가장 작은 값을 골라주면 된다 제출 코드#include using namespace std;int dp[50001];int main(){ ios::..

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