본문 바로가기
728x90
반응형

Major-

 (865)
[LeetCode- Part. 4] 5. 이진 매트릭스 최단경로 (+BFS) https://leetcode.com/problems/shortest-path-in-binary-matrix/ Shortest Path in Binary Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 예외처리 (1) 갈 수 없는 경우 (2) 시작점 또는 도착점이 1인 경우 (3) 시작점이 도착점인 경우 2. BFS를 돌면서 도착점이면 리턴 class Solution { public int shortestPathBinaryMatrix(int[..
[LeetCode- Part. 4] 4. 최대 정사각형 # (+ 2차원 DP) https://leetcode.com/problems/maximal-square/ Maximal Square - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 규칙을 찾아서 DP 배열을 작성한다. class Solution { public int maximalSquare(char[][] matrix) { //1. ds int m = matrix.length; int n=matrix[0].length; //DP에서 필요한 길이만큼 배열 생성 int[][] dp =..
[LeetCode- Part. 4] 3. 작업 일정의 최소 난이도 # (+ 2차원 DP) https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/ Minimum Difficulty of a Job Schedule - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com jobDifficulty ={6,5,4,3,2,1}, d=2 jobDifficulty ={7,1,7,1,7,1}, d=3 문제 분석 날짜들의 최솟값을 구하기 위해서는 각각의 날짜의 최곳값을 더해야한다. -> DP로 구현 가능한 ..
[LeetCode- Part. 4] 2. 슬라이딩 윈도우 최댓값 ##(+슬라이딩 윈도우, Deque) https://leetcode.com/problems/sliding-window-maximum/submissions/ Sliding Window Maximum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. K값에 해당하는 윈도우 초기값 설정 2. 한칸씩 제거하고 추가하는 작업 수행 3. 타임리밋 발생 +) 스트림을 이용한 최댓값 구하기 //스트림을 int형으로 매핑 후, 최댓값 찾아서 스트림을 다시 int형으로 변환 Integer maxValue =li..
[LeetCode- Part. 4] 1. N일 후 감옥 ## (+ 재귀함수, Arrays.toString, 삼항연산자) https://leetcode.com/problems/prison-cells-after-n-days/submissions/ Prison Cells After N Days - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 2중 for문 -> 타임리밋 발생 2. 재귀 이용 class Solution { public int[] prisonAfterNDays(int[] cells, int n) { //감옥이 사용될경우 1, 비어있을 경우 0 //양쪽의 감옥이 모두..
[LeetCode- Part. 3] 5. Province의 수 (+DFS) https://leetcode.com/problems/number-of-provinces/ Number of Provinces - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 연결된 도시를 찾는다. -> 직접연결과 간접연결 2. 초기값을 전달한 후, 초기값에서 연결된 모든 도시를 찾는다. 3. 연결된 모든 도시 찾기 종료 후, 다음 도시들은 모두 세면서 연결되어있는지 찾는다. class Solution { static int answer; public i..
[LeetCode- Part. 3] 4. 숫자를 영어 단어로 변환 # (+분할과 정복) https://leetcode.com/problems/integer-to-english-words/ Integer to English Words - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 참고 자료 https://and-some.tistory.com/897 [LeetCode- Ch3. 배열] 5. 빗물 담기 # [+ 분할과 정복] https://leetcode.com/problems/trapping-rain-water/ Trapping Rain Water..
5. 퍼즐게임 (+ 2차원 DP) // 퍼즐게임 // 2장의 카드가 남을 때 까지 반복해서 뽑는다 -> (뽑은 카드)*(뽑은 왼쪽 카드)*(뽑은 오른쪽 카드) 결과를 더한다. // 나열된 카드 중에서 맨 왼쪽 카드와 맨 오른쪽 카드는 뽑아서는 안된다. // 맨 마지막 동작을 하고 나면, 두 장의 카드가 남는다. // 당신의 목표는 동작을 모두 하고나서, 각 동작의 점수의 합이 최소가 되도록 동작 +) 세련된 풀이 : 동적계획법 dy[i][j] : i번째부터 j번째까지의 까지의 부분수열을 게임동작했을 때 얻을 수 있는 최소 점수 package Q5; import java.util.*; class Main2 { public int solution(int[] nums){ int n=nums.length; int[][] dy = new int[..
728x90
반응형

티스토리툴바