crabLab

📌강의 정리 이분탐색을 하는 것은 두 말 사이의 거리이다. 말들을 탐색하는 것이 아니다. 따라서 mid값은 1+9/2 → 5이고 ep라는 변수를 따로 만들어서 제일 가까운 두 말의 거리가 5일때 그리고 3일때 이런식으로 해서 최대거리를 구한다. 📌느낀점 쓰면서도 내가 제대로 이해한건가 싶다… 결정알고리즘은 한번으로 끝날 알고리즘이 아닌 것 같다. 우선 앞으로 나올 알고리즘들은 각 테마가 있고 그 테마들의 대표격인 문제들을 외워서 응용하든지 해야겠다. 마치 옛날에 수학풀때 매우 어려운 심화과정 문제들을 푸는 느낌이다. 이제부터는 전략을 다시 짤 필요가 있다. 아직 내 수준에서는 이제부터 나올 문제들을 완벽하게 풀어낼 수 없다. //나의 코드 //강사님 코드

📌강의 정리 이분 탐색의 범위는 주어진 배열이 아닌 DVD의 용량크기이다. 따라서 최소 9에서부터 최대 45까지에서 음악이 나누어지는게 가능할때 mid값을 구해야한다. 처음 mid는 lt + rt / 2 이고 그걸 전체 노래목록에서 하나씩 더하면서 mid보다 커질때 cnt를 ++하고 sum에는 x를 넣어주어 sum을 초기화하고 다시 더해간다. 그러면 mid 값에서의 dvd개수가 나오고 그게 주어진 음반보다 작으면 우선 answer에 할당시켜준뒤 다시 이분탐색을 해서 count해준게 주어진 dvd개수보다 작거나 같은지 작거나 같다면 answer를 그 mid값으로 업데이트한다. 이후 rt값을 mid -1로 바꿔준다. 그렇지 않다면 lt값을 mid + 1로 바꿔준다. 해주고 lt가 rt보다 커지면 반복을 멈추..

📌강의 정리 오름차순 정렬 이후에 이분탐색을 이용하여 타겟을 찾는다. 이분탐색은 while, lt, rt, mid를 이용한다. lt가 rt보다 커지면 반복을 종료하고, 반복내에서는 arr[mid]가 타겟과 같으면 answer = mid+1하고 break한다. 아닌경우 mid가 타겟보다 작으면 rt는 mid - 1, mid가 타겟보다 크면 lt는 mid + 1을 해서 반복한다. 📌느낀점 알고리즘은 진짜 넓게 배울필요도 있는 것 같다. 이분탐색을 알고는 있었지만 처음 구현해보는데 내가 푼 풀이도 가능은 하지만 강사님의 풀이가 훨씬 직관적이고 깔끔하다. lt와 rt를 생각하지못했다.. 항상 사고의 확장을 조금 더 신경써보자. //나의 코드 //강사님 코드

📌강의 정리 그리디의 또 다른 대표적인 문제이다. 주어진 배열의 온 시간을 새로운 배열의 0인덱스, ‘s’를 1인덱스에 주어진 배열의 간 시간을 새로운 배열의 0인덱스, ‘e’를 1인덱스에 넣어 온시간 간시간들로 이루어진 원래 길이의 두배에 달하는 배열을 새로 만든다.(1인덱스가 s 또는 e인) 이후 이 배열을 오름차순으로 정렬하되 같은 시간이면 1인덱스가 e인애가 먼저오게 아스키코드를 사용하여 정렬한다. 이후 다시 반복을 하여 s이면 cnt++하고 e이면 cnt— 하여 answer와 비교하며 최대값을 측정한다. 📌느낀점 처음으로 손도 못댄 문제이다… 시간을 딱 30분으로 한정했기에 그럴 수도 있지만 시간이 더 주어졌어도 장담할 수 없다.. 문제를 풀때는 이거 따로따로 다 측정하면서 계산해야 하나 라는 ..

📌강의 정리 회의 시작시간과 회의의 진행시간을 기준으로 정렬하면 최대 횟수를 구하는 데 반례들이 있기 때문에 회의가 끝나는 시간을 기준으로 정렬한다. 이때 회의의 끝나는 시간이 같은 경우의 회의들은 회의의 시작시간이 빠른 순서로 정렬한다. 정렬이 끝나면 반복을 하되 매 반복마다 et변수에 끝나는 시간을 넣어 시작시간이 et보다 큰경우에만 answer++을 한다.(처음 et는 0) 📌느낀점 정말 오랜만에 알고리즘에게 제대로 당한 문제였다. 그만큼 얻어갈게 많은 아주 좋은 문제였다고 생각한다. 우선 나는 회의 시작시간과 진행시간으로는 정렬할 생각을 했는데 끝나는 시간으로는 정렬할 생각을 하지 못했다. 그것이 이 알고리즘을 제대로 풀지 못한 제일 큰 이유인데 해결방법으로는 역시 손코딩으로 종이에 알고리즘을 그..

📌강의 정리 주어진 2차원 배열을 sort로 정렬하되 x좌표가 같을 때를 대비해 if로 x좌표가 같은경우 y좌표를 비교하여 return하게 알고리즘을 짠다. 📌느낀점 내가 푼 방식은 우연히 정답이 나올뿐 틀린 답이다. 강의시간이 3분인걸 보고 방심했다.. 좀 더 공들이자. //나의 코드 //강사님 코드

📌강의 정리 주어진 배열을 정렬한 배열을 새로만들고, 만든 배열과 처음 배열을 비교해 다른 숫자의 인덱스들을 answer에 push한다. 📌느낀점 내가 그동안 정렬에 너무 심취해 있었나보다.. 나의 풀이가 시간복잡도는 조금 더 좋지만 더 복잡하다. 간단하게 풀 수 있고 별다른 조건이없다면 간결하고 직관적인 풀이를 생각해보자. //나의 코드 //강사님 코드

📌강의 정리 캐시의 사이즈에 하나씩 최신 값들을 배열의 제일 앞으로 넣되 넣기전에 배열에 그 값이 있으면 그 값을 splice로 자르고 unshift로 넣는다. 또한 배열의 사이즈가 5를 넘으면 하나씩 pop()해준다. 📌느낀점 분명 같은 방식인데 좀 다르다.. 원인은 나는 splice를 안쓰고 진짜 반복문을 써서 순수하게 삽입정렬을 구현했기 때문이다. 문제를 구현해낸건 맞긴하지만 복잡도 측면에서 손해를 보기 때문에 간단한 메서드를 응용하는 법을 항상 연습해야 한다. //나의 코드 //강사님 코드

📌강의 정리 i=1부터 시작해서 먼저 i에 해당하는 값을 tmp에 저장해두고 두번째 반복을 하면서 j랑 비교해서 j보다 작으면 j값을 j+1로 복사해준다. j보다 작지 않으면 tmp값을 j+1값에 넣어준다. 📌느낀점 같은 삽입 정렬이지만 풀이방식이 나랑 강사님이 조금 달랐다. 나는 버블정렬과 비슷하게 풀었고 강사님은 삽입정렬스럽게 푼 것 같다. 버블 정렬과 삽입정렬의 차이는 버블은 무조건 n^2을 하는데 반면 삽입정렬은 베스트 케이스에 n만 할 수도 있다. //나의 코드 //강사님 코드

📌강의 정리 한 가지의 방법은 반복을 두 번 하는데, 첫번째 반복에서는 음수만 answer에 push하고 그 다음반복에는 양수만 answer에 push하는 것이다. 하지만 정렬의 정의에는 해당하지 않으므로 버블정렬을 사용하면 반복하며 앞과 뒤만 비교해서 양수, 음수면 바꾸고 양수양수, 음수음수면 가만히둔다. 📌느낀점 처음부터 뭔가 이상하긴 했다. 내가 본 문제제목에는 버블정렬응용이란 말이 없었는데… 알았다면 조금 쉬웠겠지만 만약 내가 진짜 구글인터뷰를 한다면 거기서 버블정렬응용하란 말은 안했을테니 같은 상황인 것 같다. 결국 나는 공간복잡도를 2개 늘리면서 정렬의 의미와는 멀어졌다. 이건 문제를 푼게 아니다… 다음에는 정렬에 맞게 풀어볼 수 있도록 하자. //나의 코드 //강사님 코드