목록Algorithm (154)
cgy12306
100000개의 테스트 개수를 주고, 1부터 1,000,000,000까지의 범위를 주어졌을 때 일반적으로 코드를 짜면 시간초과가 발생한다. 세그먼트 트리를 이용해 문제를 해결하면 시간초과를 방지할 수 있음 // https://www.acmicpc.net/problem/10868 // 최솟값 #include #include using namespace std; int arr[100002]; int tree[4 * 100002 + 4]; int INF = 1000000001; int init(int start, int end, int node) { if(start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; return tree[..
// https://www.acmicpc.net/problem/10026 // 적록색약 #include #include using namespace std; int N; char map[101][101]; int visited[101][101]; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; void dfs(int x, int y, int cnt) { visited[x][y] = cnt; for (int i = 0; i = N || ny >= N || map[x][y] != map[nx][ny]) continue; if ..
// https://www.acmicpc.net/problem/2589 // 보물섬 #include #include #include #include using namespace std; int N, M; char map[51][51]; int visited[51][51]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1, -1 }; int bfs(int x, int y) { memset(visited, 0, sizeof(visited)); queue q; q.push({ x, y }); visited[x][y] = 1; while (!q.empty()) { x = q.front().first; y = q.front().second; q.pop(); for (int ..
// https://www.acmicpc.net/problem/5014 // 스타트링크 #include #include using namespace std; int F, S, G, U, D; int dx[2]; int visited[1000002]; queue q; int bfs(int start) { q.push(start); visited[start] = 1; while (!q.empty()) { int x = q.front(); q.pop(); if (x == G) return visited[x] - 1; for (int i = 0; i F) continue; if (visited[nx] == 0) { vis..
// https://www.acmicpc.net/problem/1987 // 알파벳 #include #include #include using namespace std; int R, C, ans = 0; char map[22][22]; bool visited[27]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0 , 0, 1, -1 }; void dfs(int x, int y, int cnt) { ans = max(ans, cnt); for (int i = 0; i = R || ny >= C) continue; if (!visited..
// https://www.acmicpc.net/problem/18119 // 단어 암기 #include #include using namespace std; int N, M; int alp = 0; int arr[10001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for (int i = 0; i s; for (int j = 0; j o >> x; alp ^= 1
// https://www.acmicpc.net/problem/16398 // 행성 연결 #include #include #include #include using namespace std; long long N, parent[1002], map[1002][1002]; vector Edges; int Find(int x) { if (parent[x] == x) return x; else return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void kruskal() { long long sum = 0; for (..
초기에 발전소끼리 Union 해준뒤 kruskal 알고리즘을 돌리면 쉽게 풀리는 문제이다. // https://www.acmicpc.net/problem/10423 // 전기가 부족해 #include #include #include #include using namespace std; int N, M, K; int parent[1002]; vector city; vector powerPlant; int Find(int x) { if (parent[x] == x) return x; else return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else ..