Backtracking | LeetCode - 60. Permutation Sequence java

문제https://leetcode.com/problems/permutation-sequence 문제 설명1~n을 나타내는 숫자 범위 n, 순열의 k번째를 나타내는 순서 k가 주어질 때 k번째 숫자를 출력하는 문제입니다. 접근 방법백트래킹을 이용하여 순열을 구할 수 있었습니다. 전체 코드class Solution { // n과 k는 자주 쓸 것이기 때문에 전역변수로 빼줍니다. int cnt = 0,n,k; String answer = ""; public String getPermutation(int n, int k) { this.n = n; this.k = k; dfs(0, "", new boolean[n]); return answer; ..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 10. 9.
• textsms

Stack | LeetCode - 42. Trapping Rain Water Java

https://leetcode.com/problems/trapping-rain-water각 블록의 길이가 1인 구조물의 높이가 주어지는데, 비가 온 뒤 얼만큼의 빗물을 받을 수 있는지 구하는 문제이다. 전체 코드// 좌우의 벽 중 최소 벽의 높이 만큼 비가 찬다class Solution { public int trap(int[] height) { Deque st = new ArrayDeque(); int cnt = 0; int left = 0; for(int i = 0; i height[st.peek()]){ int top = st.pop(); if(st.isEmpty()) break; ..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 10. 7.
• textsms

DP | LeetCode - 62. Unique Paths Java

https://leetcode.com/problems/unique-paths 격자의 크기 m, n이 주어질 때, 왼쪽 위(0, 0)에서 오른쪽 아래(m-1, n-1)까지 가는 경로의 개수를 구하는 문제이다.(이때, 격자의 크기는 m x n) 풀이격자의 각 지점(i, j)에 도달할 수 있는 경로의 수는 그 지점에 도달하기 위해 거쳐왔던 지점들의 경로 수의 합과 같다.따라서 이전에 지나왔던 경로에 경로의 수가 저장되어있다면 많은 연산을 하지 않아도 손쉽게 경로의 수를 구할 수 있다.(Memoization) 코드class Solution { int[][] dp; public int uniquePaths(int m, int n) { dp = new int[m][n]; for(..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 9. 2.
• textsms

Dijkstra | LeetCode - 1514. Path with Maximum Probability Java

https://leetcode.com/problems/path-with-maximum-probability/  가중치가 성공률을 나타내는 무방향 그래프에서 최대 성공률을 구하는 문제입니다.시작 노드와 끝노드, 간선 정보, 가중치 정보가 주어지므로 다익스트라로 구현할 수 있습니다. 풀이성공률은 곱연산이므로 노드를 탐색하며 가중치를 곱한 값으로 구할 수 있었습니다.지금까지의 다익스트라 문제들은 최소 비용을 구하는(최소힙을 이용한) 문제들이 많았지만, 최대 성공률을 구해야하므로 최대 힙을 이용하여 구현하였습니다. https://i-am-strong-man.tistory.com/search/dijkstra 김스트롱의 스트롱 공부 노트 i-am-strong-man.tistory.com  성공률은 곱연산이므로 최초..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 9. 1.
• textsms

DP | LeetCode - 198. House Robber Java

https://leetcode.com/problems/house-robber 이 문제를 DP를 이용하는 문제로, 프로그래머스의 도둑질 문제와 유사합니다.https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이 문제에서 특정 집까지 도달했을 때 훔친 금액의 최대 값을 DP 테이블을 사용하여 저장하면 빠르게 해결할 수 있습니다. 문제에서 이웃한 옆 집을 같은 날에 훔친다면 경고가 울리므로 도달한 현재 집에서 훔칠 것인지, 바로 전 집을 훔칠 것인지를 결정해..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 8. 28.
• textsms

DP | LeetCode - 746. Min Cost Climbing Stairs Java

https://leetcode.com/problems/min-cost-climbing-stairs 층의 꼭대기까지 계단을 오르는데, 바닥(0) 또는 첫번째 계단에서 시작하여 최소 비용으로 계단을 오르는 문제입니다.이때, 계단을 하나씩 오르거나 두 개씩 오를 수 있습니다.풀이계단의 어느 지점까지 오르는데 드는 최소의 비용은 정해져있고, 위의 계단으로 올라가는 최소의 비용은 그 이전에 올라왔던 계단의 최소 비용 + 추가 비용이 되므로 큰 문제가 작은 문제를 포함하는 문제입니다.따라서 DP로 해결할 수 있습니다.우선, DP테이블에 담을 값을 정의하자면dp 테이블에는 각 계단까지의 최소 비용을 담습니다.DP테이블 dp의 인덱스는 인덱스 i번 째까지의 최소 비용을 뜻합니다.그리고 dp 테이블을 채우는 방법은,0번..

• format_list_bulleted Algorithm/LeetCode
• · 2024. 8. 28.
• textsms