HONG'S DB

접근 방법 문제에서 구현하라는 대로 하면 된다. 인형이 터지는지 판단하는 부분에서는 스택/리스트의 가장 마지막 원소만 비교해주면 된다. 소스 코드 - ArrayList 사용 import java.util.ArrayList; class Solution { public int solution(int[][] board, int[] moves) { int answer = 0; int n = board.length; int m = moves.length; ArrayList basket = new ArrayList(); basket.add(0); for (int i = 0; i < m; i++) { int col = moves[i]; int row = 0; while (row < n && board[row][col..

접근 방법 우선순위 큐를 사용하려고 했는데 그러면 중요도가 같은 문서들이 어떤 순서로 출력될지 모른다는 문제가 있다. → 문제에서 요구한대로 직관적으로 구현했다. 소스 코드 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 Main { static BufferedReader br; static StringTokenizer st; static int T, N,..

접근 방법 이 문제는 간선의 비용이 다르기 때문에 특정 노드(목표치)까지 최단거리를 찾기 위해서는 BFS가 아닌 다익스트라 알고리즘을 사용해야한다. 다익스트라 알고리즘은 큐에 새로운 노드를 넣을 때 마다 노드들을 비용기준 오름차순으로 정렬하고, 가장 비용이 적은 노드를 꺼내며 최단거리를 갱신한다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static BufferedReader br; static StringTokeniz..

접근 방법 연산 하나씩 해보며 탐색 명령어 리스트를 어떻게 기억할까? → class에 숫자와 명령어 속성을 만들까? —> 한번 탐색한 숫자를 반복해서 탐색하면서 시간초과 발생 → 한번 탐색한 숫자는 다시 탐색할 필요 없다. 동적계획법으로 해당 숫자의 방문여부와 명령어 순서를 기록해두는 방법을 사용해서 실행횟수를 줄일 수 있다. D n*2 , > 9999 → mod S n-1, n=0 → 9999 n이 0인지 여부를 먼저 판단해야한다. 안 그러면 n=0으로 들어왔을 때 -1이 리턴되면서 어레이인덱스오류가 남. L (n%1000) * 10 + n/1000 R (n%10) * 1000 + n/10 소스 코드 import java.io.BufferedReader; import java.io.IOException..

접근 방법 섬 표시(BFS) 다리 만들기 바다를 큐에 넣는다 → 바다 중간에서 탐색을 진행할 필요 없다!!! 섬을 큐에 넣는다. (BFS, 이때 시작하는 섬의 인덱스를 매개변수로 전달) 바다이고, 방문하지 않았으면 큐에 넣는다. 섬이고, 시작하는 섬의 인덱스와 현재 인덱스가 다르면 최소값을 업데이트한다. 최종 최소값 반환 최종 최소값 반환 소스 코드 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 Main { s..

접근 방법 육지이면 가장 먼 육지와의 거리 찾기 육지 BFS로 최단거리로 갈 수 있는 가장 먼 거리의 육지를 찾는다. 소스 코드 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 Main { static BufferedReader br; static StringTokenizer st; static int N, M; static char[][] map; static int max_value = 0; static in..

접근 방법 BFS로 방문 가능한 층수 탐색 방문 가능이란 ? 방문한 적 없어야 한다. 현재층 + 위층버튼 ≤ 꼭대기층 현재층 - 아래버튼 ≥ 1층 스타트링크 층 도착 시 이동횟수 출력 더 이상 이동가능한 층이 없으면 use the stairs 소스 코드 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 Main { static BufferedReader br; static StringTokenizer st; sta..

접근 방법 while (true) 시간 + 1 빙하가 녹는다 모든 0인 지점 큐A 에 넣기 하나씩 꺼내면서 인접 빙하 높이 - 1 다 녹았니 ? 0 이 아닌 지점 하나라도 있으면 큐B 에 넣고 return false 아니면 return true → while 문 break, print(0) 한 덩어리니? visited 배열 선언 큐B로 빙하 지점 BFS 빙하인데 visited == false인 지점 하나라도 있으면 return false → while문 break, print(시간) 아니면 return true 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..

접근 방법 처음에는 플로이드-워셜 알고리즘으로 풀어야겠다고 생각했었다. 모든 지점에서 다른 모든 지점까지의 최단경로를 구해야한다고 생각했기 때문이다. 하지만 알고리즘 분류가 BFS라서 다이나믹 프로그래밍을 사용하는 플로이드 워셜은 좋은 방법이 아닐 것 같다는 직감이 들었다. 일단 플로이드 워셜 알고리즘은 시간복잡도가 O(N^3)이기 때문에 별로 쓰고 싶지 않았다. (N이 최대 100이기 때문에 가능할 것 같기는 하다.) 좀 더 고민해보니 각 친구사이의 거리는 항상 1이므로 BFS 탐색으로 각 지점간의 최단거리를 보장할 수 있다는 것을 깨달았다. BFS는 시간복잡도 O(N)으로 이 경우에는 훨씬 효율적일 것이라고 생각했다. (단 모든 사람들을 모두 탐색해야하므로 O(N^2)이다.) BFS로 각 사람 간 최..

최근 회사에서 쿼리 튜닝이 이슈로 떠오르고 있다. 사실 이전에는 튜닝 대상 쿼리를 추출하는 방식이 굉장히 주먹구구식이고, 실행 당시 파라미터도 쉽게 파악할 수 없어서 쿼리 튜닝 작업에 큰 장벽이 있었다. 쿼리 튜닝이 이슈로 떠오르면서 이러한 문제점을 해결하기 위해 Whatap이라는 어플리케이션, 디비 모니터링 툴을 체험판으로 도입해보았고, 결과는 상당히 고무적인 것 같다. 적용 2주만에 DB CPU 부하가 6~7% 정도 감소했다고 한다. 물론 지금까지 거의 튜닝 작업을 하지 않다가 최근 2주 간 굉장히 열심히 튜닝 작업을 해서 발생한 성과라고 할 수 있지만, Whatap의 도입으로 어떤 쿼리가 문제인지 통계자료를 통해 파악하고, 파라미터 값도 쉽게 바인딩 할 수 있어 결정적인 영향을 줬다고 할 수 있다...