❐ Description이번 문제도 [LeetCode#93] Restore IP Addresses와 마찬가지로  문자열을 동적으로 분할하는 로직이 추가적으로 필요하다.     ❐ 풀이 전략☑️ 주어진 문자열의 분할 시작점을 cursor 변수에 저장한다.☑️ cursor를 시작으로 하는 for문 input의 길이만큼 순회한다. (int i = cursor;)☑️ 부분 문자열의 Palindrome 여부를 확인한다.☑️ 시작 : cursor, 종료 : i + 1     ❐ Solutionpublic class Solution { private final List> subsets = new ArrayList(); public List> partition(String s) { backTra..

❐ Description이번 문제는 기존의 순열이나 조합을 다루는 백트래킹 문제와는 달리, 입력이 문자열로 주어지고 이를조각으로 나누어가며 탐색하는 백트래킹 유형이다. 문자열의 앞뒤를 탐색하며 유효성을 검증해야 하기때문에, 문자열을 동적으로 분할하는 로직이 추가적으로 필요하다.     ❐ 풀이 전략☑️ 문자열 분할의 시작 지점을 cursor 변수에 저장한다.☑️ IP의 8비트 최대 길이인 3만큼 for문을 순환한다.☑️ 문자열 분할의 종료 지점을 cursor + length로 나타낸다.☑️ 생성된 부분 문자열이 0으로 시작하지 않는 10의 자리 숫자 이상인지 확인한다.☑️ 생성된 부분 문자열이 255 이하를 충족하는지 확인한다.☑️ dot(점)의 수가 4개가 넘어간다면 해당 IP는 무시한다.☑️ 현재 c..

❐ Description백트랙킹 문제를 풀면서 면접 질문 대비 겸  개념을 정리해보자.그리고 나만의 풀이 템플릿 까지 작성하여 라이브 코테도 준비하자.     ❐ Back Tracking이란?Back Tracking은 모든 가능한 해를 탐색하기 위해 DFS를 기반으로 하는 알고리즘 설계 기법이다.주로 문제의 해를 구성하는 과정에서, 더 이상 유망하지 않은 해(조건에 부합하지 않거나 불가능한경우)를 만나면 되돌아가(BackTrack) 다른 경로를 탐색한다. 이를 통해 불필요한 계산을 줄이고효율적으로 문제를 해결할 수 있다. DFS 기반 : 트리 또는 그래프 형태로 해를 구성하며, 깊이 우선 탐색을 진행한다.Pruning(가지치기) : 조건에 맞지 않거나 유망하지 않은 경로를 탐색하지 않고 되돌아가는 과정...

❐ Description[LeetCode#46] Permutation Ⅰ에 이은 문제이다.이번 문제에서는 중복된 요소를 제어하는 것이 핵심이다.     ❐ 탐색 과정에서 중복을 피하기1. 아이디어이번 문제를 효율적으로 풀이하기 위해서 꼭 떠올려야 하는 아이디어다.동일한 숫자 중에서, 이전 숫자를 방문하지 않았다면 현재 숫자를 선택하지 않는다.  2. 그림으로 이해하기만약 중복을 피하지 않는다면 아래와 같이 중복되는 경우도 탐색하게 된다. 하지만 탐색 과정에서 중복되는 경우는 탐색하지 않는다면 아래와 같이 불필요한 탐색을 건너 뛸수 있다.  3. 코드로 이해하기private boolean hasDuplicatedElements( int i, int[] nums, boo..

❒ Description날짜2024.11.15 (금)레벨Medium링크https://leetcode.com/problems/longest-repeating-character-replacement/description/알고리즘슬라이딩 윈도우, 투 포인터시간 복잡도O(n²)소요시간2hour풀이 확인 여부Y     ❒ 문제 분석[🔥핵심 아이디어] 윈도우 내에 있는 문제 중, 교체할 수 있는 문자의 갯수를 고려해야 한다. 현재 윈도우 내에서 교체할 수 있는 문자의 수를 구할 수 있어야 한다.현재 교체할 수 있는 문자의 수 = (right - left + 1) - maxCharCount 1. 최대 길이를 구해야 하기 때문에 최초에는 right 커서만 한 칸 씩 움직인다.2. right 커서를 움직이면서 현재 r..

❒ Description날짜2024.10.21 (월)레벨3제목입국심사링크https://school.programmers.co.kr/learn/courses/30/lessons/43238알고리즘Binary Search시간 복잡도O(nlog(n))     ❒ Ideation이번 문제에서는  아래와 같은 제한사항이 있기 때문에 가능한 최소한의 시간복잡도로 문제를 해결해야 한다.제한사항‣ 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.‣ 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.‣ 심사관은 1명 이상 100,000명 이하입니다1️⃣ 우선 심사에 걸릴 수 있는 최대 시간을 찾아야 한다.2️⃣ 이분 탐색을 진행한다.3️⃣ 이분 탐색 ..

❒ Description날짜2024.10.02 (수)레벨Medium제목Search a 2D Matrix링크https://leetcode.com/problems/search-a-2d-matrix/description/알고리즘Binary Search시간 복잡도O(log(n+m))     ❒ Ideation[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]matrix 내의 subArray를 그냥 하나의 덩어리로 바라본다. 우선 matrix에 대해서 binary search를진행하고, target이 포함된 subArray를 찾는다. 만약 없다면 null을 반환한다.subArray[firstIdx] > target : right cursor 이동subArray[la..

❒ Description날짜2024.10.01 (화)레벨Medium제목Search in Rotated Sorted Array링크https://leetcode.com/problems/search-in-rotated-sorted-array/description알고리즘Binary Search시간 복잡도O(logN)     ❒ 문제 및 로직 분석이 문제는 O(logN)의 시간 복잡도로 풀이해야 하는 문제로, pivot을 기준으로 회전된 정렬 배열에서특정 값을 찾아야 한다.int[] nums = {4, 5, 6, 7, 0, 1, 2, 3};  1. Pivot 찾는 방식먼저 pivot을 찾아야 한다. 시간복잡도 제약이 있기 때문에 pivot을 찾는 과정도 O(logN)로 해결해야 한다.Pivot을 찾으려면 `num..