연속 부분 수열의 최대합(한국어로 맞는지 모르겠습니다)을 구하는 정말 유명한 DP 문제입니다.
문제를 볼 때마다 매번 10초 정도 LCS와 헷갈립니다. 완전히 다른 알고리즘이라 금방 깨닫긴 하지만, 아마 입력의 형태가 비슷해서 그런것 같습니다.
저만 그럴수도 있구요.
아이디어는 이렇습니다. 배열 nums가 주어졌다고 할때,
어떤 위치 i 에서 끝나는 부분수열의 최대합은 두가지 경우입니다.
i-1에서 끝나는 부분수열의 최대합이 양수라서 그 값을 더하거나, 버리고 자기 자신만 취하거나
배열을 만들어서 각 위치마다 해당 위치에서 끝나는 최대합을 기록하며 풀이해도 되는데 이번 문제에선 중간 내용을 활용하지 않기 때문에 그냥 변수에 바로 저장해서 풀이했습니다.
if-else구문을 max(i, sum+i)로 줄이면 코드라인은 줄어들지만 실행시간이 조금 느려집니다.
조건문을 (0 > sum)으로 작성해도 같은 코드입니다.
class Solution:
def maxSubArray(self, nums: list) -> int:
sum = -100_000
maxSum = -100_000
for i in nums:
if(i > i + sum):
sum = i
else:
sum += i
maxSum = max(sum, maxSum)
return maxSum
input = [[-2,1,-3,4,-1,2,1,-5,4],[1],[5,4,-1,7,8]]
for i in input:
print(Solution().maxSubArray(i))
class Solution:
def jump(self, nums: list) -> int:
dp = [20000]*len(nums)
dp[0] = 0
for i in range(0, len(nums)-1):
for j in range(i+1, min(len(nums), i + nums[i] + 1)):
dp[j] = min(dp[i]+1, dp[j])
return dp[-1]
input = [[2,3,1,1,4],[2,3,0,1,4]]
for i in input:
print(Solution().jump(i))
토론 창의 도움을 얻어 BFS와 유사한, 매 step마다 내가 갈수있는 최대의 범위를 갱신하는 코드를 작성했습니다.
class Solution:
def jump(self, nums: list) -> int:
step = 0
position = 0
canMove = 0
while(position < len(nums)-1):
step += 1
maxMove = 0
while(position <= canMove):
maxMove = max(maxMove, position+nums[position])
position += 1
if(maxMove >= len(nums)-1):
return step
canMove = maxMove
return step
input = [[0],[2,3,1,1,4],[2,3,0,1,4]]
for i in input:
print(Solution().jump(i))
각 섬들을 다리로 연결하는 부분은 같지만, 다리만들기1 문제와 다르게 다리는 직선으로만 가능하며 모든 섬이 연결되도록 완성해야 하고 이때 다리의 길이가 2이상인 최소한의 다리를 활용해야 합니다.
이 문제는 크게 3가지 과정으로 나눌 수 있습니다.
1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기
2. 각각의 섬에서 다른 섬으로 잇는 최단 다리를 모두 만들기
3. 다리를 선택해 모든 섬들이 연결되게 만들기.
1,2번 과정은 다리만들기 1번 문제와 비슷하고 3번 과정은 MST(최소 스패닝 트리)를 구하는 과정으로 만들 수 있습니다.
즉, 각각의 섬들이 노드가 되고 각 섬들에서 다른섬으로 연결되는 최소거리의 다리가 엣지가 되는 식입니다.
MST를 만드는 알고리즘은 여러 종류가 있는데 우선순위 큐와 Union만을 이용해 간단하게 구현할 수 있는 크루스칼(Kruskal) 알고리즘을 사용했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class q17472__BOJ_다리만들기2 {
static StringTokenizer st;
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static int[] parent;
static int N, M;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
for (int m = 0; m < M; m++) {
map[n][m] = Integer.parseInt(st.nextToken()) * -1;
}
}
int island = 1;
Queue<int[]> queue = new LinkedList<>();
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (map[n][m] == -1) {
queue.offer(new int[] { n, m });
map[n][m] = island;
while (!queue.isEmpty()) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && map[nX][nY] == -1) {
queue.offer(new int[] { nX, nY });
map[nX][nY] = island;
}
}
}
island++;
}
}
}
int[][] graph = new int[island][island];
for (int is = 1; is <= island; is++) {
boolean[][] visit = new boolean[N][M];
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (map[n][m] == is) {
queue.offer(new int[] { n, m, 0, 5 });
visit[n][m] = true;
}
}
}
while (!queue.isEmpty()) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
int l = now[2];
int dir = now[3];
if (dir == 5) {
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 0) {
queue.offer(new int[] { nX, nY, l + 1, i });
visit[nX][nY] = true;
}
}
}
else {
int nX = x + delta[dir][0];
int nY = y + delta[dir][1];
if (isIn(nX, nY) && !visit[nX][nY]) {
if (map[nX][nY] == 0) {
queue.offer(new int[] { nX, nY, l + 1, dir });
visit[nX][nY] = true;
} else {
if (graph[is][map[nX][nY]] == 0 && 1 < l) {
graph[is][map[nX][nY]] = l;
}
visit[nX][nY] = true;
}
}
}
}
}
int answer = 0;
parent = new int[island];
for (int n = 1; n < island; n++) {
parent[n] = n;
}
PriorityQueue<int[]> pqueue = new PriorityQueue<>((e1, e2) -> {
return e1[0] - e2[0];
});
for (int from = 1; from < island; from++) {
for (int to = 1; to < island; to++) {
if (graph[from][to] != 0) {
pqueue.offer(new int[] { graph[from][to], from, to });
}
}
}
while (!pqueue.isEmpty()) {
int[] now = pqueue.poll();
int l = now[0];
int from = now[1];
int to = now[2];
if (find(from) != find(to)) {
answer += l;
union(from, to);
}
}
boolean flag = false;
int parent = find(1);
for (int n = 1; n < island; n++) {
if (find(n) != parent) {
flag = true;
break;
}
}
if (flag) {
System.out.println(-1);
} else {
System.out.println(answer);
}
}
static boolean isIn(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < M) {
return true;
}
return false;
}
static int find(int i) {
if (i == parent[i])
return i;
return parent[i] = find(parent[i]);
}
static void union(int x, int y) {
x = find(x);
y = find(y);
if (x > y)
parent[x] = y;
else
parent[y] = x;
}
}
시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class q2146_BOJ_다리만들기 {
static StringTokenizer st;
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static int[][] map;
static int[] parent;
static int N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
for (int m = 0; m < N; m++) {
map[n][m] = Integer.parseInt(st.nextToken()) * -1;
}
}
int island = 1;
for (int n = 0; n < N; n++) {
for (int m = 0; m < N; m++) {
if (map[n][m] == -1) {
dfs(n, m, island);
island++;
}
}
}
int answer = Integer.MAX_VALUE;
Queue<int[]> queue = new LinkedList<>();
for (int is = 1; is <= island; is++) {
boolean[][] visit = new boolean[N][N];
for (int n = 0; n < N; n++) {
for (int m = 0; m < N; m++) {
if (map[n][m] == is) {
queue.offer(new int[] { n, m });
visit[n][m] = true;
}
}
}
int l = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int s = 0; s < size; s++) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && !visit[nX][nY]) {
if (map[nX][nY] == 0) {
queue.offer(new int[] { nX, nY });
visit[nX][nY] = true;
} else {
answer = Math.min(answer, l);
visit[nX][nY] = true;
}
}
}
}
l++;
if (l > answer) {
queue.clear();
}
}
}
System.out.println(answer);
}
static void dfs(int x, int y, int name) {
map[x][y] = name;
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && map[nX][nY] == -1) {
dfs(nX, nY, name);
}
}
}
static boolean isIn(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < N) {
return true;
}
return false;
}
}
문제의 설명만 보면 숨겨진 의도를 바로 찾기 힘들지만 생각해 보면 숫자를 연달아 선택할 수 없다는건 이전의 House Robber문제와 같은 유형이란것을 알 수 있습니다.
또 어떤 숫자를 선택하면 그 숫자에 걸린 point는 모두 획득 할 수 있기 때문에 숫자의 범위와 같은 크기의 List로 값을 압축 해 쉽게 구현 할 수 있습니다.
class Solution:
def deleteAndEarn(self, nums: list) -> int:
expectValue = [0] * 10001
for i in nums:
expectValue[i] += i
dp = [0] * 10001
dp[1] = expectValue[1]
for i in range(2,10001):
dp[i] = max(dp[i-1], dp[i-2]+expectValue[i])
return dp[-1]
input = [[3,4,2], [2,2,3,3,3,4]]
for i in input:
print(Solution().deleteAndEarn(i))
