반응형 Medium5 [리트코드] Medium 236. Lowest Common Ancestor of a Binary Tree - 자바(JAVA) 문제 설명이진 트리가 주어졌을 때, 주어진 두 노드의 최저 공통 조상(LCA, Lowest Common Ancestor)을 찾아라.Wikipedia의 LCA 정의에 따르면:“최저 공통 조상(LCA)은 트리 T에서 두 노드 p와 q 사이에 정의되며, p와 q 모두의 자손인 노드 중에서 가장 낮은(가장 깊은) 노드를 의미한다. 여기서 노드는 자기 자신을 자손으로 간주할 수 있다.” 제한사항 트리의 노드 수는 [2, 105] 범위입니다.-10⁹ 모든 Node.val은 고유합니다.p != qp와 q는 트리에 존재합니다. 문제 파악두 노드 p, q의 최저 공통 조상(LCA)을 찾는 문제이다.LCA는 p와 q가 자손인 노드 중 가장 아래에 있는 노드이다. (자기 자신도 자손으로 친다.) 접근 방법재귀 탐색(DFS).. 2025. 5. 23. [리트코드] Medium 1091. Shortest Path in Binary Matrix - 자바(JAVA) 문제 설명n x n 크기의 이진 행렬 grid가 주어졌을 때, 이 행렬에서 가장 짧은 "청정 경로(clear path)"의 길이를 반환하세요. 만약 청정 경로가 존재하지 않는다면 -1을 반환하세요.청정 경로란 다음 조건을 만족하는 (0, 0)에서 (n - 1, n - 1)로 가는 경로입니다:경로에 포함된 모든 셀의 값이 0이어야 합니다.경로상의 모든 인접 셀들은 8방향(상하좌우 및 대각선)으로 연결되어 있어야 합니다.청정 경로의 길이는 해당 경로에 포함된 방문한 셀의 개수입니다. 제한사항n == grid.lengthn == grid[i].length1 grid[i][j]는 0 또는 1문제 파악(0, 0)에서 (n-1, n-1)까지 값이 0인 곳만 지나서 갈 수 있는 최단 경로의 길이를 구하는 문제이다.대.. 2025. 5. 13. [리트코드] Medium 785. Is Graph Bipartite? - 자바(JAVA) 문제 설명정점이 0부터 n - 1까지 번호가 매겨진 n개의 노드로 구성된 무방향 그래프가 있습니다. 이때 graph라는 2차원 배열이 주어지며, graph[u]는 노드 u와 인접한 노드들의 배열입니다. 더 정확하게 말하면, graph[u]에 있는 각 노드 v에 대해, 노드 u와 노드 v 사이에 무방향 간선이 존재합니다.이 그래프는 다음과 같은 성질을 가집니다:자기 자신과 연결된 간선(자기 루프)은 없습니다. 즉, graph[u]에는 u가 포함되지 않습니다.중복 간선이 없습니다. 즉, graph[u]에는 중복된 값이 없습니다.v가 graph[u]에 있다면, u는 graph[v]에도 있습니다. (무방향 그래프이기 때문입니다.)그래프는 연결되어 있지 않을 수도 있습니다. 즉, 어떤 두 노드 u와 v 사이에 경.. 2025. 5. 11. [리트코드] Medium 322. Coin Change - 자바(JAVA) 문제 설명당신에게는 서로 다른 금액 단위를 나타내는 정수 배열 coins와, 총금액을 나타내는 정수 amount가 주어집니다. amount를 만들기 위해 필요한 가장 적은 수의 동전 개수를 반환하세요. 만약 동전의 조합으로 해당 금액을 만들 수 없다면 -1을 반환하세요. 각 동전은 무한히 많이 가지고 있다고 가정할 수 있습니다. 제한사항1 1 0 문제 파악주어진 동전 종류를 사용해 특정 금액을 만들 때, 필요한 최소 동전 개수를 구하는 문제이다. 접근 방법bfs를 사용한다.노드는 현재까지 만든 금액을 의미한다.큐에 현재까지 만든 금액을 넣는다.큐에 있는 값(현재 금액)에 동전을 합해서 다음 노드(새로운 금액)를 만든다.이 노드를 전에 방문하지 않았다면 큐에 넣는다.amount(목표 금액)에 해당하는 금액.. 2025. 4. 29. [리트코드] Medium 841. Keys and Rooms - 자바(JAVA) 문제 설명n개의 방이 0번부터 n-1번까지 번호가 매겨져 있으며, 0번 방을 제외한 모든 방은 잠겨 있습니다. 당신의 목표는 모든 방을 방문하는 것입니다. 하지만, 열쇠 없이는 잠긴 방에 들어갈 수 없습니다. 방을 방문하면, 그 안에서 여러 개의 서로 다른 열쇠를 찾을 수 있습니다. 각 열쇠에는 해당 열쇠로 열 수 있는 방의 번호가 적혀 있으며, 이 열쇠들은 모두 가져갈 수 있습니다. rooms라는 배열이 주어지고, rooms[i]는 i번 방을 방문했을 때 얻을 수 있는 열쇠들의 집합을 나타냅니다. 모든 방을 방문할 수 있다면 true를, 그렇지 않다면 false를 반환하세요. 제한사항n == rooms.length2 0 1 0 rooms[i]에 있는 값들은 모두 유일합니다.문제 파악0번 방에서 시작한.. 2025. 4. 28. 이전 1 다음 반응형
