❐ Description[LeetCode#198. House Robber] 문제를 풀면서 메모이제이션 방식에 능숙하지 않음을 파악했고,간단한 예제와 함께 두 가지(top-down / bottom-up) 방식을 숙달하자.      ❐ 메모이제이션이란?메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 특히 동적계획법(DP)의 핵심이 되는 기술이다. 주로 배열 또는 맵을 이용해서 결과를 저장한다.      ❐ 구현하는 두 가지 방식1. Top-Down (하향식)재귀 기반의 접근으로, 문제를 더 작은 하위 문제로 나누어 풀어가며, 이미 계산한 결과를 저장..

❐ Description문제링크https://leetcode.com/problems/longest-consecutive-sequence/description/난이도medium(골드3~2)     ❐ 문제 분석주어진 배열에서 가장 긴 연속되는 요소의 길이를 구하는 문제이다.중복되는 숫자는 제외해야 하며, `O(n)`의 시간 복잡도로 구현해야 한다.     ❐ 문제 풀이1. 시간 복잡도 `O(NlogN)`정렬을 사용해서 풀이할 수 있는 방법이다. 물론 문제의 요구사항인 시간복잡도 보다 크지만,문제 제약 조건이 허술해서 이 방법으로도 풀이는 된다.public int longestConsecutive(int[] nums) { Arrays.sort(nums); int maxLength = -1; ..

❐ Description[LeetCode#162] Find Peak Element 문제를 풀면서 단순하게 생각했던 부분을 바로 잡자.     ❐ Find Peak Element 이진 탐색이란 오름차순으로 정렬된 리스트에서 단조성을 이용해 특정값을 찾는 알고리즘이다. (wiki 링크)단조성이란? 값이 한 방향으로 증가하거나 감소하는 특성 그래서 이 문제를 처음에 접근할 때 이진 트리를 어떻게 사용하라는 거지? 라는 생각을 헀다.왜냐면 주어진 배열은 오름차순이 아니기 때문이다. 하지만 해당 문제의 요구사항 중 하나는`O(logN)`의 시간 복잡도로 풀이를 하는 것이다.     ❐ 정렬되어 있지 않아도 Binary Search를 적용할 수 있다.위에서 단조성에 대해서 이야기 했다. 그럼 다음 배열은 단조성을 ..

❐ Description문제 링크Koko Eating Bananas난이도medium / Gold 4~3     ❐ 문제 분석 및 접근 piles : 바나나 더미h : 가드가 자리를 비우는 시간k : 원숭이가 한 시간동안 먹을 수 있는 바나나 갯수 int[] piles = {10, 13, 34, 55}예를 들어 위와 같은 경우에, 원숭이가 시간당 먹을 수 있는 바나나의 갯수(k)가 15라면 원숭이가 모든 바나나 더미를 다 먹는데 걸리는 시간은 아래와 같을 것이다.‣ 10개 - 1시간‣ 13개 - 1시간‣ 34개 - 3시간‣ 55개 - 4시간  원숭이가 먹을 수 있는 최소 바나나 갯수는 1개이고 최대 바나나 갯수는 piles 중 가장 큰 수이다.⇨ 정답 k는 이 사이에 존재한다. 그리고 위의 예시에서 `k ..

❐ Description[1631. Path With Minimum Effort] 문제를 다시 풀었는데 제대로 풀지 못해서 정리한다.     ❐ 접근 방식 (Binary Search)여기서는 Mid 값일 때 움직일 수 있는 경로만 움직이는 것이 핵심 포인트다. lowerEffort, upperEffort를 각각 설정한다.최소 : 0최대 : 1_000_000lowerEffort가 upperEffort 보다 작을 때만 while문을 수행한다.시작점으로 부터 좌,우,위,아래를 순회하는데Mid 값보다 작거나 같은 경우에만 이동할수 있다.목표 지점에 도달했는지 확인한다.도달하지 못함 ⇨ 현재 Mid 값으로 부족 ⇨ 더 큰 Mid 값이 필요 ⇨ lower = mid;도달 함 ⇨ 현재 Mid 값으로도 충분 ⇨ 최소..

❐ Description이번 문제는 Binary Search + Greedy로 해결하는 문제였다.백준으로 치면 실버1~골드4 사이의 난이도 이번 문제에서 문제의 조건이 단조성을 가지기 때문이다. 단조성은 특정 조건이 증가하거나 감소함에 따라결과가 변하지 않고 일정한 방향으로 변화하는 성질을 의미한다.  이와 유사한 문제로 최근에 풀어본 [Path With Minimum Effort] 문제가 있다.     ❐ 접근 방식이분 탐색을 위해 주어진 price 배열을 오름차순 정렬한다.이분 탐색 초기화 최솟값(0)과 최댓값(price 배열 내 최대값 - 최소값) 사이에서 탐색하며 가능한 최적의 답을 찾는다.이분 탐색 수행중간 값 mid를 계산하고, tastiness가 mid일 때 k개의 사탕을 선택할 수 있는지 ..

❐ Description[5. Longest Palindromic Substring] 문제를 풀면서 알게 된 Manacher 알고리즘 정리. ❐ Manacher 알고리즘 이해하기Manacher 알고리즘은 문자열에서 가장 긴 팰린드롬 부분 문자열을 효율적으로 찾는 알고리즘이다.일반적인 방법으로 풀 경우 O(n²)의 시간 복잡도가 걸리지만, Manacher 알고리즘은 이를 O(n)으로 줄여준다.이 알고리즘은 팰린드롬의 대칭성을 이용하여 중복 계산을 줄이는 방식(동적 프로그래밍)으로 동작한다. 코드로 이해해 보았다. 다른 블로그들은 변수명이 엉망 그 자체다...변수명의미radiuses반지름 배열currentCenterIdx탐색 과정에서 수시로 변경되는 중심 인덱스centerIdxOfMaxPalin..

❐ Description날짜2024.12.13 (금)레벨Medium링크https://leetcode.com/problems/surrounded-regions/description알고리즘 & 자료구조DFS, Queue시간 복잡도O(n•m)      ❐ Approach 1해당 좌표를 방문한 이력이 없고, Land(O)인 부분 부터 탐색을 시작한다.동서남북 방향으로 DFS를 실행한다.현재 위치를 WALL(X)로 변경한다.Queue에 현재 위치를 담는다.현재 위치를 방문 처리한다. ➔ 순회를 최적화하기 위함.동서남북이 WALL(X)로 둘러 쌓여 있지 않은 경우Queue에 있는 모든 좌표를 Land(O) 표시로 변경한다.public void solve(char[][] board) { int maxRow = ..