최장증가 부분수열 - LIS(Longest Increasing Subsequendce) 주어진 수열에서 일부 원소를 골라내어 만든 부분 수열 중, 오름차순으로 정렬된 가장 긴 부분수열을 의미한다. 이때 핵심은 부분수열이 반드시 연속될 필요는 없다는 것이다. 즉 몇 개의 원소를 건너뛰어도 해당 연속으로 정렬만 되면 된다는 것이다. 예를 들어 {2, 3, 8, 6, 4, 5, 9, 1}의 경우 가장 긴 증가 부분수열은 {2, 3, 4, 5, 9}이 됨 특징부분수열의 각 원소는 원래 수열에서 순서를 지켜야 함, 연속적일 필요는 없음오름차순이므로 앞의 원소보다 뒤의 원소가 크거나 같아야 함한 수열에는 여러 개의 최장 증가 부분 수열이 존재할 수 있음 구하는 방법동적계획법 - DP각 인덱스에서 끝나느 LIS의 길..

이진 탐색(binary search) vs 투 포인터(two pointer)완전 탐색, 즉 브루트 포스로 문제를 풀어나가다 보면 어떤 문제는 시간 초과가 나는 경우가 생긴다. 이럴 경우 이진 탐색 혹은 투 포인터를 사용해서 문제를 풀이하였다. 둘 다 비슷한 방식으로 진행이 되기에 비슷한 알고리즘이라 생각하였다. 둘 다 변수를 통해 값의 이동 및 값의 탐색이기에 탐색의 시작 범위의 차이이지 시간 복잡도와 구성에는 별 차이가 없을 것이라고 생각하였다. 하지만 알고리즘을 공부하면서 알아보니 둘에게는 명확한 차이점이 존재하였다. 이진 탐색 이진 탐색이다. 이진 탐색은 좌,우 그리고 중간을 기준으로 탐색을 하는 알고리즘 기법이다. 이 기법은 처음(left), 끝(rigth), 중간(mid)을 가지고 진행을 하게 ..