뱀귤 블로그

문제 링크 : https://www.acmicpc.net/problem/2470

합이 0에 가장 가까운 두 용액을 구하는 문제입니다.

N이 최대 100,000 인데 시간제한 1초인데다가 언어별 추가시간이 없기 때문에 O(n)으로 풀어야 합니다.

비효율적으로 푸는 방법은 N개중에서 2개를 뽑는 콤비네이션을 완전탐색으로 돌려서 푸는 방법이 있긴 합니다.

O(N)에 푸는 방법은 우선 배열을 정렬합니다.

그다음 가장 가장 작은 숫자인 arr[0]과 가장 큰 숫자인 arr[n-1]을 더한 후에 max 값과 비교합니다.

만약에 두 숫자의 합이 0보다 크다면 arr[n-1]의 절대값이 arr[0]보다 더 크기때문에 arr[n-1]의 인덱스를 하나 줄여줍니다.

반대로 두 숫자의 합이 0보다 작다면 arr[0]의 인덱스를 하나 증가시킵니다.

이렇게 배열의 양쪽 끝에서부터 서로 줄여가면서 합이 0에 가장 가까운 숫자를 구하면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/10835

dp 문제입니다.

dp라기보다는 메모이제이션 문제에 가깝다고 생각합니다.

처음에는 단순하게 재귀를 돌려서 했는데 생각해보면 N이 최대 2000이기 때문에 당연히 터지는 거였습니다.

dp를 통해서 한번 방문했던 인덱스는 생략하면서 점수를 저장해나갑니다.

모든 경우를 보며 max 값을 구하면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/2583

사각형을 놓았을 때 분리되는 영역이 몇개고 넓이가 어떻게 되는지 구하는 문제입니다.

영역의 갯수와 넓이는 DFS로 간단히 구할 수 있기 때문에 관건은 사각형을 놓는 방법입니다.

일반적으로 사용하는 2차원 배열은 (0, 0)이 왼쪽 위고 (N, M)이 오른쪽 아래인데, 문제에서는 왼쪽 아래가 (0, 0)이고 오른쪽 위가 (N, M)입니다.

하지만 괜히 어렵게 생각할 필요 없이 똑같이 구현하면 됩니다. 결국 모양만 다르게 나올 뿐 구하는 것에는 변함이 없습니다.

주어진 좌표들을 가지고 2차원 배열을 1로 채우고 나중에 DFS로 좌표값이 0인 부분만 세주면 됩니다.

오름차순으로 출력해야 하기 때문에 우선순위 큐를 사용하였습니다.

문제 링크 : https://www.acmicpc.net/problem/1670

원탁에 있는 사람들이 손을 교차하지 않고 모두 악수하는 경우의 수를 찾는 문제입니다.

문제를 읽으면 Dynamic Programming 이 떠오릅니다.

핵심은 두 사람이 악수를 하면 그 두 사람을 기준으로 두 개의 영역이 만들어집니다.

그럼 그 영역에 있는 사람들끼리 악수하는 경우를 구하면 됩니다.

위 사진을 보면 총 6명의 사람이 원탁에 앉아있는 상황입니다.

만약 가운데 있는 두 사람이 악수를 한다면 저렇게 빨간 선처럼 악수를 하겠죠.

저 선을 기준으로 서로 맞은 편에 있는 사람들은 악수를 하지 못합니다.

결국 선을 기준으로 파란색 동그라미친 두개의 영역이 생성된거죠.

위 사진은 한가지 예시일 뿐이고, 사람이 많아질수록 경우의 수는 더 커집니다.

위 사진처럼 8명의 사람이 있다고 가정합니다.

그럼 총 4가지의 큰 경우의 수가 생깁니다.

1. 0과 1이 악수하는 경우

2. 0과 3이 악수하는 경우

3. 0과 5가 악수하는 경우

4. 0과 7이 악수하는 경우

1. 0과 1이 악수한다면 사실상 영역이 나누어지지 않습니다.

dp[0]인 거죠. 나머지 인원은 6명이기 때문에 6명이 악수하는 경우의 수 dp[6] 입니다.

2. 0과 3이 악수한다면 위에는 2명, 아래는 4명이 생깁니다.

dp[2] * dp[4] 가 2번의 모든 경우의 수입니다.

3. 0과 5가 악수한다면 위에 4명 아래 2명 = dp[4] * dp[2]

4. 0과 7이 악수한다면 dp[6] * dp[0]

이렇게 4가지의 모든 경우의 수를 구한다음에 더해주면 총 경우의 수가 나옵니다.

0이 2, 4, 6과 악수하지 않는 이유는 사람이 홀수면 악수하는 인원이 딱 나누어 떨어지지 않기 때문입니다.

문제 링크 : https://www.acmicpc.net/problem/11920

버블 정렬의 중간 과정을 구하는 문제입니다.

N이 최대 10,000 이기 때문에 일반적인 버블 정렬을 돌리면 당연히 터집니다.

이 문제는 버블 정렬의 특징을 이해해야 합니다.

버블 정렬 한번 도는 과정이 총 N번 진행된다고 할 때, 정렬을 한번 수행할 때마다 가장 큰값은 맨 뒤로, 더 작은 값들은 한번씩 앞으로 이동합니다.

만약 K 번 수행한다면 가장 큰 수부터 K 번째 수까지 전부 뒤로 정렬된 상태입니다.

그러므로 우선순위큐를 이용하여 사이즈가 K만큼 유지되도록 만드는게 핵심입니다.

만약 우선순위큐에 K개의 숫자가 들어있는데 새로운 값이 들어온다고 가정합니다.

1. 기존의 K개의 숫자들보다 작은 값이 들어온다.

 => pq.poll() 하기 때문에 바로 출력됨

2. 기존의 K개의 숫자들과 비슷한 값이 들어온다.

 => pq.poll() 할 때 기존에 있던 값 중 가장 작은 값이 출력됩니다.

가장 작은 값이 출력되는 것은 똑같습니다.

하지만 핵심은 pq에는 항상 가장 큰 K개의 숫자들만 유지된다는 사실입니다.

만약 pq에 [4 5 6 7] 이렇게 들어있고 새로운 값으로 1, 3, 2 순으로 들어온다면 [1, 3, 2, 4, 5, 6, 7] 순으로 출력될겁니다.

문제 링크 : https://www.acmicpc.net/problem/1377

백준 1838번 과 똑같은 유형의 문제입니다.

요점은 정렬이 완료되었을 때의 i를 구하는 것입니다.

하지만 1838번과 다른 점이 한가지 있습니다.

1838번은 문제에서 서로 다른 N 개의 숫자가 들어온다고 되어있지만 1377번은 그런 설명이 없습니다.

즉, 중복된 숫자가 들어올 수 있다는 뜻입니다.

그러므로 중복된 숫자가 들어왔을 때 stable 정렬을 유지하기 위해 인덱스가 큰 건 뒤로 가도록 compareTo 조건을 살짝 수정해주면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/1517

문제 이름은 버블소트지만 버블소트로 풀면 틀리는 문제입니다.

N이 최대 500,000 이죠 O(n^2)을 돌리면 당연하게도 시간초과가 납니다.

우리가 구해야 하는건 swap하는 갯수입니다.

버블소트에서 swap이 발생하는 조건은 앞의 숫자가 뒤에 숫자보다 클 때입니다.

즉 a[i] > a[i+1] 일 때 swap이 발생합니다.

그러므로 머지 소트를 이용하여 정렬을 하되, 앞의 숫자가 뒤의 숫자보가 큰 경우에 카운트를 해주면 동일하게 swap 횟수를 구할 수 있습니다.

swapCount에 (mid+1-i) 를 더하는 이유는 왼쪽 배열에 남아있는 숫자만큼 계속 swap이 발생하기 때문입니다.

문제 링크 : https://www.acmicpc.net/problem/1838

문제 이름은 버블 정렬이지만 버블 정렬로 풀면 틀리는 문제입니다.

버블 정렬의 시간복잡도는 O(N^2)이고 N은 최대 500,000 이기 때문에 살짝만 계산해봐도 시간초과가 나온다는 사실을 알 수 있습니다.

이 문제는 버블 정렬의 특징을 이용해서 풀어야 합니다.

버블정렬은 간단히 설명하자면 0번 인덱스부터 N-2번 인덱스까지 진행하면서 arr[i] 와 arr[i+1]을 비교하여 swap 하는 정렬입니다.

위와 같은 과정을 최대 N번 반복하면 정렬된 배열을 얻을 수 있습니다.

이때 문제에 나와있는 것처럼 flag를 써서 swap 여부를 체크하는 것처럼 약간의 최적화를 할 수 있습니다.

아무튼 다시 문제로 돌아오자면 핵심은 몇 번만에 정렬이 완료되었는가를 알아내는 것입니다.

그리고 정렬이 완료되었다는 것은 for문을 아무리 돌아도 각 변수의 이동이 없다는 것을 의미합니다.

이걸 또 다른말로 하면 변수의 이동이 존재한다면 정렬은 끝나지 않았다 가 됩니다.

서론이 길었는데 간단히 말하자면

정렬하기 전 인덱스와 정렬 후 인덱스를 비교해서 가장 많이 이동한 횟수를 출력한다

가 해법입니다.

그런데 무조건 많이 이동한 횟수는 아닙니다.

예를 들어 5 4 3 2 1 은 한바퀴 돌면 4 3 2 1 5가 되는데 가장 큰수는 마지막까지 이동하기 때문에 이동횟수가 가장 많습니다.

하지만 실제로는 한바퀴만 돌았죠

버블 정렬을 한 바퀴 돌때마다 큰 수들은 뒤로 끝까지 쭉쭉 밀립니다.

하지만 작은 수는 앞으로 한칸씩 땡겨집니다.

그렇기 때문에

정렬하기 전 인덱스 - 정렬 후 인덱스 > 0 인 후보들 중에서 고릅니다.

그렇다면 가장 작은 수를 기준으로 하면 되지 않느냐 할수도 있는데 그건 또 아닙니다.

예를 들어 3 1 4 2 5 를 정렬하면

가장 작은 수인 1은 앞으로 한칸만 간 후에 더이상 이동하지 않습니다.

하지만 완전한 정렬이 되기 위해서 2는 두칸을 이동하죠

그렇기 때문에 max 값을 구하는 겁니다.

가장 많이 이동한 값이 곧 마지막 까지 이동한 값이고 이것이 정렬을 하기 위해 얼만큼 반복했는지를 나타냅니다.

저는 현재 index와 value를 갖고 Comparable 인터페이스를 상속받아 value 를 기준으로 정렬되는 클래스를 만들었습니다.

그리고 입력받은 값을 우선순위큐에 담으면 value를 기준으로 정렬된 자료구조를 구할 수 있습니다.

그리고 기존에 갖고 있던 index값과 현재 idx값을 비교하여 최대값을 찾아 출력하였습니다.