MathTrauma

완전 탐색을 하지 않고 해결하는 방법을 모르겠다. 풀이 적어놓고 천천히 생각해 봐야겠다.

문제 링크 : https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 가장 앞자리부터 가능한한 큰 수로 교환하고, 교환 횟수가 남아있다면 그 다음 자리로 가서 이를 반복한다. 알고리즘은 더 설명할 게 없고, 아래 코드에서 algorithm 라이브러리에 있는 rotate 함수를 설명하면 충분할 듯하다. rotate( arr+start , arr+p , arr+end ); arr 이 배열인 경우 [ start , end ) 에 존재하는 원소들을 p 에..

문제 링크 : https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는 '10972 다음 순열'과 같은 문제이다. 왼쪽에서 오른쪽으로 사전 순으로 순열들을 나열했다고 가정하자. 다음 순열이란 현재 순열의 오른쪽 순열일 것이고 직전 순열은 왼쪽의 것이다. 그런데 순열들을 사전 역순으로 배치했다면 이전 순열이 현재의 오른쪽의 것이 된다. 즉, 10972 번의 풀이 과정 에서 등장하는 모든 부등호를 뒤집으면 원하는 결과를 얻게 될 것이다. 10972 번 문제를 풀지 않은 경우를 위해 예를 들어 짧게 설명..

문제 링크 : https://www.acmicpc.net/problem/5905 5905번: 악당 로봇 슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 N개의 취약점을 가지고 있는데, (1 ≤ N ≤ 20) i번째 취약점은 'A', 'B', 'C' 로만 구성된 15자 이하의 문자열 S www.acmicpc.net '콤보' 라는 이름으로 패턴들이 주어진다. 검색 대상 스트링이 주어지고 거기에 콤보가 몇 번이나 발생한 것인지를 묻는다면, 평범한 스트링 문제일 것이다. 하지만 길이 K 이하의 문자열로 최대의 콤보가 발생하게 만들어야 하는 상황이니 dp 외에 뚜렷한 방법이 생각나지 않는다. 1. 필요한 정보들 (1) added[i][j] added[i][j] :콤보 i 에 1..

문제 링크 : https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 이 문제 자체 보다 생각해 봐야할 것이 있어서 기록해 둔다. 1. 방향에 대한 정보는 필요없다?! 주어진 문제이 도형은 큰 직사각형에서 작은 직사각형을 제거한 형태이다. 둘레의 길이라는 측면에서 보면 큰 직사각형을 형성하는 두 변의 길이의 합이 전체의 절반이 된다. 이 사실을 이용하면 방향에 대한 정보는 필요가 없다. 이렇게 해결하는 코드는 다음과 같다. #include using..

문제 링크 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 입력된 순서 index 와 값을 정렬했을 때 순서가 엇갈린 개수를 찾는 문제이다. 문제의 기술에서는 인접한 두 수만을 비교하지만 멀리 떨어져 있어도 언젠가는 비교해서 swap 된다. 우선 문제의 카테고리는 세그먼트 트리이지만 다른 풀이부터 보자. 1. Merge Sort 가장 직관적인 해법은 실제 버블 소트를 구현해서 swap 개수를 구하는 것이다. 그러나 $..

문제 링크 : https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최대 최소 세그먼트 트리를 Bottom-Up 방식으로 구현해 보자. 이 경우에 이미 결과를 알고 있는 토너먼트 대진표를 보면 쉽게 이해가 된다. LOL, NBA 혹은 바둑 뭐든 상관없다. Rating 이 높은 쪽이 항상 이긴다고 가정하자. 우승한 팀부터 차례로 값를 줄여가며 각 팀에 rating을 부여하면 최대 세그먼트 트리가 된다. 혹은 랭킹을..

문제 링크 : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 입력값의 컸기 때문에 걱정이 앞서서 한참 고민했던 문제이다. 그런데 결론은 효과적인 알고리즘이 필요없다는 것이었다. 절차 입력의 작은 수를 m , 큰 수를 M 이라고 하자. no 배열은 해당 수가 제곱수를 약수로 가지면 1 이고 아니면 0 이다. (우리는 0 의 개수를 세야 한다.) no[0] 은 m 이 제곱수를 가지는지 여부를 저장하고 no[M-m] 은 M 이 어떤..