Algorithms (31) 썸네일형 리스트형 [LeetCode] 98. Validate Binary Search Tree 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Validate Binary Search Tree 문제 요약 (Validate Binary Search Tree)이진 트리가 주어졌을 때,해당 트리가 Binary Search Tree(BST)ㅡ 인지 판별하는 문제 문제링크: https://leetcode.com/problems/validate-binary-search-treeBST의 정의는 다음과 같다. 모든 노드에 대해 왼쪽 서브트리의 모든 값 오른쪽 서브트리의 모든 값 > 현재 노드 값 🤔 처음 떠올린 아이디어처음에는 이렇게 생각했다. “왼쪽 자식은 부모보다 작고,오른쪽 자식은 부모보다 크면 되지 않을까?” 그래서 자연스럽게 부모와 자식만 비교하는 재귀 코드를 작성했다.if (roo.. [LeetCode] 91. Decode Ways 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Decode Ways 문제 요약 (Decode Ways)숫자로만 구성된 문자열 s가 주어지고, 'A'=1, 'B'=2, ..., 'Z'=26으로 매핑된다.문자열을 디코딩할 수 있는 모든 방법의 수를 구하라. 문제링크: https://leetcode.com/problems/decode-ways 🤔 처음 떠올린 생각문제를 보자마자 핵심 키워드는 “방법의 수”였다.즉, 모든 경우를 고려해야 하는 문제라는 점이 바로 보였다. 하지만문자 하나씩 모든 경우를 완전 탐색으로 나열한다면같은 부분 문자열을 반복해서 계산하게 되고결국 시간 초과가 날 것이라고 판단했다.그래서 자연스럽게“이미 계산한 경우의 수를 저장해두자” 라는 생각으로 이어졌고, DP + 메모이제이션이 가장 먼저 떠올.. [LeetCode] 79. Word Search (Java) - DFS, 백트래킹 ✔️ 오늘의 리트코드 공부 기록 – Word Search (백트래킹 사고의 시작) 문제 요약 (Word Search)2차원 보드(board)에서 단어(word)가 상하좌우 인접한 연속 칸을 따라 존재하는지 확인하는 문제 문제링크: https://leetcode.com/problems/word-search 문제를 바라보는 관점문제의 핵심 조건: “연속된 경로 + 이미 방문한 칸 재사용 금지”그러면 질문을 이렇게 바꿀 수 있다. 👉 “보드에서 특정 칸을 선택하면 다음 칸은 어디로 이동할까?”답: 항상 상하좌우로 갈 수 있는 선택지 중 아직 방문하지 않은 칸여기서 자연스럽게 떠오르는 접근:특정 칸에서 시작해서 단어의 다음 글자를 탐색막히면 이전 상태로 돌아가서 다른 경로 탐색 이 때 이전에 방문했던 노드는 .. [LeetCode] 76. Minimum Window Substring 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Minimum Window Substring문제 요약 (Minimum Window Substring)문자열 s와 t가 주어진다.s 안에서 t의 모든 문자를 개수까지 포함하는가장 짧은 연속 부분 문자열(substring) 을 반환하라.순서 상관 ❌부분 문자열 (연속) ⭕중복 문자 개수까지 고려 ⭕문제 링크https://leetcode.com/problems/minimum-window-substring/ 🤔 처음 떠올린 아이디어문제 내에서 시간 복잡도 O(m+n) 으로 해결하려면...연속된 구간 중에서 조건을 만족하는 가장 짧은 구간을한 번의 순회로 찾을 수는 없을까? 💡 핵심 깨달음: 슬라이딩 윈도우문제를 다시 보면 구조가 명확해진다.연속된 구간조건 만족 여부 존재최.. [LeetCode] 73. Set Matrix Zeroes 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Set Matrix Zeroes 문제 요약 (Set Matrix Zeroes)m x n 행렬이 주어질 때, 어떤 원소가 0이라면, 그 원소가 속한 행 전체와 열 전체를 0으로 설정해야 한다.⚠️ 단, 추가 배열 없이(in-place) 해결해야 한다. 문제링크: https://leetcode.com/problems/set-matrix-zeroes 🤔 처음 떠올린 아이디어처음 문제를 봤을 때는 이렇게 생각했다.0을 발견하면, 그것을 queue와 같은 곳에 저장하고, 하나씩 꺼내면서 그 원소 위치의 행이랑 열을 전부 0으로 만들면 되지 않을까? 그래서 자연스럽게 떠올린 방식은:0의 위치를 Queue에 저장하나씩 꺼내면서 위 / 아래 / 왼쪽 / 오른쪽으로 전부 0 처리즉,.. [LeetCode] 62. Unique Paths 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Unique Paths문제 요약m x n 격자가 주어지고, 오른쪽 또는 아래로만 이동할 때 가능한 경로의 수를 구하라.문제 링크: https://leetcode.com/problems/unique-paths🤔 처음 떠올린 아이디어도착점까지 항상 아래, 오른쪽으로만 갈 수 있으므로,행을 위에서부터 내려오면서 각 칸의 경로 수를 갱신하면 어떨까라는 생각이 들었다.첫 행과 첫 열은 이동 방향이 하나뿐이므로 1로 초기화나머지 칸은 위쪽과 왼쪽에서 오는 경로 수의 합으로 계산💡 핵심 깨달음: DP로 점화식 세우기각 칸 (r,c)까지 올 수 있는 경로 수 = 위에서 오는 경로 수 + 왼쪽에서 오는 경로 수즉, dp[r][c] = dp[r-1][c] + dp[r][c-1]코드 .. [LeetCode] 56. Merge Intervals 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Merge Intervals문제 요약 (Merge Intervals)여러 개의 interval이 주어진다.각 interval은 [start, end] 형태이며,서로 겹치는 구간들을 하나로 병합해서 반환해야 한다. 문제 링크: https://leetcode.com/problems/merge-intervals🤔 처음 떠올린 아이디어처음 문제를 봤을 때는 이런 생각이 들었다.겹치는지 판단하려면,interval들이 어떤 순서로 정렬돼 있으면 좋을까? 모든 interval을 서로 비교하면 복잡해진다.그래서 비교 대상을 최소화할 수 있는 정렬 기준이 필요했다. 💡 핵심 깨달음: 시작점만 정렬하면 된다겹침 여부의 조건은 단 하나다.현재 interval의 start ≤ 이전 in.. [LeetCode] 55. Jump Game 풀이 (Java) ✔️ 오늘의 리트코드 공부 기록 – Jump Game 문제 요약 (Jump Game)정수 배열 nums가 주어진다.각 원소 nums[i]는 현재 인덱스 i에서 최대 몇 칸까지 점프할 수 있는지를 의미한다.배열의 첫 번째 인덱스(0)에서 시작해서마지막 인덱스에 도달할 수 있는지를 판단하는 문제다.문제 링크: https://leetcode.com/problems/jump-game 🤔 처음 떠올린 아이디어처음 문제를 봤을 때는 이렇게 생각했다.현재 위치에서 갈 수 있는 모든 경우를 다 탐색해보면 되지 않을까?그래서 자연스럽게 떠오른 접근은:재귀,DFS 혹은 DP즉, 현재 인덱스에서1 ~ nums[i] 만큼 점프해 보면서하나라도 끝에 도달하면 true를 반환하는 방식이다.논리적으로는 맞는 접근이다.실제로 구현.. 이전 1 2 3 4 다음
