답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/3006 풀이 : 세그먼트 트리 문제입니다. 각 숫자가 자신의 자리를 찾아가는데 항상 작은 숫자는 왼쪽 큰 숫자는 오른쪽으로 가기 때문에 홀수번째 일때는 왼쪽숫자의 갯수, 짝수번째는 오른쪽 숫자의 갯수로 옮기는 횟수를 쉽게 구할 수 있습니다. 각 숫자의 위치를 따로 저장해주고 세그먼트 트리에 각 숫자의 위치의 값을 1로 채웁니다. 그다음 세그먼트 트리를 활용하여 1. 홀수번째 : 찾으려는 값의 왼쪽 범위의 구간합 2. 짝수번째 : 찾으려는 값의 오른쪽 범위의 구간합 을 구하시면 됩니다. 구하신 후에는 찾으려는 값의 세그먼트 트리에 저장된 정보를 0으로 바꾸고 업데이트 시키시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

문제 출처 : https://www.acmicpc.net/problem/18111 풀이 : 완전 탐색 문제입니다. 각 높이별로 블록이 몇 개 있는지 저장한 후 각 높이를 탐색하여 조건에 맞게 계산한 후 최댓값을 뽑아내면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; int n, m, b, a[257], result = 1e9, hei, i, j, ret, bb; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); for (cin >> n >> m >> b; i > ..

문제 출처 : https://www.acmicpc.net/problem/6549 풀이 : 스택 or 분할정복 + 세그먼트 트리 로 풀 수 있는 문제입니다. 저는 분할정복 + 세그먼트 트리로 풀었고 세그먼트 트리로 구간의 최솟값의 인덱스를 저장하여 최솟값 왼쪽 구간과 최솟값 오른쪽 구간으로 나누어서 분할 정복을 시행하였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include using namespace std; typedef long long ll; int n, base, hei..

출처 : https://www.acmicpc.net/problem/2094 풀이 : y, x가 주어졌을때 y~x 사이의 범위에서 최댓값이 x이고 두번째로 큰 값이 y인지 묻는 문제입니다. y~x 사이의 범위의 최댓값은 세그먼트 트리로 구하면 되고 그거완 별개로 모든 연도의 강수량 정보가 주어지는 것은 아니기 때문에 y와 x의 강수량이 주어졌는지 확인해주셔야합니다. 따라서 3가지의 케이스를 검사해야합니다. case 1: x년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 x년도의 강수량보다 작은가 case 2: y년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 y년도의 강수량보다 작은가 case 3: x년도의 강수량이 있고, y년도의 강수량이 있을때 y ~ x 사이의 모든값이 주어져있는가 ..

문제 출처 : https://www.acmicpc.net/problem/3830 풀이 : disjoint-set (Union-Find) 문제입니다. find를 할때마다 속도를 개선시켜주기 위해 부모를 루트로 지정해주고 무거운 정도를 루트 부터 1촌 부모까지의 차이로 저장해주고, Union 연산을 할때 점화식을 세울때 주의해서 세워주시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include typedef long long ll; int n, m, a, b, c, parent[100001],cnt; ll..

문제 출처 : https://www.acmicpc.net/problem/3176 풀이 : LCA 문제입니다. LCA를 구하는 과정에 Max값과 Min값을 구하는 과정을 포함시켜 두 도시 사이의 경로 중 최소 최대값을 찾으시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #include using namespace std; typedef pair pi; int n, k, a, b, c; ..

문제 출처 : https://www.acmicpc.net/problem/3860 풀이 : 벨만-포드 문제입니다. 1. 입구는 ( 0 ,0 ) 출구는 ( W - 1, H - 1 ) 고정. 2. 묘비가 있는 칸은 이동 불가능 3. 귀신 구멍은 텔레포트 (시간도 이동) 4. 묘지를 벗어날 수 없음 5. 출구에 도착하면 바로 탈출 (출구에서 다른 칸으로 이동하지 않음) 6. 제로 사이클은 신경쓰지 않는다. 위 여섯가지 조건으로 엣지를 구성하여 벡터에 채운다음 총 V * E 번 계산하면서 음의 사이클, 탈출 가능성을 판단 하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ..

문제 출처 : https://www.acmicpc.net/problem/11003 풀이 : 슬라이딩 윈도우로 푸는 문제이고 덱으로 풀었습니다. 값을 받아서 덱의 맨 뒤에서 자신보다 큰 수를 다 팝한후 푸쉬합니다. 그 이유는 현재 윈도우에서 현재값보다 큰 수들은 최솟값 후보가 될 수 없기 때문입니다. 최솟값을 출력할 때에는 현재 덱의 맨 앞의 값이 윈도우에 포함되는지 여부를 파악한 후 포함되지 않으면 최솟값이 아니니 팝하고 포함되면 출력합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; struct num { int v, s; num(int v, ..

문제 출처 : https://www.acmicpc.net/problem/2517 풀이 : 분할정복으로 풀 수 있는 문제입니다. 머지소트를 진행하면서 왼쪽보다 오른쪽이 더 클때 순위를 왼쪽의 남은 숫자 만큼 빼주시면 됩니다. 원리는 우측에 있는 러너가 좌측으로 이동할때 좌측에 남은 숫자만큼 추월을 한다고 생각하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include struct num { int v, r; num(int v, int r) :v(v), r(r) {} num() {} }; int n, t, r..

문제 출처 : https://www.acmicpc.net/problem/1103 풀이 : DFS 문제입니다. BFS로 풀게되면 이전에 온 경로를 알 수 없으므로 DFS를 사용하여 풀어야 합니다. DFS로 현재까지 온 경로를 체크하면서 오면 중복해서 가는 지점을 찾을 수 있어 무한대로 움직이는 경우를 찾을 수 있습니다. 그리고 시간 단축을 위해 메모이제이션 개념을 사용해 그 지점에 도착했을때 현재 이동한 횟수가 이전에 그 지점에 도달했을때의 횟수보다 작다면 스킵해줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include int n, m, ret, visit[50][50], cache[5..