R×C 격자 위에 여러 마리의 상어가 있다. 상어는 각각 속도(s), 방향(d), 크기(z)를 가지고 있으며, 낚시왕은 1열부터 오른쪽으로 한 칸씩 이동하면서 가장 가까운 상어를 낚고, 이후 모든 상어가 동시에 이동한다. 같은 칸에 여러 상어가 도착하면 가장 큰 상어만 살아남는다.
1차 시도 (오답)
import java.io.*;
import java.util.*;
public class Main {
// 상하우좌
static int[] dr = {0, -1, 1, 0, 0};
static int[] dc = {0, 0, 0, 1, -1};
static class Shark {
int r, c, s, d, z;
boolean isAlive;
public Shark(int r, int c, int s, int d, int z) {
super();
this.r = r;
this.c = c;
this.s = s;
this.d = d;
this.z = z;
this.isAlive = true;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[R+1][C+1];
Shark[] sharks = new Shark[M+1];
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken()); // 속도
int d = Integer.parseInt(st.nextToken()); // 방향
int z = Integer.parseInt(st.nextToken()); // 크기
sharks[i] = new Shark(r, c, s, d, z);
map[r][c] = i;
}
int ans = 0;
for (int c=1; c<=C; c++) {
// 낚시
for (int r=1; r<=R; r++) {
if (map[r][c] > 0) {
ans += sharks[map[r][c]].z;
sharks[map[r][c]].isAlive = false;
map[r][c] = 0;
break;
}
}
// 상어 이동
for (int i=1; i<=M; i++) {
Shark s = sharks[i];
if (!s.isAlive) continue;
// 이동 위치 계산
int nr = s.r + dr[s.d]*s.s;
int nc = s.c + dc[s.d]*s.s;
while (nr<1 || nr >R || nc<1 || nc>C) {
if (nr<1) {
nr = 1+(1-nr);
s.d = 2;
}
else if (nr>R) {
nr = R-(nr-R);
s.d = 1;
}
else if (nc<1) {
nc = 1+(1-nc);
s.d = 3;
}
else if (nc>C) {
nc = C-(nc-C);
s.d = 4;
}
}
// 겹치는지 확인
if (map[nr][nc] == 0) {
if (map[s.r][s.c] == i) map[s.r][s.c] = 0;
s.r = nr;
s.c = nc;
map[nr][nc] = i;
} else {
// 이미 이동 마친 상어면 진짜 있는거니까 크기 비교
if (map[nr][nc] < i) {
int winner = 0;
int loser = 0;
if (s.z > sharks[map[nr][nc]].z) {
winner = i;
loser = map[nr][nc];
} else {
winner = map[nr][nc];
loser = i;
}
// 사망 처리
sharks[loser].isAlive = false;
// 승자 이동 처리
if (map[sharks[winner].r][sharks[winner].c] == winner) map[s.r][s.c] = 0;
sharks[winner].r = nr;
sharks[winner].c = nc;
map[nr][nc] = winner;
}
// 아니면 그냥 이동해버리기
else {
if (map[s.r][s.c] == i) map[s.r][s.c] = 0;
s.r = nr;
s.c = nc;
map[nr][nc] = i;
}
}
}
}
System.out.println(ans);
}
}
로직
초기화
상어마다 위치와 속도·방향·크기를 입력받아 Shark 객체로 관리하고, map 배열에는 그 상어의 번호를 기록했다.
map[r][c] = i → “i번 상어가 (r, c)에 있다”는 의미.
낚시 단계
낚시꾼이 오른쪽으로 한 칸 이동할 때마다, 해당 열의 가장 위쪽 상어를 잡고 map[r][c] = 0으로 비워준다.
잡힌 상어는 isAlive = false로 표시하고, 크기를 점수에 더한다.
상어 이동 단계
for문으로 모든 상어를 순회하며 map배열 기준으로 이동 처리
만약 이동한 칸에 다른 상어가 이미 있으면, 이동 처리한 상어면 그 자리에서 즉시 크기 비교해 큰 상어만 남겼다.
이동 처리하지 않은 상어면 그냥 무시하고 이동시켰다
문제는 이동 단계에서 발생했다.
이동 중인 상어가 이미 map을 갱신한 상어의 흔적을 보고 움직이게 된다.
즉,모든 상어가 동시에 이동해야 하는데, 실제로는이전 상어의 이동 결과를 보면서 순차 이동하게 되는 구조다. 따라서 같은 입력이라도 “이동 순서”에 따라 결과가 달라질 수 있고, 문제의 요구사항인 **‘동시 이동 후 충돌 판정’**이 깨져버린다.
처음에는 단순하게 map 하나로 모든 단계를 처리하려 했다. map에 상어 번호를 저장해두고, 낚시 → 이동 → 충돌 처리를 모두 같은 배열에서 진행했다. 이 방식의 장점은 구현이 직관적이라는 점이었지만, 곧 “동시 이동”이라는 조건에서 큰 문제가 생겼다.
낚시 시점에서 map[r][c] = 0을 먼저 해서 NPE 발생
상어가 “동시에” 이동하지 않고 순차적으로 map을 덮어씀
결과적으로 같은 칸에 도착한 상어의 크기 비교가 불완전함
2차 시도 (성공)
1차에서 가장 큰 문제였던 “동시 이동 처리”를 해결하기 위해 새로운 맵(newMap)을 만들어 이동 결과를 저장하도록 수정했다.
이후 이동이 모두 끝나면 map = newMap으로 갱신하도록 했다.
for (int c = 1; c <= C; c++)
// 동시 이동 처리를 위한 map 생성
int[][] newMap = new int[R + 1][C + 1];
// 상어 이동
for (int i = 1; i <= M; i++) {
Shark s = sharks[i];
if (!s.isAlive)
continue;
// 이동 위치 계산
int nr = s.r + dr[s.d] * s.s;
int nc = s.c + dc[s.d] * s.s;
while (nr < 1 || nr > R || nc < 1 || nc > C) {
if (nr < 1) {
nr = 1 + (1 - nr);
s.d = 2;
} else if (nr > R) {
nr = R - (nr - R);
s.d = 1;
} else if (nc < 1) {
nc = 1 + (1 - nc);
s.d = 3;
} else if (nc > C) {
nc = C - (nc - C);
s.d = 4;
}
}
// 겹치는지 확인
if (newMap[nr][nc] == 0) {
newMap[nr][nc] = i;
s.r = nr;
s.c = nc;
} else {
int j = newMap[nr][nc];
if (sharks[j].z > s.z) {
s.isAlive = false;
} else {
newMap[nr][nc] = i;
sharks[j].isAlive = false;
s.r = nr;
s.c = nc;
}
}
// map 갱신
map = newMap;
}
}
하지만 여전히 아쉬운 점이 있었다.
이동 처리 시, 상어의 속도가 매우 크면, 벽에 부딪히며 상하 or 좌우로 지나치게 많이 왔다갔다하게 된다.
예를 들어 R=5, s=100이면 1행에 있던 상어가 5행까지 가서 방향 전환, 다시 1행까지 가서 방향 전환, ... 을 수십번 반복해야 한다.
이를 개선하기 위해 규칙을 찾아야 했다.
3차 시도 (개선)
결국 규칙을 찾아 속도 s를 축약했다. 간략히 설명하자면,
C가 4인 상어의 좌우 이동 과정을 쭉 한 줄로 나열했을 때
1
2
3
4
3
2
1
2
3
4
3
2
1
6
5 <-
4 <-
3 <-
2 <-
1 <-
현재 위치
-> 1
-> 2
-> 3
-> 4
-> 5
6
이다. 이 때, 상어가 2의 위치에서 오른쪽이든 왼쪽이든 다시 제자리로 돌아오려면 몇칸을 이동해야 할까?
=> 6칸이다!
즉 아래와 같이 축약할 수 있다.
세로 이동이면 s %= 2*(R-1)
가로 이동이면 s %= 2*(C-1)
이렇게 하면 이동 시 실제 필요한 거리만 계산하므로 시간 복잡도를 줄일 수 있다.
입력 시 속도를 축약해 저장해버렸다.
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken()); // 속도
int d = Integer.parseInt(st.nextToken()); // 방향
int z = Integer.parseInt(st.nextToken()); // 크기
// 속도 축약!
if (d==1 || d==2) {
s %= 2*(R-1);
} else {
s %= 2*(C-1);
}
sharks[i] = new Shark(r, c, s, d, z);
map[r][c] = i;
}
결과
결과적으로 2차 시도 대비 3차 시도에서 수행시간을 16% 단축했다!
회고
이 문제는 단순 구현처럼 보여도 “동시 이동 처리”와 “속도 축약”이라는 두 가지 포인트가 있었다.
중위 표기식(예: A+B*C)을 후위 표기식(예: ABC*+)으로 바꾸는 문제다. 연산자의 우선순위와 괄호 구조를 고려해 후위표기식으로 만들어야 한다.
처음 접근 방식
처음엔 “연산자 스택”과 “괄호 처리를 위한 임시 스택” 두 개를 만들어서 닫는 괄호가 나올 때마다 여는 괄호가 나올 때까지 임시 저장 후 한꺼번에 출력하는 방식으로 접근했다.
- 연산자 스택: +, -, *, / 저장 - 임시 스택: 괄호 내부의 피연산자와 연산자 임시 보관 - 여는 괄호 개수를 세기 위해 cnt 사용
이 방식으로 구현했을 때, 괄호 내부를 처리할 때는 정상적으로 작동했지만 괄호 밖의 우선순위 계산(예: A+B*C)에서 엉뚱한 답이 나왔다. 즉, 연산자 우선순위를 코드 내에서 직접 비교하지 않으면 단순히 괄호 단위로만 구분되는 구조였다.
개선 ver.
문제를 다시 살펴보면, 사실 이 문제는 “연산자 우선순위”만 잘 처리하면 괄호 두 개가 필요 없다.
핵심 규칙은 아래와 같다.
1. 피연산자는 바로 출력 2. 여는 괄호(`(`):는 바로 스택에 push 3. 닫는 괄호(`)`)는 여는 괄호가 나올 때까지 스택에서 pop → 출력 4. 연산자(+,-,*,/): 이게 중요하다. - 스택의 맨 위 값이 우선순위가 자기보다 높거나 같으면 pop → 출력 - 자기 자신을 스택에 push
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 연산자를 담을 스택
Stack<Character> st = new Stack<>();
// 괄호 처리를 위한 임시 스택
StringBuilder ans = new StringBuilder();
char[] inputs = br.readLine().toCharArray();
for (char c : inputs) {
// 연산자일 때
// 후순위 연산자면 여는괄호 나올때까지 모두 pop
if (c == '+' || c == '-') {
while (!st.isEmpty() && st.peek() != '(') {
ans.append(st.pop());
}
st.push(c);
}
// 우선순위 연산자도 동일 우선순위일 경우 모두 pop
else if (c == '*' || c == '/') {
while (!st.isEmpty() && (st.peek() == '*' || st.peek() == '/')) {
ans.append(st.pop());
}
st.push(c);
} else if (c == '(') {
st.push(c);
}
// 닫는 괄호일 때
else if (c == ')') {
// 여는 괄호가 나올 때까지 pop
while (st.peek() != '(') {
ans.append(st.pop());
}
// 여는 괄호 제거
st.pop();
}
// 피연산자일 땐 바로 ans 저장
else {
ans.append(c);
}
}
// 남은것 비우기
while (!st.isEmpty()) {
ans.append(st.pop());
}
System.out.println(ans);
}
}
개선 과정
1. 스택 2개 → 1개 처음엔 답을 출력할 때 편리함을 위해 피연산자, 연산자를 각각 담아 관리하려 했다. 피연산자는 아예 스택에 담을 필요 없이 바로 출력하면 되는 문제였다.
2. pop 조건 처음엔 우선순위보다 높을 때만 고려해 pop했다. 하지만 A/B*C 와 같은 상황에서 AB/C* 가 나와야 하는데 ABC*/ 로 곱하기를 먼저 해버리는 상황이 발생한다. 우선순위가 같아도 앞에 있는 연산자가 우선순위를 가지므로, 같은 경우도 고려해야 한다.
회고
- 괄호 처리에 집중하다 보니 연산자 우선순위 처리를 생각하지 못해 시간이 많이 지체됐다. - 후위표기 방식 자체에 대해 친숙하지 못해 더 오래 걸렸던 것 같다. - 처음의 방식은 복잡하지만, 이런 시행착오 덕분에 후위표기식에 대한 알고리즘을 확실히 이해했다.
N개의 지점과 M개의 도로, W개의 웜홀이 있다. 도로는 양방향, 웜홀은 단방향이며, 웜홀을 지나면 시간이 거꾸로 흐른다. 즉, 웜홀의 가중치는 음수로 표현된다.
이때, 그래프 어딘가에 “시간이 줄어드는 순환 경로(음수 사이클)” 가 존재한다면 “YES”를, 그렇지 않다면 “NO”를 출력해야 한다.
처음 접근: BFS 탐색
문제에서 “시간을 되돌리는 웜홀”이라는 문장을 보고 처음엔 단순하게 생각했다.
“모든 지점을 BFS로 돌면서, 시간이 줄어드는 루프가 생기는지 찾아보면 되지 않을까?”
그래서 처음 시도는 이렇게 했다:
도로와 웜홀을 각각 리스트로 분리해서 관리 (List<Node> roads, List<Node> wormholes)
각 지점을 시작점으로 BFS 탐색
시간이 더 짧아지는 경로(times[e] > times[s] + w)를 만나면 음수 사이클이라고 판단
하지만 문제가 생겼다. BFS는 가중치가 일정하거나 양수일 때만 정상적으로 작동한다. 음수 가중치가 있으면 “방문했어도 다시 돌아가야 하는 경우”가 생기는데, BFS는 이런 갱신을 반영할 수 없다.
그래서 시간이 과거로 가는 경우 방문했어도 다시 돌아가게끔 하는 방식을 생각했지만,
사이클이 발생했을 때는 무한대로 시간이 과거로 가기 때문에 대응할 수 없었다.
새로운 알고리즘: 벨만포드(Bellman-Ford) 알고리즘
이 문제의 핵심은 음수 사이클을 찾는 것이었다.
문제를 다시 읽어보면, 결국 출발점에 다시 되돌아왔을 때 시간이 더 과거이면 되는 것이었고,
결국 무조건 사이클이 발생하는 조건이어야 했다. 그것도 음의 사이클로만 발생해야 하는 것이다. 그 역할을 정확히 수행하는 알고리즘이 바로 벨만포드 알고리즘이다.
간략한 구조
다익스트라처럼, dist 배열을 만들어 출발점만 0, 나머진 무한대로 초기화 (단, 이 문제는 사이클만을 찾아야 하기에 모든 dist를 0으로 만들어야 한다.)
모든 간선을 순회하며 (dist[시작점]이 무한대가 아니면서, dist[시작점] + 가중치 < dist[도착점]) 을 충족하면 값을 갱신하는 행위를 V−1번 반복
사이클을 찾기 위해, 모든 간선 순회를 1번 더 반복한다. 이 때 dist에 갱신이 일어난다면, 음수 사이클이 존재한다는 뜻이다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static class Edge {
int s;
int e;
int w;
public Edge(int s, int e, int w) {
super();
this.s = s;
this.e = e;
this.w = w;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
Edge[] edges = new Edge[M * 2 + W];
List<Edge>[] adjList = new List[N + 1];
int idx = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[idx++] = new Edge(s, e, w);
edges[idx++] = new Edge(e, s, w);
}
for (int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[idx++] = new Edge(s, e, -w);
}
// 벨만-포드 알고리즘
System.out.println(bellmanFord(edges, N) ? "YES" : "NO");
}
}
private static boolean bellmanFord(Edge[] edges, int N) {
int[] dist = new int[N + 1];
Arrays.fill(dist, 0);
// 모든 간선을 순회 => N-1번 반복
// Why? 한 지점에서 다른 지점으로 갈 때 최소 거리는 사이클이 있지 않은 한, 최대 N-1개의 간선을 쓰기 때문
for (int i = 0; i < N - 1; i++) {
boolean updated = false;
for (Edge e : edges) {
if (dist[e.s] + e.w < dist[e.e]) {
dist[e.e] = dist[e.s] + e.w;
updated = true;
}
}
if (!updated)
break;
}
for (Edge e : edges) {
if (dist[e.s] + e.w < dist[e.e]) {
return true;
}
}
return false;
}
}
개선 과정
1. 처음엔 모든 정점에서 벨만포드를 실행했다.
각 정점마다 bellmanFord(i) 호출
논리적으로는 맞지만, 시간복잡도 O(V²E) → 시간초과
2. dist 값을 모두 0으로 변경
최단거리를 구하는 게 목적이 아니라, 음수 사이클을 찾는게 목적이다.
따라서 굳이 출발점을 선택해가며 N번 순회할 필요 없이dist를 0으로 하는게 시간복잡도 상 이득이다.
시간복잡도 O(VE) 로 감소 → 통과
3. 조기 종료 최적화
한 라운드에서 갱신이 한 번도 없으면(updated == false), 모든 최단경로가 확정된 상태이므로 더 돌 필요 없음 → break
배운점
BFS는 가중치가 음수일 땐 쓸 수 없다. 사이클에서 막히거나, 방문 체크에서 막힌다..
새로운 벨만 포드 알고리즘에 대해 알게 됐다.
다익스트라와 유사하지만, 음수 가중치일 때 사용할 수 있고, 사이클을 찾고자 할 때에도 사용할 수 있다!
private static void selectSort(int[] w) {
// 정렬 시작지점
for (int i = 0; i < w.length - 1; i++) {
int minIdx = i;
// 범위 내 최저값 찾기
for (int j = i + 1; j < w.length; j++) {
if (w[minIdx] > w[j]) {
minIdx = j;
}
}
swap(i, minIdx, w);
}
}
삽입 정렬
처리되지 않은 데이터를 하나씩 골라 앞 수와 비교해 바꿔가며 적절한 위치에 삽입
평균 시간복잡도: O(N2)
기존 배열이 거의 정렬되어 있을수록 빠르게 동작 ⇒ 최선의 경우 O(N)
private static void insertSort(int[] w) {
// 정렬 대상 구간 => 첫 인덱스는 정렬된 것으로 보고 인덱스 1부터 시작
for (int i = 1; i < w.length - 1; i++) {
// 정렬 대상 원소를 정렬된 구간의 수와 비교하며 삽입
for (int j = i + 1; j > 0; j--) {
// 나보다 작은 원소를 만날 때까지 스왑
if (w[j] < w[j - 1]) {
swap(j, j - 1, w);
} else
break;
}
}
}
버블정렬
인접한 두 원소를 검사하며 정렬하는 알고리즘
1회전 시 가장 마지막 인덱스에 가장 큰 수가 배치되고, 회전을 거듭할수록 뒤쪽부터 정렬되는 방식
평균 시간복잡도:O(N2)
장점
구현이 매우 간단하다.
단점
위치 교환 과정이 많아 비효율
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
private static void bubbleSort(int[] w) {
// 뒤쪽부터 정렬됨 -> 정렬 완료된 부분 직전까지만 정렬하도록 제한
for (int i = w.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (w[j] > w[j + 1]) {
swap(j, j + 1, w);
}
}
}
}
퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 자근데이터의 위치를 바꾸는 방법
병합정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
기본 방식은 첫 데이터를 기준데이터(Pivot)로 설정함
O(N logN)
최악의 경우 O(N2) → 이미 정렬된 경우
private static void quickSort(int[] w, int start, int end) {
if (start >= end) {
return;
}
int pivot = w[start];
int l = start + 1;
int r = end;
while (l <= r) {
// 왼쪽부터 나보다 큰거 찾기
while (l <= end && w[l] <= pivot) {
l += 1;
}
// 오른쪽부터 나보다 작은거 찾기
while (r > start && w[r] >= pivot) {
r -= 1;
}
// l, r 교차하는 순간 피봇과 작은수 위치 스왑
if (l > r) {
swap(start, r, w);
// 교차하지 않으면 l, r만 스왑
} else
swap(l, r, w);
}
quickSort(w, start, r - 1);
quickSort(w, r + 1, end);
}
병합정렬
단점
임시 배열이 필요하다.
제자리 정렬이 아니다.
배열 크기가 큰 경우에는 이동 횟수가 많으므로 비효율 발생한다.
장점
최선과 최악 모두 시간복잡도 O(NlogN)으로, 안정적인 정렬 방법
만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
제자리 정렬(in-place sorting)로 구현할 수 있다.
따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.
private static void mergeSort(int[] w, int start, int end) {
if (start >= end)
return;
int mid = (start + end) / 2;
mergeSort(w, start, mid);
mergeSort(w, mid + 1, end);
merge(w, start, mid, end);
}
private static void merge(int[] w, int start, int mid, int end) {
int[] tmp = new int[end - start + 1];
int l = start;
int r = mid + 1;
int tIdx = 0;
while (l <= mid && r <= end) {
if (w[l] <= w[r]) {
tmp[tIdx++] = w[l++];
} else {
tmp[tIdx++] = w[r++];
}
}
while (l <= mid) {
tmp[tIdx++] = w[l++];
}
while (r <= end) {
tmp[tIdx++] = w[r++];
}
for (int i = 0; i < tmp.length; i++) {
w[start + i] = tmp[i];
}
}
/*
* 숫자가 주어질 때마다 위치 찾아 삽입.
* 삽입 위치 찾는건 이분탐색으로.
* 중간값은 짝수->len/2-1 홀수->len/2
*/
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static int N;
static List<Integer> list;
public static void main(String[] args) throws IOException {
init();
for (int i=0; i<N; i++) {
int newNum = Integer.parseInt(br.readLine());
int targetIdx = binarySearch(0, list.size()-1, newNum);
list.add(targetIdx, newNum);
int midIdx = list.size()/2;
if (list.size()%2 == 0) midIdx -= 1;
sb.append(list.get(midIdx)).append('\n');
}
System.out.println(sb);
}
private static int binarySearch(int s, int e, int target) {
int mid = (s+e)/2;
if (s > e) {
return s;
}
int midNum = list.get(mid);
if (midNum == target) {
return mid;
} else if(midNum < target) {
return binarySearch(mid+1, e, target);
} else {
return binarySearch(s, mid-1, target);
}
}
private static void init() throws IOException {
sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
}
}
결론적으로 정답은 맞았으나, 실행속도가 아쉬웠다.
개선 사항
원인
기존 내 코드의 실행속도가 느렸던 원인을 생각해볼 때,
ArrayList를 사용해 삽입하는 방식이 주요 원인이라고 생각했다.
✨ Javadoc (ArrayList의 add 메서드에 대한 내용 발췌)
위 javadoc 내용을 보면 어레이리스트도 결국 배열이기 때문에,
삽입을 하려면 결국 배열처럼 해당 인덱스를 비우기 위해 이후 숫자를 모두 하나씩 미루고,
비워진 자리에 삽입하는 로직이기 때문에 배열 전체를 순회해야 한다.
사실상 시간 복잡도는 O(N2) 인 셈인 것이다.
그래서 대안으로 힙정렬을 생각했다.
PriorityQueue의 정렬방식이기도 한 힙정렬은 시간복잡도가 O(NlogN)으로 더 효율적이다.
개선 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static int N;
static PriorityQueue<Integer> maxHeap; // 최대힙 (작은 수들의 절반)
static PriorityQueue<Integer> minHeap; // 최소힙 (큰 수들의 절반)
public static void main(String[] args) throws IOException {
init();
for (int i = 0; i < N; i++) {
int x = Integer.parseInt(br.readLine());
insert(x);
sb.append(maxHeap.peek()).append('\n'); // 항상 아래 중앙값 출력
}
System.out.print(sb);
}
private static void init() throws IOException {
sb = new StringBuilder();
N = Integer.parseInt(br.readLine().trim());
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
private static void insert(int n) {
// maxheap을 우선으로 담기
if (maxHeap.isEmpty() || n <= maxHeap.peek()) maxHeap.offer(n);
else minHeap.offer(n);
if (maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.poll());
if (maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
int a = maxHeap.poll(), b = minHeap.poll();
maxHeap.offer(b);
minHeap.offer(a);
}
}
}
개선 후 (30% 속도 향상)
배운점
기존에는 매 입력마다 정렬된 리스트에 이분 탐색으로 삽입했는데, 삽입 과정에서 배열의 뒤 원소들을 한 칸씩 밀어야 해서 O(N) 시간이 소요되었다. 따라서 입력이 많아질수록 전체 시간 복잡도가 O(N^2)까지 치솟아 성능상 한계가 있었다.
이를 힙(PriorityQueue) 두 개로 관리하는 방식으로 바꾸면서, 각 입력마다 삽입·삭제 연산을 O(log N)에 처리할 수 있었고, 전체 시간 복잡도는 O(N log N)으로 크게 개선되었다.
다만, 다른 사람들의 200ms대 풀이를 보니 똑같이 힙을 활용하더라도 PriorityQueue 대신 배열 기반으로 직접 힙 연산을 구현해 오버헤드를 줄인 경우가 있었다. 이를 통해 단순히 자료구조를 교체하는 것만으로는 충분하지 않고, 문제 상황에 맞는 세밀한 최적화와 구현 방식의 차이가 성능을 크게 좌우한다는 점을 배울 수 있었다.
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
내 정답 코드
내가 생각한 로직은,
1. 지도에서 현황을 관리할 map 배열(int[][] map), 빠르게 물고기 위치에 접근하기 위한 fishes배열(ArrayList<int[]>[] fishes), 상어의 위치, 크기, 먹은 물고기 수를 관리하기 위한 shark 배열(int[] shark)을 선언하여 관리한다.
그리고 엄마 상어를 찾기 전까지 아래 작업을 반복한다.
1. 가장 가까운 타겟 선택
- fishes 배열을 순회하며, 나보다 크기가 작은 물고기들과의 거리를 각각 bfs 작업으로 탐색한다.
- 가장 가까우면서, 좌측 상단에 있는 물고기를 타겟으로 선정한다.
2. 선택된 타겟이 없으면 반복 종료
3. 해당 타겟으로 이동하여 잡아먹기
- map에서 상어 위치 이동
- shark배열 좌표값, 먹은 물고기 수, 크기 값 조정
- fishes리스트에서 해당 물고기 제거
4. 이동하는 데 필요한 시간만큼 소요시간에 가산
public class Main {
static StringBuilder sb;
static int N;
// 0: r, 1: c, 2: 크기, 3: 먹은 물고기 수
static int[] shark = new int[4];
// 0: r, 1: c, 2: 크기, 3: 물고기 리스트 index
static int[] target = new int[4];
static int[][] map;
static boolean[][] visited;
static ArrayList<int[]>[] fishes;
public static void main(String[] args) throws IOException {
init();
System.out.println(simulation());
}
// 시뮬레이션
private static int simulation() {
int time = 0;
while (true) {
// 가장 가까운 타겟 선택
// => 상어보다 크기 작으면서 가장 가까운 물고기
Arrays.fill(target, 0);
int min = 401;
for (int i = 1; i < shark[2] && i < 7; i++) {
for (int j=0; j<fishes[i].size(); j++) {
int[] fish = fishes[i].get(j);
int timeTaken = bfs(fish[0], fish[1]);
if (timeTaken <= min) {
if (timeTaken == min) {
if (target[0] < fish[0])
continue;
else if (target[0] == fish[0]) {
if (target[1] < fish[1])
continue;
}
}
target[0] = fish[0];
target[1] = fish[1];
target[2] = i;
target[3] = j;
min = timeTaken;
}
}
}
// 타겟이 없으면 종료
if (target[2] <= 0) {
return time;
}
// 타겟 있으면 해당 위치 이동 후 시간 가산
// 물고기 먹기
shark[3] += 1;
fishes[target[2]].remove(target[3]);
// 상어 위치 이동
map[shark[0]][shark[1]] = 0;
map[target[0]][target[1]] = 9;
shark[0] = target[0];
shark[1] = target[1];
// 상어 크기 조정
if (shark[3] >= shark[2]) {
shark[2] += 1;
shark[3] = 0;
}
// 시간 가산
time += min;
}
}
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
private static int bfs(int targetR, int targetC) {
visited = new boolean[N][N];
Queue<int[]> q = new ArrayDeque<>();
// 시작지점 큐에 삽입 & 방문체크
q.offer(new int[] { shark[0], shark[1] });
visited[shark[0]][shark[1]] = true;
int size = 1;
int cnt = 0;
while (!q.isEmpty()) {
for (int i = 0; i < size; i++) {
int[] curr = q.poll();
// 목표지점 도착 시 종료
if (curr[0] == targetR && curr[1] == targetC) {
return cnt;
}
// 사방탐색
for (int dir = 0; dir < 4; dir++) {
int nr = curr[0] + dr[dir];
int nc = curr[1] + dc[dir];
// 이미 방문했거나, 범위 밖이거나, 상어보다 크기가 큰 물고기면 패스
if (nr < 0 || nr >= N || nc < 0 || nc >= N)
continue;
if (visited[nr][nc])
continue;
if (map[nr][nc] > shark[2])
continue;
q.offer(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
cnt += 1;
size = q.size();
}
return Integer.MAX_VALUE;
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
// 물고기 크기별 좌표값 저장 배열
fishes = new ArrayList[7];
for (int i = 1; i <= 6; i++) {
fishes[i] = new ArrayList<>();
}
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
int n = Integer.parseInt(st.nextToken());
map[r][c] = n;
if (1 <= n && n <= 6) {
fishes[n].add(new int[] { r, c });
}
if (n == 9) {
shark[0] = r;
shark[1] = c;
shark[2] = 2;
}
}
}
}
}
개선 사항
생각해보니, 모든 물고기를 대상으로 bfs를 돌릴 필요가 없었다.
상어의 현위치를 중심으로, bfs 탐색을 하다가 물고기가 걸리면, 그것을 타겟으로 하면 됐다.
결국 bfs를 1번만 하면 훨씬 시간을 단축할 수 있을 거라 생각했다.
주요 변경
우선순위 큐 사용
노드(Node)를 거리 → 행 → 열 순으로 정렬하도록 구현.
우선순위가 가장 높은(가장 가까운 + 위쪽 + 왼쪽) 물고기부터 바로 선택 가능하다.
탐색 리셋 구조
물고기를 먹은 순간 pq.clear() + visited 배열 재생성하여 shark의 현위치를 기준으로 새로 탐색한다.
상어 위치에서 새롭게 탐색을 시작하므로, 불필요한 경로 계산을 방지한다.
public class Main {
static StringBuilder sb;
static int N;
// shark: [0]=r, [1]=c, [2]=size, [3]=eaten
static int[] shark = new int[4];
static int[][] map;
public static void main(String[] args) throws IOException {
init();
System.out.println(simulation());
}
static class Node implements Comparable<Node> {
int r, c, dist;
Node(int r, int c, int dist) {
this.r = r; this.c = c; this.dist = dist;
}
@Override
public int compareTo(Node n) {
if (this.dist != n.dist) return Integer.compare(this.dist, n.dist);
if (this.r != n.r) return Integer.compare(this.r, n.r);
return Integer.compare(this.c, n.c);
}
}
// 상, 좌, 하, 우 (제시 코드의 dirs와 동일 순서)
static int[] dr = {-1, 0, 1, 0};
static int[] dc = { 0,-1, 0, 1};
// 제시 코드의 playGame() 로직을 네 simulation() 틀에 이식
private static int simulation() {
int time = 0;
// 탐색 시작 상태
PriorityQueue<Node> pq = new PriorityQueue<>();
int[][] visited = new int[N][N];
visited[shark[0]][shark[1]] = 1;
pq.offer(new Node(shark[0], shark[1], 1));
while (!pq.isEmpty()) {
Node cur = pq.poll();
// 먹을 수 있는 물고기를 만났다면 즉시 먹기
if (map[cur.r][cur.c] != 9 && map[cur.r][cur.c] != 0 && map[cur.r][cur.c] < shark[2]) {
time += (cur.dist - 1);
// 상어 위치/맵 갱신
map[shark[0]][shark[1]] = 0;
map[cur.r][cur.c] = 9;
shark[0] = cur.r;
shark[1] = cur.c;
// 먹은 수/크기 갱신
shark[3] += 1;
if (shark[3] == shark[2]) {
shark[3] = 0;
shark[2] += 1;
}
// 탐색 리셋
pq.clear();
visited = new int[N][N];
visited[shark[0]][shark[1]] = 1;
pq.offer(new Node(shark[0], shark[1], 1));
continue; // 다음 먹이 탐색
}
// 사방 확장
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (visited[nr][nc] > 0) continue;
if (map[nr][nc] > shark[2]) continue; // 더 큰 물고기는 통과 불가
visited[nr][nc] = visited[cur.r][cur.c] + 1;
pq.offer(new Node(nr, nc, visited[nr][nc]));
}
}
return time;
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
int n = Integer.parseInt(st.nextToken());
map[r][c] = n;
if (n == 9) {
shark[0] = r;
shark[1] = c;
shark[2] = 2; // 초기 크기
}
}
}
}
}
개선 전
개선 후 (약 5배 이상 빨라짐!)
배운점
기존에는 물고기마다 BFS를 수행해 한 번 이동할 때마다 많은 탐색이 필요했지만, 이를 BFS 한 번으로 줄여 시간 복잡도를 크게 개선할 수 있었다.
하지만 BFS 한 번으로 고쳐도 처음에는 PriorityQueue를 무작정 사용해 큐에 모든 탐색 결과를 삽입하면서 매번 정렬이 발생해 오히려 시간 초과가 났다.
따라서 PQ에 불필요하게 많은 데이터를 넣지 않고, 최소한으로 삽입되도록 로직을 구성해야 했다. 즉, BFS 레벨 단위로 탐색하고 같은 거리 내에서만 후보를 관리하면서 먹을 수 있는 물고기를 찾자마자 탐색을 종료하는 방식으로 바꿔야 효율적으로 해결할 수 있었다.
해당 노드의 모든 인접 노드에 대해, 현재노드까지의 거리 + 간선 가중치가 더 짧으면 갱신한다.
모든 노드를 방문할 때까지 2~3 과정을 반복한다.
예를 들어 노드 5개, 시작 노드 1일 때의 dist 초기 상태는 다음과 같다.
dist = [0, 2, INF, 1, INF] (1번에서 직접 연결된 값)
1번 방문 → 2번과 4번 거리 갱신
다음으로 거리가 짧은 2번 방문 → 3번 거리 갱신
다음으로 4번 방문 → 5번 거리 갱신
이런 식으로 한 시작점에서의 최단거리를 완성한다.
시간복잡도
플로이드 워셜 : for문을 3번 돌기 때문에, O(N^3) 이다.
다익스트라 : 간선 수가 E라고 할 때, O(E logN)가 된다.
따라서 간선 수가 많을 수록 다익스트라는 불리해지고,
노드 수가 많을수록 플로이드 워셜이 불리해진다.
백준 14938 문제 예시 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static int N, M, R, max;
static final int INF = Integer.MAX_VALUE;
static int[] items;
static int[][] dist;
static int[][] dist_dijkstra;
static ArrayList<Site>[] adjList;
static class Site {
int v;
int l;
public Site(int v, int l) {
super();
this.v = v;
this.l = l;
}
}
public static void main(String[] args) throws IOException {
init();
long start = System.currentTimeMillis();
// 플로이드 워셜
floydWarshall();
// 다익스트라
dijkstra();
// 낙하위치별 최단거리 구하기
max = 0;
for (int i=1; i<=N; i++) {
int sum = items[i];
for (int j=1; j<=N; j++) {
if (i==j) continue;
if (dist_dijkstra[i][j] <= M) {
// if (dist[i][j] <= M) {
sum += items[j];
}
}
max = Math.max(max, sum);
}
System.out.println(max);
long end= System.currentTimeMillis();
System.out.println(end - start);
}
private static void floydWarshall() {
// i에서 j로 가는 모든 경로에서 k를 거쳐갈 때 최단거리
// 양방향 통행 => (i>j) == (j>i) 이므로 중복 계산 줄임
for (int k=1; k<=N; k++) {
for (int i=1; i<=N; i++) {
if (dist[i][k] == INF) continue;
for (int j=i+1; j<=N; j++) {
if (i==j) continue;
if (dist[k][j] == INF) continue;
if (dist[i][j] > dist[i][k]+dist[k][j]) {
dist[i][j] = dist[i][k]+dist[k][j];
dist[j][i] = dist[i][j];
}
}
}
}
}
static void dijkstra() {
dist_dijkstra = new int[N + 1][N + 1];
final int INF = Integer.MAX_VALUE;
for (int s = 1; s <= N; s++) {
Arrays.fill(dist_dijkstra[s], INF);
dist_dijkstra[s][s] = 0;
// (정점, 현재까지의 거리)로 사용
java.util.PriorityQueue<Site> pq = new java.util.PriorityQueue<>((a, b) -> Integer.compare(a.l, b.l));
pq.offer(new Site(s, 0));
while (!pq.isEmpty()) {
Site cur = pq.poll();
int u = cur.v;
int d = cur.l;
// 이미 더 짧은 경로가 있으면 스킵
if (d > dist_dijkstra[s][u]) continue;
// 인접 정점 완화
for (Site nx : adjList[u]) {
int v = nx.v;
int w = nx.l;
// d + w 연산 전 INF 가드 (오버플로 방지용)
if (d != INF && d + w < dist_dijkstra[s][v]) {
dist_dijkstra[s][v] = d + w;
pq.offer(new Site(v, dist_dijkstra[s][v]));
}
}
}
}
}
private static void init() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
items = new int[N+1];
adjList = new ArrayList[N+1];
for (int i=1; i<=N; i++) {
adjList[i] = new ArrayList<>();
}
// 지역별 아이템 수 입력
st= new StringTokenizer(br.readLine());
for (int i=1; i<=N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
// 플로이드 워셜용 배열
dist = new int[N+1][N+1];
for (int i=1; i<=N; i++) {
for (int j=1; j<=N; j++) {
if (i==j) continue;
dist[i][j] = INF;
}
}
// 인접 정보 리스트 입력
for (int i=1; i<=R; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
dist[a][b] = l;
dist[b][a] = l;
adjList[a].add(new Site(b, l));
adjList[b].add(new Site(a, l));
}
}
}
코드가 긴데, 플로이드 워셜과 다익스트라를 모두 구현해놓아서 그렇다.
주석 처리를 통해 시간을 비교할 수 있도록 코드를 작성해봤다.
문제에서는 범위가 N이 100 이내이고, 간선도 100 이내라서, 실행시간의 큰 차이를 보이지 않았다.
위가 다익스트라, 아래가 플로이드 워셜이다.
그래서,
N 범위를 더 크게 해서 테스트케이스를 만들어 실험해봤다!
테스트케이스는 GPT를 활용해 테스트케이스를 만드는 파이썬 코드를 생성하여 적용했다.
속도 비교 실험
1-1. 노드 수 :500개, 간선 수:120000개
1-2. 노드 수: 500개, 간선 수 : 60000개
1-3. 노드 수: 500개, 간선 수: 10000개
=> 간선 수가 줄어들수록 확실히 다익스트라는 빨라진다!!
=> 반면, 플로이드는 약간 느려졌는데, 큰 의미는 없는 수치로 보인다.
2-1. 노드 수: 1000개, 간선 수: 490000개
2-2. 노드 수: 1000개, 간선 수: 245000개
2-3. 노드 수: 1000개, 간선 수:100000개
2-4. 노드 수: 1000개, 간선 수:10000개
=> 플로이드는 O(N^3) 이므로 노드 수 500에 비해 이론상 10배 이상 실행시간이 늘어야 한다. 결과를 보면 얼추 10배 정도 나온 것으로 보인다.
=> 다익스트라는 간선 수에 비례하게 속도가 빨라지는 것으로 보인다. 노드수 500에 비해서는 이론 상 1.1배 실행시간 늘어나야 하는데, 244 -> 621이면 꽤 많이 늘어난 것 같다.
결론!!
모든 노드 간 최단 거리를 구해야 할 때, 노드 수 500까지는 웬만하면 플로이드 워셜이 빠르다.
다익스트라가 더 빨라지는 구간은 노드 수가 1000 이상쯤부터. 다만 간선 수가 매우 적어야 한다. 완전 그래프 N*(N-1)/2 에 비해 현저히 작아야 다익스트라가 유리해진다!!
N개의 정수로 이루어진 수열이 주어졌을 때, 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 최대값을 구하는 문제다.단, 수는 한 개 이상 선택해야 한다.
1차 시도 (실패)
이 문제를 마주했을 때, 가장 먼저 생각난 건 누적합을 활용한 방식이었다.
모든 수열을 순회하면서
sum[앞의값] - sum[뒤의값] 으로 계산할 수 있으니,
누적합 배열을 만들고
각 위치마다 그 전까지의 최소 누적합을 빼면 최대 구간합이 되지 않을까? 라고 생각했다.
나보다 앞선 누적합 중 가장 작은 값을 찾으려면, 누적합 배열을 인덱스와 함께 정렬해서 탐색하면 될 것 같았다.
이렇게 작성한 코드는 다음과 같았다:
for (int i = 0; i < N; i++) {
int max = sum[i];
for (int j = i + 1; j < N; j++) {
int tmp = sum[j] - sum[i];
if (tmp > max) {
max = tmp;
}
}
ans = Math.max(max, ans);
}
이중 반복문을 통해 각 구간합을 계산하고, 최댓값을 갱신하는 구조다.
결과는 시간 초과가 발생했다.
생각해보니 이중 for문 구조는 O(N²) 의 시간복잡도였고,입력값이 최대 100,000이기 때문에 이 방식은 실질적으로 불가능했다.
나는 처음에 "정렬 없이 그냥 순회하면서 빼는 거니까 O(N log N) 아닌가?"라고 착각했지만,실제로는 모든 (i, j) 쌍에 대해 sum[j] - sum[i]를 계산하기 때문에 완전한 이중 순회로 O(N²)이다.정렬을 포함했더라도 O(N log N)이 아닌, 여전히 느린 구조였을 것이다.
2차 시도
결국 다시 인터넷을 뒤져보며 동적 계획법을 활용해야함을 깨달았다.
이 알고리즘은 현재 위치에서
지금까지의 누적 최대값에 현재 수를 더하는 것과
현재 수 하나만 사용하는 것 중에서 더 큰 값을 고른다.
즉, 아래와 같은 점화식이다:
dp[i] = max(arr[i], dp[i-1] + arr[i])
for (int i = 0; i < N; i++) {
int max = sum[i];
for (int j = i + 1; j < N; j++) {
int tmp = sum[j] - sum[i];
if (tmp > max) {
max = tmp;
}
}
ans = Math.max(max, ans);
}
이 코드는 O(N) 으로 매우 빠르며, 메모리도 효율적이다.
회고
처음 시도한 방식처럼, 누적합과 정렬을 이용해 푸는 방식도 사용되긴 한다. 예를 들어 "구간합이 K 이상인 최소 길이 구간" 같은 문제에서는 유용하다. 하지만 이 문제처럼 단순한 연속 구간합의 최대값을 구하는 문제에는 오히려 복잡하고 비효율적이다.
이 문제는 전형적인 동적프로그래밍으로 푸는 문제였다. 그런데 풀이법이 잘 생각나지 않았다.
