crabLab

📌강의 정리 해쉬, 슬라이딩윈도우, 투포인터 알고리즘의 종합선물세트같은 문제이다. 슬라이딩 윈도우를 b의 길이만큼 만들지만 투포인터 알고리즘을 써서 계속 a와b를 비교하며 a의 슬라이딩윈도우를 한칸씩 옆으로 옮긴다. 슬라이딩 윈도우를 만들때는 b의 길이 -1 을 해서 만들고 옮기면서 하나씩 더하고 빼주며 옮긴다. 비교할때는 해쉬를 사용하여 키,밸류 형태로 비교한다. 키, 밸류 형태로 비교할때는 size가 맞는지와 키는 있는지, 키 당 밸류의 개수가 맞는지를 비교한다. 📌느낀점 문제를 볼때 강의시간이 27분이라 정말 엄청 어려운 문제인줄 알았는데 생각보다는 할만했다. 물론 생각보다 할만했다는 거지 결코 쉽지는 않았다. 이 문제의 까다로운 점이 있다면 지금까지의 알고리즘들을 다 써야 할줄은 물론이고 그것들을..

📌강의 정리 이번에도 해쉬(맵)를 써서 알고리즘을 짠다. 처음 맵에는 str1의 값을 키에는 영문자를 밸류에는 그 개수를 누적으로 구해주고 그 다음에는 각각의 str1의 키값을 str2의 문자들로 비교하여 있으면 밸류를 -1해주고 없거나 그 개수가 0이 되었으면 answer를 NO로 바꿔준다. 📌느낀점 Map을 쓴 두번째 풀이였다. 솔직히 그냥 정렬 2번써서 비교하면 편하겠다라는 생각을 수도 없이 했지만 그러면 그냥 푸는 의미가 없으니 이 악물고 Map으로 풀었다. Map이 익숙하지 않아서 시간이 좀 걸렸고 심지어 풀이도 내가 for문 3개로 강사님 풀이보다 for문이 한 개 더 많다. 그 이유는 나는 map을 2개 만들고 그 둘을 다시 비교했지만 강사님은 하나만 만들고 그 안에서 증감하며 비교했기 때문..

📌강의 정리 해쉬라는 알고리즘을 쓸건데 js에서는 이 해쉬를 Map객체로 쉽게 표현할 수 있다. new Map() – 맵을 만듭니다. map.set(key, value) – key를 이용해 value를 저장합니다. map.get(key) – key에 해당하는 값을 반환합니다. key가 존재하지 않으면 undefined를 반환합니다. map.has(key) – key가 존재하면 true, 존재하지 않으면 false를 반환합니다. map.delete(key) – key에 해당하는 값을 삭제합니다. map.clear() – 맵 안의 모든 요소를 제거합니다. map.size – 요소의 개수를 반환합니다. 우리가 중복을 제거할때 썼던 객체는 여기서 key의 중복을 카운트하지 않는 Set객체이다. 이 맵을 이용하여..

📌강의 정리 슬라이딩 윈도우라는 알고리즘 기법을 사용할 것이다. 슬라이딩 윈도우란 반복에서 하나의 창문처럼 구간을 설정해 그 구간을 옆으로 쭉 밀며 계산을 하는 알고리즘 기법이다. 이 문제에서는 이중포문을 사용해 슬라이딩 윈도우를 구현하면 조건이 최대값들일때 100000*500 해서 어마어마한 숫자가 나올 수 있기에 포문을 하나만 이용해서 구현한다. 그럴 경우 핵심은 하나의 윈도우에서의 값이 나오면 다음 반복에서 단순히 앞의 값은 더하고 뒤의 값은 빼주는 것이다. 이렇게 하면 하나의 반복문으로 복잡도를 늘리지 않고 이 문제를 풀 수 있다. 📌느낀점 드디어 옛날에 풀었던 부분을 다시 다 풀고 새롭게 푸는 첫번째 문제이다. 처음시작할때는 이걸 언제 다 풀어 했는데 생각보다 훨씬 빠르게 다 풀었다.. 정말 매..

📌강의 정리 앞의 문제보다 조금 더 어렵다. lt, rt 두개의 포인터를 이용해서 풀어보자 lt=rt=0이기에 sum은 0이고 이제 lt는 가만히 rt는 오른쪽으로 증가해서 sum은 4가 된다. 새롭게 숫자가 추가되면 그 숫자를 포함한 연속부분수열을 구해야 한다. 3이 추가되면 3과 1,3을 구해야 한다. 그래야 중복을 회피하며 구할 수 있다. 그 다음으로 다시 1이 추가되면 1이 포함된 연속부분수열을 구해야 한다. 이런식으로 반복하면 되는데 그 수는 rt-lt+1을 하면 된다. sum이 m보다 커지면 lt가 증가하며(- -)sum을 구해준다. 즉, rt가 증가하면서도 구하고 lt가 빠지면서도 구해야한다. 추가되면 무조건 최소 한개는 있다. 이 문제의 핵심은 부분수열을 구해야하는 구간을 정해주고 그 구간..

📌강의 정리 투포인터 모르면 이중포문 쓸 것이다. 그러지 말자 이준포문이면 n^2알고리즘이 된다. 투포인터는 단일 포문으로 풀 수 있다. 포인터 변수는 lt,rt이다. lt는 가만히 있고 rt만 더해가며 M인지를 확인해간다. rt가 변하다 M을 넘으면 lt를 증가시켜 다시 확인하고 같아지면 다시 lt를 움직인다. rt가 증가하든 lt가 증가하든 6인지는 확인을 해야한다. 이렇게 알고리즘을 탐색하다가 rt가 끝나면 탐색이 끝난 것이다. rt는 for문돌릴때 기준으로 돌린다. 이제 코드로 알고리즘을 짜면 sum+=arr[rt]; 로 rt를 계속 더하게 한다. 이때 매순간 M과 같은지 if문을 통해서 짜준다. sum-=arr[lt++]; if(sum===m) answer++; 으로 같은지 확인을 하고 whil..

📌강의정리 이중포문을 이용해서 하면 되긴 하지만 투포인터를 배웠으니 투포인터를 해보자. arr1,2를 정렬한다. 정렬후 투포인터로 비교하며 같은경우를 push를 하는데 다른경우는 작은경우의 포인터를 증가시킨다. 작은값을 증가시켜야 나중에 같은값을 다시 매칭시킬 수 있지 큰 값을 증가시키면 반대편에 같은값이 있었을 수도 있다. arr1.sort()로 정렬해준다. while문으로 조건을 arr1,arr2가 그 배열의 길이보다 작을때로 맞춰주고 같은경우 push로 앤서값에 넣어주고 나머지는 else if , else로 포인터를 증가시켜준다. sort()는 배열을 문자열로 정렬하기때문에 우리가 원하는 숫자의 정렬이 안된다. 따라서 안에 함수를 새로 설정해주어서 우리가 원하는 방식으로 정렬되게해야한다. arr1...

📌강의 정리 문제 자체는 어렵지 않다. sort함수를 쓰기만 해도 nlog(n)이므로 시간복잡도가 높아진다. 하지만 투포인터를 쓰면 O(n+m)으로 끝낼 수 있다. 두 개의 포인터를 잡았다고 투포인터 알고리즘이다. answer라는 배열을 잡아서 계속 push를 하면 된다. 두 개의 arr1,2를 비교해서 작은 것을 앤서배열에 넣는다. arr1[p1] 과 arr2[p2]를 비교한다. 이때의 p1,p2가 포인터이다. 넣으면 포인터를 1 증가시킨다. 이렇게 계속 비교해서 한쪽이 끝나면 한쪽은 남으므로 그것을 그냥 다 집어넣으면 된다. n,m을 길이로 해놓고 p1,p2도 0으로 설정해 놓는다. while(p1