매일 조금씩

1. DFS (깊이 우선 탐색)DFS는 그래프의 한 방향으로 깊이 들어가서 탐색을 마친 후, 돌아와서 다른 경로를 탐색하는 방식이다. Java에서는 주로 재귀 호출이나 스택 자료구조를 사용하여 구현한다.시간복잡도 : O(V+E) (V: 노드 수, E: 간선 수)DFS 예제 코드 (Java)import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set;public class GraphTraversal { private Map> graph; public GraphTraversal(Map> graph) { this.graph = graph; ..

dp란?문제를 작은 부분 문제들로 나누어 해결하고, 그 해답을 재활용하여 전체 문제를 해결하는 알고리즘.중복되는 부분문제, 최적 부분 구조 문제에 적용된다. 메모이제이션과 타뷸레이션 방식을 통해 시간 복잡도를 크게 줄일수 있다. dp를 구성하는 핵심 개념메모이제이션 (Memoization)주로 재귀 호출과 함께 사용필요한 부분 문제를 만나면 그때 계산하며, 계산된 결과는 캐시에 저장함.탑다운(Top-down) 방식이라고 부름. 메모리 사용량이 더 많을 수 있지만, 불필요한 부분은 계산하지 않기 때문에 효율적임각 부분 문제는 최대 한 번만 계산됨.타뷸레이션 (Tabulation)주로 반복문을 사용하여, 작은 문제부터 순차적으로 해답을 구해가는 방식모든 부분 문제를 미리 계산해 테이블에 저장함.바텀업(Bot..

이문제는 구현 문제이다. 원쿠션을 한다는 것을 통해 벽을 기준으로 점을 대칭시킨다는 생각을 가장 먼저 해야하고, 시작공과 목표 공이 x축이나 y축에 수평으로 놓여있을때 4개의 벽 한 벽에선 시작공이 벽보다 목표공을 맞추게 되므로 이를 예외 시켜야한다. import java.util.*; class Solution { static class Point{ int x,y; public Point(int x, int y){ this.x = x; this.y = y; } } public int[] solution(int m, int n, int startX, int startY, int[][] balls) { int[] answer = new int[balls.length]; Point border = new P..

BFS로 풀수 있는 문제이다. 항상 문제를 제대로 읽어야한다. 갈수 있는 상하좌우 방향으로 한칸씩 도는게 아니고.. 모든방향을 장애물이나 맨끝에 부딪힐때까지 미끄러져서 가는 것이 한번의 이동이다. 따라서 (0,0)에서 아래방향으로 가는데 장애물이 없어서 맨끝인 (n,0)까지 미끄러진다하면 (0,0)에서 (n,0)까지 가는것이 한번의 이동인 것이다. 또한, 목표물인 G까지 도달하는 것도 이 원칙이 적용 되어서 G의 상하좌우에 장애물있거나 G가 맨끝에 위치하는 경우에만 G에 도착이 가능하다. import java.util.*; class Solution { private final int[] dx = {-1,1,0,0}; private final int[] dy = {0,0,-1,1}; private fin..

그리디로 풀수 있는 문제이다. 이문제를 가장 먼저 접근했을때 실수한 것이 무조건 맨 첨에 다이아 곡괭이부터 광물을 캐기 시작한다고 생각한 것이다. 한 곡괭이 당 광물을 5개까지는 무조건 캐야하니 광물 리스트를 보고 가장 피로도가 높은 광물 구간은 가장 좋은 곡괭이로 캐야하는 것이다. 그러기 위해선 가장 먼저 광물 리스트에서 5개씩 구간을 잘라서 해당 구간에서 곡괭이별 피로도 합산을 구해야한다. 1. 특정 구간의 곡괭이별 피로도 합산 클래스를 (내코드에선 TiredSumPerPick) 만들어야한다. 2. 광물 리스트를 돌며 5개씩 피로도 합산을 구해서 피로도 합산 리스트를 만든다. 3. 피로도 합산 리스트에서 돌곡괭이로 캐는 경우 합산 값들끼리 비교하여 내림차순 정렬한다. 4. 곡괭이 리스트는 이미 가장 ..

. 생각해야할 경우의 수가 많았던 문제이다. 과제(Task) 클래스를 하나 만들어서 PriorityQueue와 Stack 을 사용하면 수월하게 풀수 있다. PriorityQueue말고 Arrays를 써서 정렬해서 써도된다 import java.util.*; class Solution { static class Task{ private String name; private int start; private int playtime; public Task(String name, int start, int playtime){ this.name = name; this.start = start; this.playtime = playtime; } public Task(String name, int playtime){..