DFS를 구현하는 것은 크게 의미가 없는 것 같으므로 간단히 설명하고 넘어가자 하나의 노드에 대해, 해당 노드가 가진 child node를 완전히 탐색하고 넘어가는 것을 DFS이라고 한다 stack을 사용하여 노드의 순회를 컨트롤한다 속도는 느리지만, 저장 공간의 수요가 적고 구현이 간단하다는 장점이 있다. 특히 그래프를 search 할때는 root의 위치에 따라 preorder, inorder, postorder로 나뉜다 예시1. 230. Kth Smallest Element in a BST 다음과 같은 간단한 예시문제를 보자. 대표적인 그래프인 트리에 대한 문제이다. 트리를 방문하되, 크기순대로 세웠을때 k번째에 있는 노드의 value를 리턴하라는 문제이다. 일종의 inorder traversal 문..

Bianry Search는 오름차순(또는 내림차순)으로 정렬된 배열에서 특정 값을 찾는 방법이다 로직의 핵심은 middle point를 선정하는데 있다. 특정 value A를 찾아야 되는 경우, middle을 찾고 value가 middle point보다 작거나 큰지 검사한다 작다면 middle point 보다 큰 값들은 모두 대상에서 제외되는 것이다 이러한 방식으로 매번 반절씩 후보군을 줄여나갈 수 있다 기본적인 코드는 다음과 같다 left, right를 정해주고 Loop안에서 middle point를 지속적으로 바꿔주며 target을 찾는다 예시1. 33 Search in Rotated Sorted Array nums배열은 원래 오름차순이었지만 특정 기준에 따라 rotate되어있는 상태이다 기본적인 b..

용어는 Dynamic Program이지만 사실 핵심은 메모제이션에 있다. DP관련 문제 풀이들은 이전에 계산한 내용을 '기억'해두고 다음 계산에 지속적으로 이용한다. 일반적으로 풀이방식에 따라 bottem-up, top-down을 구분하는데 큰 의미는 없다고 생각한다. 트리처럼 recursion을 이용한 풀이는 보통 top-down으로, 배열에 대해 index 0부터 차근차근 풀어나가는 방식을 bottom-up으로 생각하는 경우가 많다 무튼 dp의 가장 간단한 예시는 피보나치 수열이다 피보나치 수열의 경우 모든 항목을 일일이 계산하지 않는다. f(1)을 한번 계산해두면, f(2)를 구할때 계산했던 f(1)을 메모제이션 했다가 사용한다. 결국은 일종의 점화식이다. 예시1- 416. Partition Equ..

특정 배열에 대해 범위 단위로 로직을 처리할 때 주로 사용되는 알고리즘이다. 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를 바꿔준다. 그것이 아니라면 범위를 그대로 푸쉬해주면된다.

무작위로 정렬되어 있는 정수를 원소로 가진 배열에 대해, 오름차순으로 정렬된 원소의 갯수를 구하라는 문제이다. DP와 Binary Search를 써서 풀 수 있는 문제 DP의 경우는 간단하다. nums의 길이만큼 1로 채운 dp 배열을 만든다 이때 dp [ i ]는 nums의 i번째 원소의 longest Increasing Subsquence이다. 원소가 하나만 들어오면 longest Increasing Subsquence는 1개이므로 초깃값은 모두 1로 설정한다 nums의 원소를 하나씩 Loop하면서 i보다 작은 j를 모두 검사한다. nums[ j ]가 nums[ i ]보다 작다면 오름차순으로 정렬이 되어 있다는 뜻이다. i보다 작은 j번째 원소를 기준으로 longest Increasing Subsqu..