무작위로 정렬되어 있는 정수를 원소로 가진 배열에 대해, 오름차순으로 정렬된 원소의 갯수를 구하라는 문제이다. 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..

2차원 matrix가 주어질때, target이 있는지 찾아라. 이때 행렬별로 모두 오름차순으로 정렬되어있다 오름차순 배열에서 무언가를 찾으려면? binary search ㄱㄱ 간단한 문제였지만 2차원 배열도 binary search를 한번 적용해 본다는 의미로 기억할만한 문제

오름차순으로 정렬된 배열에 대해 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 문제대로 오름차순으로 정렬되어 있다면 그냥 쪼개면..

두번 나온 element 리턴하기 set을 이용하여 처음 나온 element는 add로 set에 넣고, 두번째 나온건 해당 element를 리턴하면 됨 왜 medium일까 궁금한 문제.. 나중에 바이너리 서치나 투포인터로도 풀어보자