CodingTest/LeetCode19 [LeetCode] 70. Climbing Stairs [문제 링크]https://leetcode.com/problems/climbing-stairs/description/ [문제]당신은 계단을 오르고 있습니다. 정상에 도달하려면 n개의 계단을 올라야 합니다. 한 번에 1칸 또는 2칸씩만 이동할 수 있습니다.정상에 도달하는 방법의 수를 반환하세요.[풀이 과정]어떻게 풀어야 하는지 감이 오질 않아 그냥 하나하나 단순하게 구해봤는데 점화식을 찾게 되었습니다. 위 점화식을 토대로 구현을 했습니다.처음에 위 점화식처럼 구현을 했는데 시간 초과가 떠서 생각을 해보니했던 연산을 계속 하고 있는게 생각이나 계산을 하고 memo라는 배열에 값을 저장하고이미 계산한 구간이면 값을 바로 memo에서 찾아 return하는 방식으로 구현했습니다.[코드]class Solution .. 2025. 3. 20. [LeetCode] 841. Keys and Rooms [문제 링크]https://leetcode.com/problems/keys-and-rooms/description/ [문제]당신은 n개의 방(0번부터 n-1번까지 번호가 매겨짐)으로 이루어진 건물에 있다.처음에는 0번 방에 있으며, 이 방은 열려 있다. 나머지 방들은 모두 잠겨 있다. 각 방에는 일부 다른 방의 열쇠들이 들어 있을 수 있다. 열쇠를 이용해 해당 방을 열고 들어갈 수 있다. 모든 방을 방문할 수 있는지 확인하라.모든 방을 방문할 수 있으면 true, 그렇지 않으면 false를 반환한다.[풀이 과정]문제를 보니 출발점 하나를 잡고 깊게 쭉 조사하는게 효과적일 것 같아DFS로 구현하기로하고 구현했다. [코드]class Solution { int x; List> rooms; bo.. 2025. 3. 19. [LeetCode] 1091. Shortest Path in Binary Matrix [문제 링크]https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ [문제]n x n 크기의 이진 행렬 (binary matrix) grid가 주어진다.grid[i][j] == 0 : 이동 가능한 칸 grid[i][j] == 1 : 이동 불가능한 칸 좌상단 (0,0)에서 출발하여 우하단 (n-1,n-1)으로 이동하는 최단 경로의 길이를 구하라.단, 대각선 방향을 포함한 8방향으로 이동할 수 있다. 도착이 불가능하면 -1을 반환한다. [풀이 과정]출발지점부터 도착지점까지 가장 짧게 가는 걸 구해야하기 때문에BFS가 DFS보다 효율적일 것 같아 BFS로 코드를 구현하였다. [코드]class Solution { int x, y;.. 2025. 3. 19. [LeetCode] 200. Number of Islands [문제 링크]https://leetcode.com/problems/number-of-islands/ [문제]m x n 크기의 2D 그리드(grid)가 주어집니다. 그리드에서 '1'은 땅(land), 0'은 물(water)을 나타냅니다.상하좌우로 연결된 '1'들이 하나의 섬을 형성합니다. 그리드에서 섬의 개수를 구하는 함수를 작성하세요.[풀이 과정]문제를 보자마자 DFS, BFS 문제인 것을 알았다.그래서 연습겸 DFS로도 풀어보고 BFS로도 풀어보기로 했다. [코드]DFS 코드class Solution { // 어디서든 사용해야하기 때문에 private int x, y; private boolean[][] visited; private char[][] grid; publ.. 2025. 3. 18. [LeetCode] 104. Maximum Depth of Binary Tree [문제 링크]https://leetcode.com/problems/maximum-depth-of-binary-tree/ [문제]이진트리의 최대 깊이를 구하는 함수를 작성하세요.이진트리의 깊이란,루트 노드에서 가장 깊은 리프 노드까지의 경로에 포함된 노드의 개수를 의미합니다.[풀이 과정]문제를 보자마자 전체 탐색을 사용해야만 할 것 같았고BFS를 사용하여 풀어야겠다고 생각했습니다. [코드]/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val .. 2025. 3. 18. [LeetCode] 2895. Minimum Processing Time [문제 링크]https://leetcode.com/problems/minimum-processing-time/description/ [문제]이진트리에서 두 노드 p와 q가 주어졌을 때, 이 둘의 최소 공통 조상(LCA)을 찾는 문제입니다.최소 공통 조상이란?트리에서 두 노드 p와 q를 모두 자손으로 포함하는 가장 낮은(가장 깊은) 노드를 의미합니다. 즉, p와 q가 다른 서브트리에 있다면 그들의 부모가 LCA가 됩니다. 한쪽이 다른 쪽의 조상이라면, 조상 노드가 그대로 LCA가 됩니다. - 입력root: 이진 트리의 루트 노드 p, q: 트리 내 존재하는 두 노드 (항상 트리 내에 존재함) - 출력p와 q의 최소 공통 조상(TreeNode 객체)을 반환[풀이 과정]처음에 어떤식으로 풀어야 하지?라고 생.. 2025. 3. 16. 이전 1 2 3 4 다음
