🦾 오늘의 컨디션 및 특이사항(개인 일정 등)
- 수면 시간
- 6시간
- 학습 시간
- 10 : 30 ~ 12 : 30
- 15 : 00 ~ 17 : 00
- 특이사항
📑 세부 학습 내용
📅 스케쥴
- 2시간 독서 + 궁금한 개념 조사 및 학습 + 2시간 코딩테스트 및 풀이 리뷰
- 총 4시간
📖 도서 정독 및 실습
실전 레디스 : 기초, 실전, 고급 단계별로 배우는 레디스 핵심 가이드
- 캐싱 등
RDB의 보조 역할을 해줄NoSQL중 가장 범용적이고 유지보수가 잘 진행 중인Redis의 구조부터 기초, 심화 내용, 사용법 등을 확실하게 이해하여, 이후의 프로그래밍에 있어 자신 있고 근거 있게 레디스를 채택하고 사용할 수 있는 개발자를 목표로 독서 시작 - 2.6.2 Sorted Set형 주요 명령어 (p.123) ~ 2.7.2 지리적 공간 인덱스 (p.147)
- 도서 내 모든 내용 이해 및 실습 완료
- 궁금한 부분은 따로 조사 후 학습
- 궁금한 부분은 따로 조사 후 학습
✏️ 코딩 테스트
- 1 SOLVE 및 깃허브 커밋
- 프로그래머스 -
67259 - 문제 유형 :
다익스트라,BFS,DP,시뮬레이션/구현 - https://github.com/oneplast/ProgrammersCT/commit/0ab4ce95198270cab53bdab1ad836cb66fc90637
🔨 트러블 슈팅
- 최초 풀이
class Solution {
PriorityQueue<Point> pq;
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n;
int minWeight = Integer.MAX_VALUE;
public int solution(int[][] board) {
n = board.length;
pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
boolean[][] visited = new boolean[n][n];
visited[0][0] = true;
pq.offer(new Point(0, 0, 0, 0, visited));
while (!pq.isEmpty()) {
Point cur = pq.poll();
int y = cur.y;
int x = cur.x;
int curWeight = cur.weight;
int curDir = cur.direction;
if (y == n - 1 && x == n - 1) {
minWeight = Math.min(minWeight, curWeight);
continue;
}
visited = cur.visited;
for (int[] dir : dirs) {
int nextY = y + dir[0];
int nextX = x + dir[1];
if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < n
&& !visited[nextY][nextX] && board[nextY][nextX] == 0) {
if (x == 0 && y == 0) {
curDir = nextY == 1 ? 1 : 0;
}
int newDirection = -1;
if (curDir == 0) {
if (nextY == y) {
newDirection = 0;
curWeight += 100;
} else {
newDirection = 1;
curWeight += 500;
}
} else {
if (nextX == x) {
newDirection = 1;
curWeight += 100;
} else {
newDirection = 0;
curWeight += 500;
}
}
boolean[][] newVisited = new boolean[n][n];
for (int i = 0; i < n; i++) {
newVisited[i] = visited[i].clone();
}
newVisited[nextY][nextX] = true;
pq.offer(new Point(nextX, nextY, curWeight, newDirection, visited));
}
}
}
return minWeight;
}
static class Point {
int x;
int y;
int weight;
int direction;
boolean[][] visited;
public Point(int x, int y, int weight, int direction, boolean[][] visited) {
this.x = x;
this.y = y;
this.weight = weight;
this.direction = direction;
this.visited = visited;
}
}
}
- 풀이 실패
- 아이디어 :
- 일반
BFS문제처럼 방향 배열을 이용하되, 각pq객체들은 지나온 곳을 또 가면 안되기에, 이전visited배열을 참고하여 새로운newVisited배열 할당 - 방향 변수를 이용하여 코너, 직진을 판단
- 무한 루프나 값 처리가 제대로 이루어지지 않는 등 여러 문제 발생, 풀이 실패
- 일반
- 최종 풀이
class Solution {
int n;
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
Queue<Point> queue = new LinkedList<>();
public int solution(int[][] board) {
n = board.length;
int[][][] arr = new int[n][n][4];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(arr[i][j], Integer.MAX_VALUE);
}
}
if (board[0][1] == 0) {
arr[0][1][0] = 100;
queue.offer(new Point(0, 1, 100, 0));
}
if (board[1][0] == 0) {
arr[1][0][1] = 100;
queue.offer(new Point(1, 0, 100, 1));
}
while (!queue.isEmpty()) {
Point cur = queue.poll();
for (int i = 0; i < dirs.length; i++) {
int nextY = cur.y + dirs[i][0];
int nextX = cur.x + dirs[i][1];
if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < n
&& board[nextY][nextX] == 0) {
int nextWeight = cur.weight + (cur.direction == i ? 100 : 600);
if (arr[nextY][nextX][i] > nextWeight) {
arr[nextY][nextX][i] = nextWeight;
queue.offer(new Point(nextY, nextX, nextWeight, i));
}
}
}
}
return Arrays.stream(arr[n - 1][n - 1])
.min().getAsInt();
}
static class Point {
int y;
int x;
int weight;
int direction;
public Point(int y, int x, int weight, int direction) {
this.y = y;
this.x = x;
this.weight = weight;
this.direction = direction;
}
}
}
- 기존 아이디어 접근 자체는 대부분 정확
- 방향 변수를 추가한 3차원 배열 및 DP 알고리즘,
BFS를 활용하여 문제 풀이 - 현재 문제에서 비효율적인
PriorityQueue대신Queue를 사용 - 초기에 우측, 하측 방향 두 값을 넣고 시작
- 3차원 배열에 넣어둔 방향 변수를 이용하여 배열 참조 및 데이터 기록
DP알고리즘 사용
- 각 방향 요소에서의 접근을 통해 최종 기록된 배열의 마지막 좌표 최소값 반환
- 시간복잡도
O(N^2)board의 각 인덱스 모두 접근, 이중 반복문 : `O(N^2)- 방향 반복은 최대 4회이므로, 사실상 시간복잡도에 큰 영향을 주지 않음
- 최종 시간복잡도
O(N^2)
💡 어려웠던 것 || 알게 된 것
- 금일은 없음
기록