+-------------------------+
| Method Area | 클래스 정보, static 변수
+-------------------------+
| Heap | new로 생성한 객체 저장
| (모든 스레드 공유) |
+-------------------------+
| Stack (Thread 1) | 메서드 호출마다 Frame 생성
| - 메서드 Frame | 지역변수, 파라미터
| - 메서드 Frame | 리턴 주소 등
+-------------------------+
| Stack (Thread 2) | 스레드마다 별도 Stack
| - 메서드 Frame |
+-------------------------+
| PC Register | 현재 실행 중인 명령어 주소
| (스레드별) |
+-------------------------+
| Native Method Stack | JNI 호출용
+-------------------------+
Heap: 객체(인스턴스) 저장 (공용 영역)
Stack: 메서드 호출 정보 저장 (스레드 프라이빗)
OOME, OutOfMemoryError
Java의 Heap 공간은 거의 모든 객체와 인스턴스가 저장되는 영역이다.
그러나 무한 루프 안에서 객체를 계속 생성하거나,
대규모 컬렉션(List, Map 등)을 관리하면서 참조를 끊지 않게 되면,
GC(Garbage Collector)가 불필요한 객체를 수거하지 못해 Heap 공간이 고갈된다.
이럴 때 OutOfMemoryError(OOME)가 발생한다.
대표적인 상황은
무한 객체 생성
캐시(메모리)에 데이터 무한 적재
참조 해제 없이 객체를 쌓아두는 메모리 누수(Leak)
다음 코드 예시를 살펴보자.
import java.util.ArrayList;
import java.util.List;
public class OOMExample {
public static void main(String[] args) {
List<byte[]> list = new ArrayList<>();
while (true) {
list.add(new byte[10 * 1024 * 1024]); // 10MB 배열 계속 추가
}
}
}
위 코드는 10MB 짜리 byte 배열을 무한히 리스트에 추가하는 코드이다.
결국 GC가 치우지 못하고 Heap이 가득 차게 되면서 java.lang.OutOfMemoryError: Java heap space 가 발생한다.
SOE, StackOverflowError
Stack 영역은 각 스레드 프라이빗(스레드의 지역변수같은 느낌)하며,
하나의 스레드 안에서 발생하는 메서드 호출과 지역변수를 관리한다.
메서드가 호출될 때마다 Stack Frame이 쌓이는데,
이 호출이 탈출 조건 없이 무한 반복되거나,
메서드 호출 깊이가 지나치게 깊어지면 Stack 크기를 초과하여
StackOverflowError(SOE)가 발생한다.
대표적인 상황은
탈출 조건이 없는 재귀 호출
너무 깊은 메서드 체인 호출
의도치 않은 순환 호출(loop)
다음 예시 코드를 살펴보자.
public class SOEExample {
public static void main(String[] args) {
recursiveMethod();
}
private static void recursiveMethod() {
recursiveMethod(); // 탈출 조건 없는 재귀 호출
}
}
위 코드는 recursiveMethod()가 끝나지 않고 자기 자신을 계속 호출하는 코드이다.
Stack Frame이 무한히 쌓이다가 Stack 공간을 초과하게 되면서, java.lang.StackOverflowError 가 발생한다.
컨벤션(convention)이란 용어는 cum이라는 라틴어(together를 의미)에서 con과, 라틴어 venire(to come의 의미)에서 vene이라는 말에서 유래한 것으로 '함께 와서 모이고 참석하다'의 의미를 가지고 있다. 즉 컨벤션이란 다수의 사람들이 특정한 활동을 하거나 협의하기 위해 한 장소에 모이는회의(meeting)와 같은 의미라 할 수 있으며전시회를 포함하는 좀 더 포괄적인 의미로 쓰이기도 한다.콘퍼런스(Conference)라고도 한다.
그렇다면, 개발 컨벤션이란 뭘까?
개발 컨벤션은 코드 작성 시 지켜야 할 규칙과 스타일을 정의한 것!!
개발 컨벤션, 즉 개발 규칙은 개발자들끼리 원활한 협업을 하기 위한 중요한 규칙이다.
개발자들마다 코드 스타일이 제각각인데, 서로의 코드를 클린하게 이해하기 위해서는 필수적인 요소이다.
혹은, 본인이 작성한 코드더라도 오랜만에 그 코드를 까봤을 때 낯설게 느껴지는 경우도 많다.
Subject는 최대 50문자를 넘기지 않으며, 특수문자를 사용하지 않는다. 동사는 원형으로만 작성한다.
// 대표적인 Type 의 종류
feat 새로운 기능 추가
fix 버그 수정
docs 문서 수정 (코드 변경 X)
style 포맷, 세미콜론, 들여쓰기 등 순수 스타일 변경
refactor 리팩토링 (기능 변화 없음)
test 테스트 코드 추가/수정
chore 빌드, 설정, 라이브러리 등 변경
perf 성능 개선
build 빌드 시스템 또는 외부 종속성 변경
ci CI 관련 설정 변경 (GitHub Actions, Jenkins 등)
2. 커밋 Body
본문의 경우 한줄당 72자 내로, 양에 구애받기보다는 최대한 상세히 적도록 해야한다.
How 보다는 What 과 Why 에 초점을 맞춰서 작성해야 한다.
(즉, 코드 자체를 설명하기보단, 어떤 요구사항에 의해 개발한건지, 어떤 버그에 의해 수정된건지 작성한다.)
3. 커밋 Footer
꼬리말은 선택사항이다.
이슈 트래커 ID를 작성할 수 있다. 이슈트래커 ID는 `#이슈 번호` 형식으로 작성한다.
`유형:#이슈 번호` 의 형식으로 작성하는데, 유형은 다음과 같다.
이슈 트래커 유형은 다음 중 하나를 사용한다.
Fixes: 이슈 수정중 (아직 해결되지 않은 경우)
Resolves: 이슈를 해결했을 때 사용
Ref: 참고할 이슈가 있을 때 사용
Related to: 해당 커밋에 관련된 이슈번호(아직 해결되지 않은 경우)
(ex) Fixes: #45 Related to: #34, #23
사용 예시
// 가장 기본적인 커밋
feat: 로그인 버튼 클릭 시 로그인 API 연동
// 기능 범위를 포함한 커밋
fix(login): 토큰 저장 오류 수정
// 본문과 이슈 연결까지 포함한 커밋
// 한 줄 요약 + 상세 설명 + 관련 이슈 연결
// GitHub PR이나 이슈에서 자동으로 #42 이슈를 닫아줌
feat(account): 비밀번호 변경 기능 추가
- 기존 API 명세에 따라 변경 요청 및 확인 로직 구현
- 버튼 클릭 시 확인 팝업 추가
Closes #42
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
전형적인 시뮬레이션 문제!
음.. 방금전에 지옥같던 지저분한 문제를 풀다와서 그런가.. 너무 명확해서 좋아요..ㅠㅠ
뱀의 동작을 구현해보자.
단, 방향에 대한 개념을 잘 이용하는 문제인 것 같다!
(하지만 방향에 대한건 지금까지 열심히 연습했지! 핫핫하)
import java.io.*;
import java.util.*;
public class Main {
static int n;
final static int SNAKE = 1;
final static int APPLE = 2;
static int UP=0; static int RIGHT=1; static int DOWN=2; static int LEFT=3;
final static int[][] directions = { // 상 -> 우 -> 하 -> 좌 (오른쪽 순)
{-1, 0, 1, 0},
{0, 1, 0, -1}
};
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader("src/input.txt"));
// BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(reader.readLine());
int k = Integer.parseInt(reader.readLine());
int[][] map = new int[n][n];
for (int i=0; i<k; i++) {
int[] apple = getIntArr(reader.readLine().split(" "));
map[apple[0]-1][apple[1]-1] = APPLE;
}
Map<Integer, String> commandList = new HashMap<>();
int l = Integer.parseInt(reader.readLine());
for (int i=0; i<l; i++) {
String[] command = reader.readLine().split(" ");
commandList.put(Integer.parseInt(command[0]), command[1]);
}
map[0][0] = SNAKE;
// printMap(map);
simulation(map, commandList);
}
static void simulation(int[][] map, Map<Integer, String> commandList) {
ArrayDeque<int[]> que = new ArrayDeque<>();
que.addFirst(new int[]{0, 0});
int dir = RIGHT;
int sec = 0;
while (true) {
sec ++;
int[] head = que.peekFirst();
int[] tail = que.peekLast();
int x = head[0] + directions[0][dir];
int y = head[1] + directions[1][dir];
if (!inRange(x, y) || map[x][y] == SNAKE) { // 뱀 몸통
System.out.println(sec);
break;
}
if (map[x][y] == 0) { // 전진.
int[] removed = que.pollLast();
map[removed[0]][removed[1]] = 0;
}
que.addFirst(new int[]{x, y});
map[x][y] = SNAKE;
if (commandList.containsKey(sec)) {
if (commandList.get(sec).equals("D")) {
dir++;
} else {
if (dir == 0) dir = 3;
else dir--;
}
dir %= 4;
}
}
}
static boolean inRange(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
static int[] getIntArr(String[] strArr) {
return Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
}
static void printMap(int[][] map) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
음.. 구현인가?
일단 각 CCTV의 상태의 경우의 수를 구하고,
그 상태별로 비쳐서 # 칠을 해야한다.
그냥 처음부터 끝까지 구현인건가?
시간 복잡도를 구해보자.
각 CCTV의 경우 최대 4가지의 경우의 수가 존재한다. (물론 2번은 두가지지만.)
CCTV는 최대 8개니까, 8개의 CCTV가 4가지 방향 중 하나를 비추는 모든 경우의 수는...
4x4x4x4x4x4x4x4 = 4의 8승 = 65,536 개!
그냥 계산하면 되나..?
아, 이거 조합의 DFS 문제구나.
여러 CCTV가 존재하고,
해당 CCTV마다 최대 4가지의 선택 가능한 방향이 존재한다.
모든 CCTV에 대해서 하나의 방향만을 선택하고, 그 선택 조합을 구하는 것이었다..
먼저, CCTV가 특정 방향을 비출 때 map을 바꾸고, 사각지대의 수를 줄여보자.
/**
* x, y 좌표에서 시작해서 dir 방향으로 비춘다.
* @param map 얕은 복사로 # 를 채워 넣는다.
* @param x 시작하는 x좌표
* @param y 시작하는 y좌표
* @param dir 비출 방향
* @param squareZone 비추기 전 사각지대의 수
* @return 비춘 이후, 줄어든 사각지대
*/
static int watching(int[][] map, int x, int y, int dir, int squareZone) {
x += directions[0][dir];
y += directions[1][dir];
while (inRange(x, y)) {
if (map[x][y] == 6) break;
if (map[x][y] == 0) {
map[x][y] = -1;
squareZone --;
}
x += directions[0][dir];
y += directions[1][dir];
}
return squareZone;
}
O(V + E)
// V: 정점 수 (노드 수)
// E: 간선 수 (연결선 수)
// 그러나 `연구소`문제처럼 2차원 격자 배열일 경우에는,
O(N × M)
// N × M: 맵 크기 (전체 칸 수)
왜이렇게 계산하나면,
BFS는 각 칸을 최대 한 번씩만 방문함
각 칸에서 상하좌우 최대 4번 시도함 → 상수 시간
즉, 2차원 격자 배열일 때는 BFS의 시간복잡도를 O(전체 칸 수)로 계산한다.
그러면 O(64)! 고작 상수 ... 64번의 복잡도가 나왔다..
브루트포스 + BFS 가 맞구나
두 시간복잡도를 합쳐봐야 37,820 x 64 = 242,048번
시간 제한 1초당 1억번 안에 무조건 풀이가 가능한 양이다.
연구소에 바이러스가 퍼지는 BFS부터 구해보자.
/**
* 특정 상황을 제공하면, 바이러스가 퍼지고 난 후의 안전 구역의 합을 알려준다.
* @param map 현재 상황
* @param virus 바이러스 큐
* @param safeZone 안전 구역의 수
* @return 바이러스가 다 퍼지고 난 후의 살아남은 안전 구역의 수
*/
static int getSafeZone(int[][] map, Queue<Pos> virus, int safeZone) {
while (!virus.isEmpty()) {
Pos pos = virus.poll();
for (int dir=0; dir<4; dir++) {
int x = pos.x + directions[0][dir];
int y = pos.y + directions[1][dir];
if (inRange(x, y) && map[x][y] == 0) {
safeZone --;
map[x][y] = 2;
virus.add(new Pos(x, y, pos.val));
}
}
}
return safeZone;
}
파라미터로 넘어오는 map과 queue의 경우 깊은 복사를 해서 넣어주어야 한다.
그 이유는, 벽 3개가 세워진 각각의 조합별로 바이러스가 퍼지는 `상태`가 다를 것이기 때문이다.
결국 분기점에서 상태가 변화하기 때문!
조합.. 조합을 구하자..
여기서 좀 헤맸다.
왜냐면..
좌표를 기준으로 조합을 만들려다 복잡해짐
(a1, a2), (b1, b2), (c1, c2)처럼 2차원 for문 중첩으로 조합 구현 시 열 기준 증분 조건을 잘못 설정하면 일부 조합 누락 또는 중복 발생
중복 없는 조합인데, 중복된 경우 고려를 따로 안 함
벽을 세울 때 (0,1)-(1,1)-(2,1)과 (2,1)-(1,1)-(0,1)이 같은데 별도로 거르지 않음
조합을 구하랬더니 왜 순열을.. ㅠㅠ
조합을 너무 복잡하게 구현하려 했음
map에서 직접 좌표 조작보다, 빈 칸 리스트를 만들고 index 기반 조합이 훨씬 간결하고 정확함
그러다 조합을 구현하는 방식에는 2가지가 있다는 것을 깨달았다.
1. 리스트 인덱스 기반 3중 for문
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
for (int k = j + 1; k < list.size(); k++) {
// list.get(i), list.get(j), list.get(k)
}
}
}
값이 map 으로 구현되어 있다고 map 으로만 접근하라는 법은 없다..
좌표를 List에 넣고 순차적으로 모두 들려보도록 하자..
2. DFS 방식 (일반 조합)
조합의 개수가 유동적이거나, 백트래킹 조건이 필요한 경우
void dfs(int depth, int start) {
if (depth == k) {
// 조합 완성
return;
}
for (int i = start; i < n; i++) {
selected[depth] = arr[i];
dfs(depth + 1, i + 1);
}
}
그러나 이 문제에서는 1번, 리스트 기반으로 조합을 풀어도 충~분히 가능하다!
최종 코드 (조합 포함)
import java.io.*;
import java.util.*;
public class Main {
static int[][] directions = {
{-1, 1, 0, 0},
{0, 0, -1, 1}
};
static String[] directions_string = {"↑", "↓", "←", "→"};
static int n;
static int m;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int[] inputs = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
n = inputs[0];
m = inputs[1];
int zero_count = 0;
int[][] map = new int[n][m];
List<Pos> combin = new ArrayList<>();
Queue<Pos> virus = new LinkedList<>();
for (int i=0; i<n; i++) {
inputs = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j=0; j<m; j++) {
map[i][j] = inputs[j];
Pos pos = new Pos(i, j, inputs[j]);
combin.add(Pos.clone(pos));
if (inputs[j] == 0) zero_count ++;
if (inputs[j] == 2) virus.add(Pos.clone(pos));
}
}
int result = Integer.MIN_VALUE;
for (int i=0; i< combin.size(); i++) {
if (combin.get(i).val != 0) continue;
int a1 = combin.get(i).x;
int a2 = combin.get(i).y;
for (int j=i+1; j< combin.size(); j++) {
if (combin.get(j).val != 0) continue;
int b1 = combin.get(j).x;
int b2 = combin.get(j).y;
for (int k=j+1; k< combin.size(); k++) {
if (combin.get(k).val == 0) {
int c1 = combin.get(k).x;
int c2 = combin.get(k).y;
int[][] newMap = deepCopyMap(map);
newMap[a1][a2] = 1;
newMap[b1][b2] = 1;
newMap[c1][c2] = 1;
Queue<Pos> newVirus = deepCopyQue(virus);
int safeZone = getSafeZone(newMap, newVirus, zero_count-3);
result = Math.max(result, safeZone);
}
}
}
}
System.out.print(result);
}
static Queue<Pos> deepCopyQue(Queue<Pos> virus) {
Queue<Pos> newVirus = new LinkedList<>();
for (Pos pos : virus) {
newVirus.add(Pos.clone(pos));
}
return newVirus;
}
static int[][] deepCopyMap(int[][] map) {
int[][] newMap = new int[n][m];
for (int i=0; i<n; i++) {
if (m >= 0) System.arraycopy(map[i], 0, newMap[i], 0, m);
}
return newMap;
}
/**
* 특정 상황을 제공하면, 바이러스가 퍼지고 난 후의 안전 구역의 합을 알려준다.
* @param map 현재 상황
* @param virus 바이러스 큐
* @param safeZone 안전 구역의 수
* @return 바이러스가 다 퍼지고 난 후의 살아남은 안전 구역의 수
*/
static int getSafeZone(int[][] map, Queue<Pos> virus, int safeZone) {
while (!virus.isEmpty()) {
Pos pos = virus.poll();
for (int dir=0; dir<4; dir++) {
int x = pos.x + directions[0][dir];
int y = pos.y + directions[1][dir];
if (inRange(x, y) && map[x][y] == 0) {
safeZone --;
map[x][y] = 2;
virus.add(new Pos(x, y, pos.val));
}
}
}
return safeZone;
}
static boolean inRange(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
static void printMap(int[][] map) {
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
class Pos {
int x;
int y;
int val;
public Pos(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
public static Pos clone(Pos pos) {
return new Pos(pos.x, pos.y, pos.val);
}
}
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.
낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
낚시왕이 오른쪽으로 한 칸 이동한다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
상어가 이동한다.
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.
상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.
입력
첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.
출력
낚시왕이 잡은 상어 크기의 합을 출력한다.
음.. 시뮬레이션(구현) 문제!
딱히 상태값이 달라지는 분기점도 없고,
상어의 이동! 만 잘~ 구현하면 되는 문제인 것 같다. 상어가 벽에 부딪히면 방향을 전환하는 것만 조금 까다롭지 않을까..?
왜 골드1씩이나 되는 문제일까? 나중에 구현할 때 어려운 점이 생기려나?
먼저 상어 객체부터 생성해보자.
class Shark implements Comparable<Shark> {
int x;
int y;
int speed;
int dir;
int size;
public Shark(int x, int y, int speed, int dir, int size) {
this.x = x;
this.y = y;
this.speed = speed;
this.dir = dir;
this.size = size;
}
@Override
public int compareTo(Shark shark) {
return shark.size - this.size;
}
}
Comparable 인터페이스를 상속한 이유는, PrioryQueue<Shark> 에 넣어서 크기(size)가 큰 순대로 정렬하기 위함이다.
즉, Comparable + PrioriQueue 전략을 사용하기 위함이다!
왜 PrioryQueue 에 상어 객체를 넣으려고 하냐면..
낚시왕이 상어를 낚고 난후, 모든 상어를 이동시키기 위해서는, 모든 상어에 접근해야 한다.
그러나 상어를 자료구조가 Shark[][] map밖에 없다면, 모든 상어에 접근하기 위해서 map의 크기인 RxC만큼 순회해야 할 것이다.
그렇게 되면, 상어가 없는 칸도 불필요하게 조회하게 될 것이며,
R이나 C의 값이 커지면 불필요한 이중 반복문의 크기만 더 커지게 될 것이다.
또한, 만약 RxC의 값(map의 크기)보다 상어의 수가 현저히 적다면, (예를 들어) 3마리의 상어를 찾기위해 100x100의 맵을 전부 뒤져야 하는 상황이 발생할 수도 있는 것이다. 그러면 3마리를 위해서 10,000 번의 탐색이 일어나는 것이다.
이때 PrioryQueue(우선순위 큐)에 상어의 크기가 큰 순서대로 정렬해 놓으면 어떻게 될까?
또, 이 방식을 사용하면, 상어가 한 칸에 두마리 이상 만날때마다 상어의 크기를 비교하지 않아도 된다.
어짜피 그 다음에 도착한 상어라면, 더 크기가 작은 상어일 테니까.
1. 낚시왕이 오른쪽으로 한 칸씩 움직인다.
// 1. 낚시 왕이 오른쪽으로 한칸씩 움직인다.
for (int col=0; col<c; col++) {
// 2. 해당 열에서 낚시 왕이 상어를 낚는다.
// 3. 상어가 이동한다.
}
열의 갯수만큼, 해당 열에서 낚시 왕이 할 일은 정해질 것이다.
또한, 열의 갯수만큼, 모든 상어는 대이동을 할 것이다.
2. 해당 열에서 낚시 왕이 (가장 가까운) 상어를 낚는다.
// 2. 해당 열에서 가장 가까운 상어를 잡는다.
for (int row=0; row<r; row++) {
if (map[row][col] != null) {
// 상어가 존재한다. 잡아올리자.
Shark caughtShark = map[row][col];
resultSize += caughtShark.size;
map[row][col] = null;
break;
}
}
3. 상어가 이동한다.
Shark[][] newMap = new Shark[r][c];
PriorityQueue<Shark> newQueue = new PriorityQueue<>();
// 3. 상어가 이동한다.
int cnt = sharksCount;
while (cnt -- > 0) {
Shark shark = queue.poll();
// 바로 직전 잡아올려진 상어면 큐에서 제외하고, 다음 상어로 넘어간다.
if (map[shark.x][shark.y] == null) {
sharksCount --;
continue;
}
// 상어가 진짜 이동한다.
int x = shark.x;
int y = shark.y;
// 스피드 만큼 이동한다.
for (int i=0; i<shark.speed; i++) {
// 범위 밖이면, 뒤로 돌아야 한다.
if (!inRange(x, y, shark.dir, r, c)) {
shark.dir = changeDir(shark.dir);
}
x += directions[0][shark.dir];
y += directions[1][shark.dir];
shark.x = x;
shark.y = y;
}
if (newMap[x][y] == null) {
// 가려는 공간에 다른 상어가 없네. 먹고 먹힐 일은 없겠군!
newMap[x][y] = shark;
newQueue.add(shark);
} else {
// 이미 해당 공간에 다른 상어가 있다면, 현재 상어의 정보를 다시 넣지않는다.
// 먹혔기 때문.. 우선순위 큐라서 뒤이어 온 상어가 무조건 크기가 더 작다.
sharksCount --;
}
}
map = newMap;
queue = newQueue;
sharksCount(상어의 수)는 상어가 현재 몇 마리 있는지 통제하기 위해서 만들어 놓은 변수이다.
이 변수는 PrioryQueue<Shark> 와는 따로 저장되지만, 결국 우선순위 큐에 들어있는 상어의 수일테니,
상어가 잡힐 때마다 상어의 수와 우선순위 큐를 둘 다 알맞게 조정해주어야 한다. (물론 map 도!)
나는 기존 map과 newMap을 따로 만들었다.
또 기존 queue와 newQueue를 따로 만들었다.
그 이유는 하나의 map에서만 정보를 조정해버리면, 복잡한 상황이 생겼기 때문이다.
바로, 상어가 모두 이동을 완료한 이후에, 같은 칸에 두 상어가 있는지 확인해야 하는데, 아직 이동하지 않은 상어와 이동한 상어에 대해서 동시에 관리하기 힘들었다.
queue의 경우도 하나의 큐에서만 정보를 조정해버리면, 복잡한 상황이 생겼기 때문이다.
바로, PrioryQueue 특성상 가장 우선순위가 큰 객체가 들어오면 그 객체를 맨 앞에 두기 때문이었다.
낚시 왕이 특정 열에서 수행하는 하나의 Round에서는, 한 번 탐색한 객체는 이제 다음 Round 에서 사용되어야 했다.
그러니까 큐에서 FIFO 의 기능도 필요로 했던 것이다. 하지만 우선순위 큐에서는 이미 조회되었다고 하더라도 가장 큰 객체를 무조건 앞에 놓았기 때문에, 같은 객체만(주로 가장 큰) 계속해서 조회하게 되었다.
그런데 이 기능을 구현할 때 실수한 점 한가지가 나왔다.
★ 새로운 자료구조로 갱신하도록 만들었으면, 그 다음 라운드에서도 사용할 수 있게, 새로 만든 자료구조를 기존 자료구조에 넣어야 할 것 아니냐 ㅠㅠ
즉, 새로운 자료구조를 만들어놓고, 다음 라운드 시작 전, 기존 자료구조에 갱신을 안했다.
map = newMap;
queue = newQueue;
바로 위 코드를 빼먹은 것.
또 다음 코드도 빼먹었다.
shark.x = x;
shark.y = y;
상어 객체의 위치를 바꾸어주었으면, 위치 정보도 바꾸어줘야할 것 아니냐 ㅠㅠ
여기까지 했을 때, 다한 줄 알았지만, 경곗값 확인을 안했다.
상어가 0마리일 땐, 아예 로직을 타지 못하게 하자...
아~ 테스트케이스 다 맞았으니까 이제 정답이겠지 ?????
어라......
자.. 시간 복잡도를 계산해보자.
열(C)의 수는 최대 100, 행(R)의 수도 최대 100 이니까, -
1번(낚시 왕이 오른쪽으로 한 칸씩 움직인다)랑
2번(해당 열에서 가장 가까운 상어를 잡는다)를 수행했을 때의 시간 복잡도는,
기껏해야 10,000번이다. 그러나 시간 제한이 1초이니까, 1억번보다는 무조건 낮다.
자 .. 이제 3번(상어가 이동한다.)를 계산해보자.
열의수(C) x 상어의 수(M) x 상어의 스피드(s) 의 최댓값은,
100 x 10,000 x 1,000 = 1,000,000,000 번
어? 10억 번??
어디서 줄일 수 있지? 어디서 반복을 더 줄일 수 있지 ? ? ?
낚시 왕이 오른 칸으로 이동하는 열의 수를 줄일 수는 없다.
그건 한 시뮬레이션 Round가 돌아가는 핵심 단위이기 때문이다.
그렇다면.. 상어가 이동하는 것을 줄일 수 있나?
그것도 그렇지 않다.. 모든 상어는 무조건 이동해야 한다..
결국, 상어를 스피드 만큼 이동하는 로직을 최소 1/10 으로 줄여야 한다는 건데 ....
뭔가 규칙성이 있나 ?? ㅠㅠ
라고 생각하던 차에, 생각해보니..
상어는 현재의 자리에서 ..
예를들어 방향이 좌우라면, (열(C)의 수-2)*2 + 2 = 2(C-1) 번
위아래라면, (행(R)의 수-2)*2 + 2) = 2(R-1) 번
이 횟수라면 제자리로 돌아온다..
그렇다면 이 횟수보다 speed(s) 값이 크다면..
이 횟수만큼 speed를 나눠서, 나머지만큼만 이동하는 것을 계산하면 되는 것이다..!!
그러면 스피드의 최대 횟수는 s%C 혹은 s%R 이다.
이는 스피드의 수는 1000 에서 1000%100 까지 주는 것이다.
최대 1000을 최대 100으로 나눴을 때, 아무래도 최악의 나머지 값은, 나누는 값 - 1 일 것이다.
따라서 최대 99개가 최악의 경우이다.
다시 시간 복잡도를 계산해보면,
열의수(C) x 상어의 수(M) x 상어의 스피드(s) 의 최댓값 = 100 x 10,000 x 99 = 99,000,000번 = 약 9천9백만번.. !!
class Person implements Comparable<Person> {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
return this.age - other.age; // 나이 오름차순 정렬
}
}
Comparable 은 특정 객체를 생성했을 때, 해당 객체의 Override 메소드로써 호출이 가능하다.
Comparable 인터페이스를 상속(implements)한 뒤에, 해당 객체를 PriorityQueue(우선순위 큐)에 넣으면 자동으로 compareTo 메서드의 기준대로 정렬이 되어서 큐에 삽입 된다.
즉, 가장 처음에 poll() 해서 나오는 값은, compareTo 메서드의 기준에 따라 가장 앞 순위에 배치된 Person 객체일 것이다 !
이때, compareTo 객체는, 더 적은 정수값이 나온 객체가 더 우선순위를 갖는다.
List<Person> list = new ArrayList<>();
Collections.sort(list); // Person 내부 compareTo 기준으로 정렬
구체적으로 위와 같이 사용된다.
Comparator - 외부에서 비교 기준을 정함
Comparator<Person> byName = new Comparator<Person>() {
@Override
public int compare(Person a, Person b) {
return a.name.compareTo(b.name); // 이름 기준 정렬
}
};
독립적인 전략 객체처럼 사용되며, 주로 외부에서 사용된다.
즉, 정렬 전략을 외부에서 넘겨주는 독립 객체인 것이다!
Collections.sort(list, byName); // 이름 기준으로 정렬
list.sort((a, b) -> a.name.compareTo(b.name)); // 혹은 람다로 이렇게 표현도 가능!
위와 같이 사용된다.
왜 두개나 있을까?
왜냐하면.. 두 인터페이스의 목적이 다르기 때문이다!
구분
설명
Comparable
정렬 기준을 가진 객체 스스로가 구현하는 인터페이스 (implements Comparable<T>)
void change(int x) {
x = 100;
}
int a = 10;
change(a);
System.out.println(a); // 결과는 10이 나온다. 100으로 변하지 않는다.
보통은 완전한 값 복사의 형태를 띄기 때문에, a 의 값은 바뀌지 않는다.
그러나..
참조 타입(객체)
class Box { int value = 10; }
void change(Box b) {
b.value = 100;
}
Box box = new Box();
change(box);
System.out.println(box.value); // 100 이 출력된다! 값이 바뀐것이다.
파라미터 Box b 는 Box box 객체를 가리키는 참조값을 복사한다.
따라서 b.value 의 값을 바꾸면, box.value 의 값도 바뀌는 것이다.
이에 따른 DFS 에서 주의할 점.
Fish[][] copiedTank = originalTank; // 얕은 복사
위 이중 배열에는 Fish 객체가 정의되어 있다.
기존 originalTank 이중 배열을 복사하려는 로직이지만, 이렇게되면 의미가 없어진다.
왜냐하면 복사한 배열인 copiedTank 는 originalTank 의 참조값을 가져올 것이기 때문에,
copiedTank 내부의 Fish 객체를 수정하면 자동으로 originalTank 내부의 Fish 객체도 수정되어버린다.
이때 DFS는, 분기별로 다른 상태값을 가지면서, 다시 이전 상태로 돌아가(BackTraking) 새로운 분기 상태 객체를 만들어야 한다. 그런데 객체 배열 복사를 위와 같이 해버리면, 다시 이전 상태로 돌아갈 수 없게 된다. 이미 원본 객체도 수정되어 버렸기 때문이다.
그래서 깊은 복사를 해야한다.
Fish[][] copy = new Fish[4][4];
for (...) {
copy[i][j] = original[i][j] == null ? null : new Fish(...);
}
매 객체를 순회하면서 Fish 객체를 새로 생성해주는 깊은 복사를 해주어야만 한다.
그런데 변화할 Fish 객체가 적다면, 매번 모든 배열을 복사하는 것은 메모리에 부하가 크다.
거기다가 상태를 다르게 가져가야하는 분기점의 수가 많다면 상황은 더 악하된다.
이 때 사용하기 좋은 것이 in-place + BackTracking 전략이다.
어떤 전략일까? 바로..
별도의 상태 복사 없이 현재 상태를 그대로 사용하면서,
재귀 호출 전과 후에 직접 원상복구하는 방식
void dfs(state) {
// 현재 상태 변경
변경하기();
// 다음 상태로 재귀
dfs(nextState);
// 상태 원상복구 (backtrack)
복구하기();
}
DFS 란, 재귀를 하면서 해당 분기의 모든 처리가 끝난 다음에, 다시 이전의 메소드로 돌아간다(BackTracking).
다시 이전의 메소드(상태)로 돌아갔을 때, 상태가 일관적이어야 하므로,
다시 다른 분기를 타기전에 상태를 원상복구 해주는 것이다.
간단한 예시를 들자면 다음과 같다.
Fish eatenFish = tank[x][y];
int[] prevPos = fishPos[eatenFish.num].clone();
// 상태 변경
tank[x][y] = null;
fishPos[eatenFish.num][0] = -1;
// DFS 호출
dfs(...);
// 복구
tank[x][y] = eatenFish;
fishPos[eatenFish.num] = prevPos;
