본문 바로가기

알고리즘/📌leetcode17

Climbing Stairs - #dp 📌 문제 1칸 혹은 2칸으로만 위를 올라갈 수 있다. N칸을 갔을 때, N칸을 올라올 수 있는 경우의 수는? https://leetcode.com/problems/climbing-stairs/ 📌 문제 풀이 📌 코드 public class Main { public static void main(String[] args) { Solution solution = new Solution(); int i = solution.climbStairs(45); System.out.println(i); } static class Solution { public int climbStairs(int N) { if(N==1) return 1; if(N==2) return 2; int[] dp = new int[N+1]; dp.. 2021. 12. 3.
Unique Paths - #dp 📌 문제 길 경우의 수 문제 https://leetcode.com/problems/unique-paths/ 📌 문제 풀이 📌 코드 public class Main{ public static void main(String[] args){ int m=5; int n=5; Solution solution = new Solution(); solution.uniquePaths(m,n); } static class Solution{ public int uniquePaths(int N,int M){ int[][] map = new int[N][M]; for(int i=0;i 2021. 12. 3.
Course Schedule - 위상정렬 📌 문제 [2번 강의를 듣기 위해서는 1번이 필요하다.] 라는 명제를 [2,1]로 표시한다. 각 코스들이 '위상정렬' 적으로 돼 있는지 true, false를 출력하라. https://leetcode.com/problems/course-schedule/ 📌 문제 풀이 🔥 위상 정렬 🔥 풀이 inDegree의 값이 모두 0이라면 순서대로 들어간 것이므로, true가 나오고, 0이 하나라도 없다면 위상정렬 적으로 이루어진 것이 아니므로 false를 return 한다. 📌 코드 import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String.. 2021. 11. 30.
Word Ladder 📌 문제 시작단어와 끝 단어가 주어진다. ex) 시작 : hit // 끝 : cog 중간단어들이 주어진다. ex) ["hot","dot","dog","lot","log","cog"] 단어들은 한 글자씩 바뀔 수 있다. ex) hit -> hot 바뀐 단어가 중간 단어에 포함돼 있다면, 그 단어는 해당 단어로 바뀔 수 있다. 시작단어에서 시작해서 중간 단어들을 걸쳐서 끝 단어로 갈 때, 몇 단계를 거치는 지 출력하라. https://leetcode.com/problems/word-ladder/ 📌 문제 풀이 해당 단어를 맨 앞자리 부터 맨 뒷자리까지 알파벳 26자리를 전부 넣으면서 바꿔본다. 해당 단어가 중간 단어에 해당한다면, queue에 넣는다. queue에는 처음 시작 값을 넣고, queue가 빌때까.. 2021. 11. 30.
Max Area of Island 📌 문제 해당 1의 면적 중, 1의 개수가 가장 많은 면적을 return 하기. 위의 문제에서는 주황색으로 칠해진 만큼인 6을 return https://leetcode.com/problems/max-area-of-island/ 📌 문제 풀이 해당 값의 count의 상태를 알면서 나갈 때는 parameter로 넘기는 dfs보다 bfs가 더 편하다고 생각해서 bfs를 이용해서 풀었다. 📌 코드 import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Solution solution = new Solution(); int i = solution.maxAreaOf.. 2021. 11. 30.
Maximum Depth of Binary Tree 📌 문제 트리의 최대 깊이를 구하는 문제 https://leetcode.com/problems/maximum-depth-of-binary-tree/ 📌 문제 풀이 - DFS, BFS 📌 코드 - DFS public class MainDFS { public static void main(String[] args) { TreeNode node = new TreeNode(3); node.left = new TreeNode(9); node.right = new TreeNode(20); node.right.left = new TreeNode(15); node.right.right = new TreeNode(7); Solution solution = new Solution(); solution.maxDepth(n.. 2021. 11. 30.
Binary Tree Level Order Traversal 📌 문제 자식 노드들의 값을 level별로 묶고, 순회하면서 출력할 것. https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/ 📌 문제 풀이 📌 코드 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; /** * date : 21.11.29 * link : https://leetcode.com/problems/binary-tree-level-order-traversal/ * memo : 강좌 위치로는 queue / stack 에 존재 */ public class MainV2 { publi.. 2021. 11. 30.
BaseBall Game , Valid Parentheses 📌 BaseBall Game - 문제 +면 두 숫자 더해서 넣기, D면 전 숫자 double, C면 지우기 https://leetcode.com/problems/baseball-game/ 📌 풀이 🔥 주의점 문제를 잘 봐야 한다. 문제 잘못봐서, 당연히 계산하면 스택에서 빼는걸로 생각했다 ( 계산기처럼 ) stack 은 뺀 거 그대로 넣을라면, 뺀 순서의 반대로 넣어주어야 원래 순서가 유지된다. 📌 코드 public class Main { public static void main(String[] args) { Solution solution = new Solution(); int i = solution.calPoints(new String[]{"5", "-2", "4", "C", "D", "9", "+.. 2021. 11. 28.

티스토리툴바