뱀귤 블로그

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

모든 마을에서 출발하여 X 마을에 들렀다가 다시 돌아오는 길이 가장 큰 값을 구하는 문제입니다.

N이 크지 않아서 플로이드와샬, 다익스트라 어느것으로 해도 풀리는 문제입니다.

하지만 X에 대한 최단 경로만 구하면 되는 상황에서 모든 정점에 대해 다익스트라를 하는 것은 비효율 적입니다.

그래서 'X마을 -> 다른 모든 마을' 의 최단경로와 '다른 모든 마을 -> X마을' 의 최단경로.

단 두번만 다익스트라를 돌려서 문제를 해결할 수 있습니다.

X마을에서의 최단 경로는 시작점을 X로 놓고 하면 되지만

X마을로 향하는 최단 경로는 조금 다릅니다.

입력받는 간선의 값을 전부 뒤집어서 넣은 뒤에 시작점을 X로 하여 구해야 합니다.

인접행렬을 예로 들면 원래는 edge[v1][v2] = cost 이렇게 입력하는 식을 edge[v2][v1] = cost 로 입력한 edge 배열을 이용하여 구할 수 있습니다.

저는 처음부터 인접리스트를 두개 생성하여 구하는 방법으로 하였습니다.

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

시작점이 주어지면 각 정점에 대한 최단 경로를 출력하는 문제입니다.

다익스트라 알고리즘을 사용해서 풀면 됩니다.

처음에는 아무 생각 없이 인접행렬로 만들어서 풀었었는데 메모리 초과가 나왔습니다.

정점의 갯수가 최대 2만개여서 인접행렬을 만든다면 최대 2억개의 int 배열을 할당하기 때문에 당연히 메모리가 터집니다.

그래서 인접리스트로 만들었더니 통과하였습니다.

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

상근이가 갖고 있는 숫자가 맞는지 확인하는 문제입니다.

배열 크기는 약 2700만 정도까지 할당이 가능하기 때문에 boolean 배열을 선언해서 해도 됩니다.

하지만 boolean 배열을 쓴다면 BitSet 이라는 자료구조를 사용하면 더 좋습니다.

일반적으로 boolean 배열은 값마다 1Byte씩 차지하는데 BitSet은 1bit만 차지합니다.

무려 7bit를 아끼는 효과가 있죠.

값을 넣을 때 주의할 점은 BitSet 역시 인덱스를 사용하기 때문에 음수 인덱스를 참조하면 에러가 발생합니다.

인덱스가 0부터 시작할 수 있도록 10,000,000 을 더해줍시다!

그리고 입/출력이 많기 때문에 BufferedReader와 BufferedWriter를 사용해주는 것이 좋습니다.

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

자두가 먹을 수 있는 자두의 최대 갯수를 구하는 문제입니다.

[현재 시간][자두가 이동한 횟수] 를 배열로 한 DP로 해결을 할 수 있습니다.

위치에 대한 인덱스를 만들지 않은 이유는 자두가 이동한 횟수로 현재 위치를 알 수 있기 때문입니다.

자두는 무조건 나무 1에서 시작합니다.

자두가 0, 2, 4, ... 처럼 짝수번 움직이면 자두의 현재 위치는 나무 1입니다.

만약 자두가 1, 3, 5 .. 처럼 홀수번 움직인다면 자두의 현재 위치는 나무 2입니다.

그렇기 때문에 dp[i][j] 는 나무 1일때와 2일때 서로 겹치는 일이 없습니다.

한가지 주의할 점은 현재 시간이 1일때는 항상 나무 1에 떨어지는 경우만 카운트해야 한다는 점입니다.

그 외에는 자두가 가만히 있는 경우 dp[i-1][j] 와 움직인 경우 dp[i-1][j-1] 로 나누어 처리를 해주면 됩니다.

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

백준 2470번 두 용액 문제의 업그레이드 버전입니다.

두 용액을 O(n) 시간에 구했었습니다.

세 용액은 배열의 숫자 하나를 지정해서 (두 용액 + 지정된 용액) 의 합이 0에 가장 가까운지 판단하면 됩니다.

따라서 배열을 순회하면서 두 용액 구하는 과정을 N번 반복하면 되기 때문에 O(N^2) 시간에 구할 수 있습니다.

한 가지 주의할 점은 두 용액 문제에서는 용액의 합으로 나올 수 있는 최대값이 2,000,000,000 이었기 때문에 int 형으로도 풀렸지만

세 용액 문제에서는 3,000,000,000 이상이 될 수 있기 때문에 long 타입으로 풀어줘야 합니다.

문제 링크 : 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인 부분만 세주면 됩니다.

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