답은 알고리즘 뿐이야!

문제 출처 : 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/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/1780 풀이 : 분할 정복 문제입니다. 만약 전체가 같은 수로 이루어 지지 않았다면 전체를 9구역으로 분할 한 후 계속 검사해 나갑니다. 저는 type 변수를 스위치 처럼 사용 하였습니다. 현재 분할 된 부분의 전체를 탐색하고 스위치가 켜지면 하나의 수로 채워진 종이가 아닌 경우이고 꺼져있으면 하나의 수로 채워진 종이라고 인식합니다. 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 #include int n,arr[2187][2187],score[3]; void divide(int x,int y,int size) {..

문제 출저 : https://www.acmicpc.net/problem/1725 풀이 : 스택으로도 풀 수 있고, 분할 정복으로도 풀 수 있는 문제입니다. 스택으로는 아직 안 풀어 봐서 다음에 기회가 되면 올리도록 하고 분할 정복으로 설명하겠습니다. 이 문제는 분할 한 두 영역에 겹쳐서 최댓값이 존재 할 수도 있기 때문에 병합을 할 때 매번 중앙부터 시작해 양 옆으로 확장 해 나가면서 현재 구해진 값 과 중간 값 중 최댓값을 찾는 과정을 병행 해주어야 합니다. 그 과정은 중앙에서 부터 양옆으로 탐욕적으로 넓혀 나가시면 됩니다. 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 3..

문제 출저 : https://www.acmicpc.net/problem/2447 풀이 : 분할 정복 문제입니다. 출력을 자세히 보면 *** * * *** 위 의 모양 처럼 중간 부분만 뻥 뚤린 형태를 유지하고 있음을 유추할 수 있습니다. 따라서 중간 부분만 출력 하지 않도록 9가지 구역으로 분할 후 정복하시면 됩니다. 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 #include int n; char arr[7000][7000]; void divide(int y,int x,int size,int cnt) { if (size == 1||cnt==4) { arr[y][x] = cnt==4 ? '..