매일 조금씩

문자열이 하나 주어지고 조건에 만족하는 결과를 도출하도록 하는 문제의 유형은 매우 다양하다.대충 정리해보자면 다음과 같다.슬라이딩 윈도우 최대/최소길이start, end 투 포인터 활용anagram 판별s.toCharArray() 로 char[] 변환 후Arrays.sort() 사용palindrome 판별, 최대/최소길이start, end 투 포인터 활용중심확장법Character의 스태틱 함수 사용 (숫자 or 문자 인지 확인)Character.isLetter(), Character.isLetterOrDigit()여기서 가장 어려웠던 유형은 1번의 슬라이딩 윈도우였다.문제의 난이도가 어려워질수 있는 가능성이 더 많아 보였다.HashMap과 투 포인터, 적절한 변수들을 선언하여 풀어내야한다. 다음은 슬라이..

matrix 문제는 일반적인 그래프 문제와 비슷하게 출제될수도 있다.그러나 그래프 알고리즘을 요구하지 않고,matrix 그 자체로, '구현' 하듯이,matrix를 반전 시키거나 일정한 규칙에 의해 값들을 이동시켜야하는 경우도 있다. 따라서 matrix 관련 문제가 나오면 그래프(dfs, bfs) 알고리즘으로 풀 수 있는 문제인지를 먼저 파악한 후, 그게 아니라면 문제에서 요구하는 matrix 특징을 파악하고 접근하는 것이 중요하다.

[LinkedList의 특징]총 길이를 알수 없어서 노드를 순회해야한다.사이클이 발생할 수도 있다. [LinkedList 관련 문제의 특징]링크드 리스트 문제 중, 링크드 리스트의 head를 리턴해야하는 경우가 있다.이땐, head 노드를 next로 하는 dummy 노드를 선언해놓고 링크드 리스트에서 여러 작업을 하고, dummy.next를 리턴하는 식으로 하면 된다. 링크드 리스트의 고난도 문제들은 대부분, next의 방향을 바꿔야할 때가 있다.방향을 바꾸기 위해선 기존 next를 저장할 temp 노드가 필요하다. 여기서 더 나아가, 링크드 리스트의 크기를 알아야 해결할 수 있는 문제들이 있다.예를 들어, 링크드 리스트의 가운데 노드를 찾아야하는경우, 링크드 리스트에 순환이 있는지 파악해야하는경우 등...

개념Interval은 구간 배열 or 리스트가 주어지며, 구간을 삽입, 삭제, 병합 하는 문제가 주어진다.  특징관련 문제 유형은 다음 세가지로 볼 수 있다.새로운 구간 하나를 구간들 사이에 넣기.구간들의 겹치는 부분을 정리하기.최대 겹치는 구간 길이 구하기.이때, 각 구간은 [시작점, 끝점]의 형식으로 시작점과 끝점이 배열로 정의되어 있다. interval 문제는 정렬이 중요하다.구간 배열이 intervals라고 하면 시작점이나 끝점을 기준으로 오름차순 정렬을 하는 것이 기본이다.// start 기준 오름차순 정렬Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]);// end 기준 오름차순 정렬Arrays.sort(intervals, (a,b) -..

1. DFS (깊이 우선 탐색)DFS는 그래프의 한 방향으로 깊이 들어가서 탐색을 마친 후, 돌아와서 다른 경로를 탐색하는 방식이다. Java에서는 주로 재귀 호출이나 스택 자료구조를 사용하여 구현한다.시간복잡도 : O(V+E) (V: 노드 수, E: 간선 수)DFS 예제 코드 (Java)import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set;public class GraphTraversal { private Map> graph; public GraphTraversal(Map> graph) { this.graph = graph; ..

dp란?문제를 작은 부분 문제들로 나누어 해결하고, 그 해답을 재활용하여 전체 문제를 해결하는 알고리즘.중복되는 부분문제, 최적 부분 구조 문제에 적용된다. 메모이제이션과 타뷸레이션 방식을 통해 시간 복잡도를 크게 줄일수 있다. dp를 구성하는 핵심 개념메모이제이션 (Memoization)주로 재귀 호출과 함께 사용필요한 부분 문제를 만나면 그때 계산하며, 계산된 결과는 캐시에 저장함.탑다운(Top-down) 방식이라고 부름. 메모리 사용량이 더 많을 수 있지만, 불필요한 부분은 계산하지 않기 때문에 효율적임각 부분 문제는 최대 한 번만 계산됨.타뷸레이션 (Tabulation)주로 반복문을 사용하여, 작은 문제부터 순차적으로 해답을 구해가는 방식모든 부분 문제를 미리 계산해 테이블에 저장함.바텀업(Bot..