특정 배열에 대해 범위 단위로 로직을 처리할 때 주로 사용되는 알고리즘이다. pointer가 두개라는 점에서 Two-Pointers 알고리즘과 유사하지만, Two-Pointers알고리즘이 서로 독립적으로 움직이는 것과 달리 Sliding window 알고리즘은 포인터 두 개가 서로 동일하게 움직인다. 사실 내 생각에 두 알고리즘을 구분하는 것은 의미가 없어 보인다. 전체 element에 대해 Loop를 돌아야할 문제를, 포인터를 두 개 두고 element 하나씩 찍어가면서 돌면 two pointer고, range 단위로 비교하게 되면 sliding window라고 생각한다. 예컨데 대상배열(전체배열)과 비교 target인 기준배열이 있다면, left와 right라는 pointer 두 개를 두고, 순회가 ..

start와 end로 이루어진 interval의 배열이 input으로 들어올 때, 범위가 중복되는 값을 합쳐서 리턴하라 stack을 이용하여 풀이하였다 오름차순으로 정렬 후, stack에 interval[0]를 기준으로 넣어 둔다 interval[0][0]은 start, interval[0][1]은 end일 것이다. 이때 stack의 원소의 end보다(Loop가 돌면 마지막 원소와 비교하게 될 것) intervals의 start가 짧다면, 두개를 합친 배열로 stack의 end를 바꿔준다. 그것이 아니라면 범위를 그대로 푸쉬해주면된다.

board라는 2차원 배열로 매트릭스가 주어지고, word라는 글자가 sequential하게 이어질 수 있는지 여부를 리턴하는 문제 DFS를 하면서 해당하는 word가 나오면 하나씩 substring하는 방식으로 풀어보았다 일단 dfs함수는 board와 i,j라는 위치, 남은 word인 remain을 인자로 받는다. remain이 더이상 남아있지 않으면 true, 있으면 false를 리턴한다. 모든 요소에 대해 검사를 진행할것인데, 검사가 진행된 board는 - 로 바꿔준다 이후 해당 char에 인접한 동서남북을 각각 dfs하여 remain[0]이 없는 경우는 바로 false를 리턴해주고 나머지는 true로 진행한다.

오름차순으로 정렬된 배열에 대해 target이 주어지면, 이 타겟이 위치한 index의 시작과 끝을 구하라는 문제 binary search 문제다. 여기서 주의할 부분은 target이 2개이상이므로, target=mid일때 리턴하지 않고 mid까지 포함하여 범위를 자른다는 것이다. 기존의 binary search를 이용하면 range중 하나만 찾아낼 것이기 때문이다. 따라서 가장 먼저 등장하는 res[ 0 ]과 가장 나중에 등장하는 res [ 1 ]을 각각 구한다 res[0]의 경우는 다음과 같은 과정을 거친다. mid를 정하고 해당 로직처럼 범위를 좁혀나가면, r=mid, l=mid+1로 설정하므로 l이 해당 target의 첫번째 위치가 된다 res[1]의 경우는 다음과 같은 과정을 거친다. mid를 ..

임의의 pivot index에 의해 rotate된 배열에서 target이 몇번째 위치에 있는지 찾아라. 오름차순으로 정렬된 배열은 binary search로 해결하는 것이 일반적이다. start와 end index를 두고, endIndex가 클때까지 Loop를 돌린다 이 loop는 middle index를 구하고 target이 있다면 해당 값을 리턴하고, target이 더 크다면 startIndex를 우측 반으로, 더 작다면 endIndex를 좌측 반으로 설정한다. 이는 배열이 오름차순으로 정렬되어 있다는 전제하에 가능한 것이다 이 문제도 target이 있다면 리턴해주면 되는데, 문제는 target이 mid가 아닌 경우다 일반적인 binary search 문제대로 오름차순으로 정렬되어 있다면 그냥 쪼개면..

반드시 연속된 부분집합 중 원소들의 곱이 가장 큰 것을 찾아 그 값을 리턴하라 DP문제이고, min, max 배열을 만들어 Loop를 돌리면서 매 순간의 max를 찾아주면 된다. 좀 더 줄여보았다.