답은 알고리즘 뿐이야!

문제 출저 : 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 ? '..

문제 출저 : https://www.acmicpc.net/problem/2805 풀이 : 이분 탐색 문제입니다. 절단기 높이의 최댓값은 나무 높이 들 중 최댓값이 됩니다. 기본적인 이분 탐색은 [2512] 예산 과 같으니 참고 하시면 감사하겠습니다. 그리고 나무의 최대 높이가 20억이니 꼭 결과값 저장할 때 long long int 같이 큰 정수 써주셔야합니다. 처음에 아무생각 없이 안썼다가 틀렸었습니다 .ㅠㅠ 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 #include int n, m, arr[1000000], Max, result; void parametricSearch(int s, int e) { i..

문제 출저 : https://www.acmicpc.net/problem/2512 풀이 : 이분 탐색 문제입니다. 배정 될 수 있는 예산들 중 최댓값은 요청의 최댓값을 넘을 수 없기 때문에 e를 요청중 최댓값으로 설정합니다. mid를 요청 당 최대로 배정할 예산으로 두고 아래와 같이 계산합니다. 1. 요청 당 배정할 예산 >= 요청 : 요청만큼 배정 2. 요청 당 배정할 예산 < 요청 : 배정할 예산만큼 배정 그 후 현재 배정된 총 예산과 총 예산과 비교하고 아래와 같이 이분탐색을 실행합니다 1. 배정된 총 예산 총 예산 : parametricSearch(s, mid - 1); 배정된 총 예산이 총 예산보다 작다면 예산을 조금 더 배정 할 수 있다는 말이 되므로 예산을 더 늘려서 이분 탐색을 진행하고, 반..

문제 출저 : https://www.acmicpc.net/problem/9465 풀이 : DP문제입니다. 스티커를 떼면 변을 공유하는 모든 스티커는 사용 할 수 없으니 대각선 스티커만 보면 됩니다. 아래의 그림에서 60점 스티커를 뗀다고 가정했을때, 그 전에 점수를 쌓을 수 있는 경우는 20점과 100점을 뗐을 때 뿐입니다. 그럼 20점을 뗀다면 어떨까요? 그 전에 점수를 쌓을 수 있는 경우는 70점과 50점을 뗐을 때 뿐이겠죠. 따라서 쌓는 과정에서 값의 틀어짐이 없이 잘 쌓일 거라는 사실을 알 수 있습니다. 문제의 목표는 스티커 점수의 최댓값을 찾는 것이므로 두가지 경우 중 값이 더 큰 경우를 채택하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

문제 출저 : https://www.acmicpc.net/problem/1002 풀이 : 수학 문제입니다. 두 원의 접점을 찾으면 되는 문제로 1. 접점이 두개인 경우 : 두 중점 사이의 거리 반지름의 차 2. 접점이 하나인 경우 : 두 중점 사이의 거리 == 반지름의 합(외접) || 두 중점 사이의 거리 == 반지름의 차(내접) 3. 접점이 없는 경우 : 두 중점 사이의 거리 > 반지름의 합 || 두 중점 사이의 거리 < 반지름의 차 아래의 3가지 경우만 고려해주면 됩니다! 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 int x1, x2, y1, y2, r1, r2, ..

문제 출저 : https://www.acmicpc.net/problem/1004 풀이 : 간단한 수학 문제입니다. 출발점과 도착점중 하나만 원 안에 있으면 어떠한 경로로 이동하건 간에 무조건 한번은 진입/이탈 해야하므로 진입/이탈 횟수가 하나 늘어납니다. 그러므로 원의 중심과 점 사이의 거리를 구한 뒤 그 원의 반지름 보다 작으면 원 안에 있다고 판단합니다. 필자는 실수 연산을 오차가 생기므로 피하라고 배웠기 때문에 정수형으로 점과 점사이의 거리를 구하는 과정 중 유도리 있게 제곱근을 사용하는 부분을 뺀 대신 반지름을 제곱하였습니다. 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 #include struct ci..

문제 출저 : https://www.acmicpc.net/problem/14891 풀이 : 주어진 조건대로 구현하기만 하면 되는 시뮬레이션 문제입니다. 항상 4개의 톱니바퀴가 주어지고 8개의 상태를 가지니 ch[4][9]만큼 배열을 선언해줍니다. (ch[4][8]했다가 왜오답인지만 한시간 고민했습니다... ㅠㅠ) 저는 평소에 모드연산자를 좋아하기 때문에 문제에 주어진 조건대로 모드연산자를 이용해 cnt%8이 항상 12시라 두고 오른쪽은 (cnt+2)%8, 왼쪽은 (cnt+6)%8로 비교 한 후, 1. 시계방향으로 돌면 cnt-- 2. 반시계방향으로 돌면 cnt++ cnt는 적당히 100이 넘는 8의배수로 잡아 주시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

문제 출저 : https://www.acmicpc.net/problem/11723 풀이 : 비트마스킹의 개념을 알고 있는지에 대해 묻는 문제입다. 1. k번 비트가 1인지 0인지 확인 : num & (1

문제 출저 : https://www.acmicpc.net/problem/3078 풀이 : 단순히 큐 전체를 탐색하면 O(N^2)이되므로 타임에러가 나게 됩니다 필자도 쉽게 풀려다가 타임에러 났습니다 ㅠㅠ 그래서 그때 그때 들어오는 길이만 data배열에 저장하기로 했습니다. (편의상 삽입은 push, 삭제는 pop으로 정함) 하지만 등수가 K+1등수 이상 차이나면 큐에서 팝해줘야 함으로 언제 얼마만큼의 길이가 push 됬는지는 알아야 합니다. 따라서 길이를 저장할 큐도 따로 만들어 줍니다. 모든 문자열은 항상 최대 K등수 만큼 차이나는 이전에 들어오는 문자열과 비교되고, 정확히 K등수만큼 차이나는 후에 들어온 문자열과 비교 되기 때문에 이와 같이 길이만 가지고 n번 진행하게 된다면 특정 문자열은 앞으로 K..