전체 글

코드#include #include #include #include #include using namespace std;typedef long long ll;int res;string s, n;void FASTIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}int main() { FASTIO(); cin >> n; s = n; // 비교할 값 저장 while (1) { if (n.length() == 1) { string m = "0"; m += n; // 문자열 앞에 더해주어야 함 n = m; } int tmp = 0; string stmp; for (int i = 0; i 풀이문제에 있는 조건을 그대로..

코드#include #include #include #include #include using namespace std;bool isfour, isthree, istwo, iscon;int a[15], b[5], four, three, two, cnum;string ca, cb;void FASTIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}int main() { FASTIO(); for (int i = 0; i > ca >> cb; int num = stoi(cb); a[num]++; if (ca == "R") { b[0]++; } else if (ca == "B") { b[1]++; } else if..

코드1 (next_permutaion 사용)#include #include using namespace std;int n, a[10], res;int main() { cin >> n; for (int i = 0; i > a[i]; sort(a, a + n); do { int tmp = 0; for (int i = 0; i 코드2 (순열 구현)#include using namespace std;int n, a[10], res;void permutation(int n, int r, int depth) { if (r == depth) { int tmp = 0; for (int i = 0; i > n; for (int i = 0; i > a[i]; permutation(n, n, 0); cout 풀이n의..

펜윅트리 (Fenwick Tree, Binary Indexed Tree, BIT)펜윅트리는 트리 구조를 1차원 배열로 구현한 자료구조로, 각 위치에서 특정 구간을 대표하는 값을 저장하여 빠르게 구간 합 등을 계산할 수 있다. 업데이트와 쿼리 연산의 시간 복잡도는 O(logN)이다. 1기반 인덱싱을 사용하기 때문에 배열의 크기를 N + 1 (N은 데이터의 크기)로 설정하는 경우가 많다. 세그먼트 트리보다 상대적으로 구현이 간단하고 메모리 사용량이 적다.  주요 연산 비교연산펜윅 트리세그먼트 트리구간 쿼리O(logN)O(logN)단일 업데이트O(logN)O(logN)구간 업데이트O(NlogN)O(logN) (Lazy Propagation 사용 시)메모리 사용량O(N)O(4 * N) 펜윅 트리 코드#inclu..

그래프에서 음의 사이클 구하기벨만 포드 알고리즘을 이용하는 것과 플로이드 워셜 알고리즘을 이용하면 그래프에서 음의 사이클을 찾아낼 수 있다. 플로이드 워셜 알고리즘을 이용한 방법mp를 그래프라고 할 때, 플로이드 워셜 알고리즘에서 사이클의 존재 여부는 mp[i][i] 값을 통해서 확인할 수 있다. 플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하기 위해 각 정점 i에서 j로 가는 최단 경로를 mp[i][j]에 저장하게 된다.사이클이 없는 경우라면, 어떤 정점에서든 자신으로 돌아오는 경로가 존재하지 않으므로 mp[i][i]는 초기화된 값인 INF를 유지하게 된다.반면, 사이클이 존재하는 경우 해당 경로의 길이를 갱신하게 되어 mp[i][i] (자기 자신에게로 돌아오는 경로)가 INF가 아닌 값..

느리게 갱신되는 세그먼트 트리 (Lazy Propagation)느리게 갱신되는 세그먼트 트리(Lazy Propagation)는 세그먼트 트리에서 구간 업데이트를 더 효율적으로 처리하기 위해 사용하는 기법이다. 구간의 여러 값을 한 번에 갱신하고, 그 후에 구간에 대한 정보를 빠르게 얻어야 할 때 사용된다. 1. 느리게 갱신되는 세그먼트 트리란?기본 세그먼트 트리는 특정 구간의 값(합, 최대값 등)을 빠르게 쿼리할 수 있게 해준다. 그런데 만약 구간 내 모든 값에 동일한 연산(ex. 더하기)을 여러 번 적용해야 하는 경우, 기본 세그먼트 트리로는 비효율적일 수 있다. 최악의 경우 nlogn의 시간이 걸릴  수 있기 때문이다. 이때 느리게 갱신되는 세그먼트 트리를 사용하면 구간 전체에 대한 업데이트를 지연시..

세그먼트 트리세그먼트 트리는 효율적인 구간 연산을 처리하기 위해 사용되는 트리 구조이다. 주어진 배열에서 특정 구간의 합이나 최대값/최소값 등과 같은 정보를 빠르게 구해야 할 때 유용하다. 이 구조를 사용하면 배열의 값을 업데이트하거나 구간의 값을 구하는 작업을 빠르게 처리할 수 있다. 1. 세그먼트 트리란 무엇인가세그먼트 트리는 주어진 배열을 관리하는 트리 구조로, 배열의 특정 구간에 대한 연산(예: 합, 최대값, 최소값 등)을 효율적으로 처리하는 데 사용된다. 일반적으로 배열의 크기가 커질수록 배열의 구간 합이나 구간 최대/최소를 구하는 시간이 오래 걸리는데, 세그먼트 트리를 사용하면 로그 시간(O(logN)))에 이런 연산을 처리할 수 있다. 즉, 세그먼트 트리는 배열의 구간 정보를 미리 저장해 두..

코드#include #include #include #include #include using namespace std;const int INF = 987654321;int T, n, m, t, s, g, h, a, b, d, x;vector> adj[2003];vector wh, res;int distS[2003], distG[2003], distH[2003]; // s, g, h에서 각각의 최단 거리void INPUT() { cin >> n >> m >> t; cin >> s >> g >> h; for (int i = 0; i > a >> b >> d; adj[a].push_back({b, d}); adj[b].push_back({a, d}); } ..

코드#include #include #include #include #include using namespace std;int n, m,a,b, visited[103],res=987654321,resnum;vector adj[103];// bfsint bfs(int x) { fill(visited, visited + 103, 0); queue q; q.push(x); visited[x] = 1; while (!q.empty()) { int pn = q.front(); q.pop(); for (int i : adj[pn]) { if (!visited[i]) { visited[i] = visited[pn] + 1; q.push(i); } } } int tmp = 0; for (int..

코드#include using namespace std;const int INF = 987654321;int n,m,b, a[503][503], res = INF, max_h = -1, min_h = 257,oh;// 높이 0 ~ 256, 칸의 크기 500*500// 브루트포스로 풀 수 있을 듯// 땅 높이 가장 높은 거, 낮은 거 계산// 그 사이에 높이를 설정하고, 낮으면 더하고 높으면 깎기// 다 돌렸는데 블록이 음수로 나오면 적용 Xvoid go() { int tmp = min_h; // 최저점부터 탐색 while(tmp != (max_h + 1)) { int blockcnt = b; // 블록의 개수 int tmptime = 0; // 걸린 시간 for(int i = 0; i a[i..