제목과 본문에서 찾습니다.
❓문제목표 위치까지 멈출 때 최소 이동거리상, 하, 좌, 우 한 방향으로만 움직임 장애물이나 가장자리 부딪힐 때까지 직진🖐️손코딩height, width, visiteddx = {-1, 1, 0, 0}dy = {0, 0, -1, 1}bfs(startx, starty, matrix) queue.offer([starty, startx, cnt=0]) visited[starty][startx] = true while(!queue.isEmpty()) info = queue.poll() cury = info[0] curx = info[1] curcnt = info[2] if(matrix[cury][curx] == 'G') ..
❓문제rows X columns 크기의 행렬 (x1, y1, x2, y2) 영역에 해당하는 직사각형의 테두리 숫자를 시계방향으로 회전🖐️손코딩main(): matrix[rows][columns] num = 1 answer[queries.length] for(i: 0 ~ rows-1) for(j: 0 ~ columns-1) matrix[i][j] = num num++ for(i : queries) left, right, top, bottom temp = matrix[top][left] min = temp for(x: top+1 ~ bottom) m..
❓문제시추관을 수직으로 하나만 뚫을 수 있음. 여러 덩어리의 석유를 시추관이 지나가면 그 합을 시추할 수 있음.시추할 수 있는 석유의 최대양을 리턴.🖐️손코딩bfs(start: 석유가 있는 칸): queue.offer(석유 있는 칸의 좌표) while(queue가 비어있지 않을 때) curx: 현재 x값 cury : 현재 y값 덩어리 + 1 cols.add(cury) : 덩어리가 있는 칸의 y값(시추관이 y값만 신경쓸거임!) for(상하 좌우): 1. 격자 볌위 밖이면 패스 2. 이미 방문했으면 패스 3. 석유 없으면 패스 queue.offer(다음 석유 칸)..
❓문제주어진 항공권을 모두 이용한 여행 경로(여러 개일 경우 알파벳 순으로) 🖐️손코딩Tickets을 인덱스 기준으로 사전순으로 정렬 => 항상 사전순임을 보장bfs(curNode){ for(i: 0 ~ tickets 수) if(visited[i] == false) if(curNode[1] == Tickets[i][0]) answer.add(Tickets[i]) curNode = Tickets[i] bfs(curNode) answerlist.remove visited[i] = false }main{ tickets을 오름차순으로 정렬 ..
❓문제이웃한 집은 털 수 없다는 조건에서 도둑질했을 때 가장 많은 돈을 털 수 있는 방법Return Max(도둑질 값)🖐️손코딩## 처음에 생각했던 방법현재 위치 i에서 털 수 있는 집 중 가장 많은 돈을 보유한 집(leetcode 점프 게임과 유사한 방식)-> Greedy 법으로 최적해를 보장하지 못함dp[i] -> 0~i번째 집까지 고려했을 때 가능한 모든 경우의 돈의 합 중 최댓값def rob() for(i:0~n) i를 터는 경우 : MAX(money[i], dp[i-2]+money[i])// dp[i-2]+Money[i] >= money[i] -> dp[i-2]+money[i] i를 안터는 경우 : dp[i-1] dp[i] = Max(dp[i-2]+money[i], dp[i-1..
❓문제괄호를 어디에 치느냐에 따라 결과가 달라짐 -> 이 결과들 중 최솟값을 Return🖐️손코딩dpMax[i][j] : i번째 숫자부터 j번째 숫자까지 만들 수 있는 최댓값dpMin[i][j] : i번째 숫자부터 j번째 숫자까지 만들 수 있는 최솟값i~j의 중간 인덱스 : kk == '+' : Max = leftMax + rightMax Min = leftMin + rightMink == '-' : Max = leftMax - rightMin Min = leftMin - rightMax return dpMin[0][n-1]구간 DP는 구간 길이를 기준으로 범위 지정해야함!👩💻구현 코드import java.util.*;class Solution { public int so..
❓문제물 웅덩이를 피해 집에서 학교까지 갈 수 있는 최단 경로의 개수🖐️손코딩물 웅덩이의 위치 : boolean puddle[][]에 넣기DP : 해당 칸까지 도달할 수 있는 최단 경로의 개수for(1~i) for(1~j) i==1, j==1 일 때는 왼쪽 값, 위쪽 값 그대로 복사 물웅덩이가 true 일 때는 continue 그 외에는 왼쪽값 + 위쪽값 더한값 (파스칼 삼각형)👩💻구현 코드class Solution { public int solution(int m, int n, int[][] puddles) { int answer = 0; int[][] dp = new int[n+1][m+1]; boolean[][] pu..
❓문제숫자 N을 8개 이하와 사칙연산만을 사용해서 number 만들 때 N 사용횟수의 최솟값 구하기(단, 8개 이상 사용하면 -1)🖐️손코딩DP를 사용해서 dp[i] = N을 i개 사용해서 만들 수 있는 모든 숫자의 집합(Set) EX)N = 5, number = 12dp[1] = 5dp[2] = 555+55-55*55/5dp[3] = 55555-5(dp[2] - dp[1])55+5(dp[2] + dp[1])55/5(dp[2] / dp[1])55*5(dp[2] * dp[1])...이런식으로 dp[4]를 만들 수 있는 방법은 dp[1]+d[3] dp[2]+dp[2] dp[3]+dp[1] 의 조합즉,for(i=현재)for(j=1부터 현재-1까지)for(k=현재-j)j+kj-kj*kj/k👩💻구현 코드i..