어쨌든 공부하는 블로그

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::..

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(..

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; ..