crabLab

📌강의 정리 이번에도 해쉬(맵)를 써서 알고리즘을 짠다. 처음 맵에는 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

📌강의 정리 3장을 뽑는 모든 경우는 10C3이 된다. 이 중 K번째로 큰수를 구하는 문제이다. set이라는 자료구조가 있다. 중복을 없애주는 자료구조이다. 이번에는 내림차순으로 정렬해야한다. 먼저 set자료구조를 만들어야 한다. new연산자를 통해 새로운 객체를 만들어준다. 삼중포문으로 모든 경우의 수를 다 구할수 있고 이때 두,세번째포문은 i+1, j+1 이런식으로 중복을 피해준다. 마지막 세번째 포문에서 tmp.add(card[i]+card[j]+card[k]); 해주면 중복을 피하면서 다 더할 수 있다. 또한 i포문의 범위를 n-2로해줘도 좀 더 정확한 표현이 가능하며 그냥 다 b - a); console.log(card); for (let i = 0; i b - a); console.log("f..

📌강의 정리 최대한 많은 학생에게 선물을 사줘야 하므로 선물 개수가 중요하다. 상품가격하고 배송비를 더한 값으로 정렬을 한다. 제일 비싼것을 할인 받는다고 반드시 많은 선물을 사는 것은 아니다. 그러므로 모든 경우를 다 봐야한다. 각 상품마다의 50퍼센트 할인을 받아 다 계산해본다. n은 문제에서의 학생수이다. 이제 정렬을 하는데 sort를 써서 ((a,b)⇒(a[0]+a[1])-(b[0]+b[1])); 을 하면 두 값을 더한 값의 오름차순으로 정렬된다. 이제 포문을 써서 i일때 할인을 받는것으로 한다. money 변수는 i값의 상품금액의절반과 배송비용을 총비용에서 뺀값이다. 이제 다시 포문을 돌려 i를 제외한 상품금액과 배송비용을 더한게 money보다 작아야한다. 그래야 뺄수가 있으므로 이제 money..

📌강의 정리 이 문제가 블루투포스 완전탐색을 쓰는 대표적인 문제이다. 하나하나의 경우를 전부다 확인해야한다. 앞을 멘토 뒤를 멘티로 한다. 총 경우의 수는 4*4로 16가지이다. i가 멘토 j가 멘티라고 가정하고 문제를 푼다. 각각의 테스트마다 하나하나 다 비교해야한다. 또한 포문 두개가 더 돈다 총 4중 포문이다. forfor ij 로 16번 다 돌면서 forfor sk로 하나씩 멘토멘티의 경우를 다 비교해본다. 그렇게 비교하며 예를들어 (3,1)이 맞는 멘토멘티인지 확인하려면 test[k][s] === i test[k][s] === j 를 하며 하나의 멘토 멘티 짝이 모든시험에서 다 통과하는지를 확인한다. 입력 배열을 test로 받고 m테스트갯수를 test.length로 3을 구한다. 학생수n은 te..