Algorithm/내용 정리

❐ Description1. Requests주어진 두 문자열의 겹치는 subsequence 중 가장 긴 문자열의 길이를 반환하라.겹치는 부분이 없다면 0을 반환하라. 두 문자열의 순서를 유지한 채 공통으로 존재하는 가장 긴 부분 수열을 찾는 것 2. Constrains`1 제약 조건에 의하면 시간복잡도는 최대 O(n²)까지는 괜찮다.     ❐ Approach  1 - 2D memoization (Bottom - Up)class KtSolutionV1 { fun longestCommonSubsequence(text1: String, text2: String): Int { val maxRow = text1.length val maxCol = text2.length ..

❐ Description[LeetCode#1143. Longest Common Subsequence]를 풀면서 학습한 LCS 알고리즘 정리 *참고 블로그 : [알고리즘] 그림으로 알아보는 LCS 알고리즘    ❐ Longest Common Subsequence란?우선 Longest Common Subsequence의 의미를 이해하자.LCS란 두 문자열의 순서를 유지한 채 공통으로 존재하는 가장 긴 부분 수열을 찾는 것이다.부분 수열이기 때문에, 주어진 문자열에서 순서만 유지하면 몇 개든 건너 뛰어도 된다.Longest Common Substring이란?주어진 문자열에서 순서를 유지한 채 공통으로 존재하는 연속된 문자를 찾는 것     ❐ 점화식 이해하기1. 두 문자가 동일한 경우//text1[i - 1]..

❐ Description[LeetCode#274] HIndex를 풀면서 Counting Sort를 알게 됐다. 이를 직접 구현해보자!     ❐ 특징시간 복잡도최선, 평균, 최악 모구 O(n+k)n : 정렬할 데이터의 개수k : 데이터 값의 범위비교 기반이 아님데이터를 비교하지 않고, 데이터의 출현 횟수만 이용하여 정렬한다.안정정렬데이터의 순서를 유지하며 정렬한다.한계점데이터 범위가 크면 비효율적이다.정수 또는 정수로 변환 가능한 데이터에만 사용할 수 있다.부동소수점이나 복잡한 객체에는 적합하지 않다.     ❐ 순서대로 구현해보기Step1. 주어진 배열의 요소 중 최댓값 찾기int maxElement = Arrays.stream(nums).max().getAsInt();  Step2. 길이가 `최대값 ..

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

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

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

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

❒ Description이분 탐색의 동작과정을 정리하자.     ❒ Binary Search 이진 검색이란 정렬된 배열에서  타깃을 찾는 검색 알고리즘이다. 어떠한 경우에는 O(logN)의 시간복잡도를 갖는다. 동작 방식은 아래와 같다.      ❒ 효율적인 중앙 찾기만약 아래와 같이 중앙 위치를 찾는면 중앙 값은 0이 나오게 된다.int start = Integer.MAX_VALUE;int end = Integer.MAX_VALUE;int mid = (start + end) / 2;그 이유는 start와 end의 합이 자료형의 최댓 값을 넘어가기 때문이다.  이런 경우를 방지하기 위해서 다음과 같이 중앙 값을 찾아야 한다.int start = Integer.MAX_VALUE;int end = Integ..