본문 바로가기

inflearn78

[ 자바스크립트(JavaScript) ] section05 - 4 - 연속 부분수열2 📍 section05 - 4 - 연속 부분수열2 연속 부분수열1보다 약간 더 어려운 문제였다. 이전 문제는 다음 rt 포인터가 기준보다 커지면 arr[lt++]처리를 해줬는데, 이 문제는 특정 기준 값 이하인 경우 새로운 숫자가 포함된 연속 부분 수열을 구해주면 된다. 그럼 이전 숫자는 안 구하는지 궁금할 수 있는데, 이전 숫자가 끝에 있으면서 연속 수열인 값은 이전 과정에서 구했기 때문에, 새로운 경우의 수만 누적해주면 된다. 반복문을 따라 sum+=arr[rt]를 누적한다. 만약, sum>target이면 sum target) { sum -= arr[lt++]; } ans += rt - lt + 1; } return ans; } 2021. 8. 27.
[ 자바스크립트(JavaScript) ] section05 - 2 - 공통 원소 구하기 📍 section05 - 2 - 공통 원소 구하기 A, B 두 개의 집합이 주어질 때 공통 원소를 추출하여 오름차순으로 출력하는 문제다. 투 포인터를 사용해야 하는 이유는 N의 크기가 30,000인데, 이를 O(N^2)으로 풀게 되면 최악의 경우 1초당 9억번의 연산을 해야 하기 때문에 시간 초과가 난다. 따라서, O(N^2) 보다 작은 시간 복잡도로 계산해야 한다. 만약, N의 범위가 30,000보다 더 작다면 O(N^2)으로 bruteForce로도 풀 수 있다.bruteForce의 장점은 모든 경우의 수를 검사하기 때문에 정확한 결괏값이 나온다는 점이다. //O(N^2), bruteForce let n = 5; let arr1 = [1, 3, 9, 5, 2]; let m = 5; let arr2 = .. 2021. 8. 24.
[ 자바스크립트(JavaScript) ] section05 - 1 - 두 배열 합치기 📍 section05 - 1 - 두 배열 합치기 이번 섹션은 효율성을 고려하는 섹션으로 투 포인터, 슬라이딩윈도우, 해쉬를 사용하는 문제를 풀어본다. 오름차순으로 정렬된 배열을 합치는 문제인데, 저번에 병합 정렬(mergeSort) 연습하다가 이 문제와 비슷한 로직인 것 같아서 그대로 적용했다. 강사님 코드는 나의 코드와 조금 비슷하면서 달랐다. 또, 문제에서 n의 범위가 100까지기 때문에 시간 복잡도를 다항시간(O(N^2) 이상)내로 풀어도 되지만, 범위가 큰 경우를 대비해서 TwoPointer를 사용하여 O(N)으로 풀었다. 똑같이 풀 수 있는데 왜 twoPointer를 선택했냐고 묻는다면 만약, 실무에서 O(N^2) 코드와 O(N)코드가 있을 때 O(N)코드를 선택할 것임은 자명하다. 강사님은 후.. 2021. 8. 23.
[ 자바스크립트(JavaScript) ] section04 - 5 - K번째 큰 수 📍 33 - K번째 큰 수 100장의 카드 중 3장을 뽑는 모든 경우의 수는 100C3이므로 161,700이다. 여기서 3장을 뽑아 각 카드의 적힌 수를 합하려면 3 중반 복문으로 bruteForce로 모든 경우의 수를 돌려보면 된다. 이 문제의 시간복잡도는 다항 시간인 O(N^3)이지만 N=100일때 최대 1,000,000번 수행하므로 시간 초과에 걸리지 않는다. (보통 반복문을 돌 때 1초당 최대 10^8 (약 1억번) 돌 수 있으므로, N=100일때는 O(N^4)까지는 커버 가능하다.) 또, 강의에서는 3중 반복문의 i, j, k의 범위를 모두 n까지로 설정했는데, 맨 마지막에서 k가 n을 벗어나면 반복문에 들지 않고, 마찬가지로 j가 n의 범위를 벗어나도 반복문에 들지 않기 때문에 자동적으로 종료.. 2021. 8. 22.
[ 자바스크립트(JavaScript) ] section04 - 4 - 졸업선물 📍 section04 - 4 - 졸업선물(bruteForce) 상품을 최대한 많이 사야 하는 문제는 비용이 적게 드는 상품부터 포함하면 최대한 많이 살 수 있다는 점을 알고 이 문제를 풀자. 그리고 최대 몇 명의 학생들에게 사줄 수 있는지 보려면 경우의 수를 하나씩 따져가며 검사를 다 해야 하기 때문에 bruteForce를 이용하자. 이중 반복문을 돌면서 맨 처음 상품은 50% 할인 쿠폰을 사용하고 나머지 상품을 구매할 때는 그냥 더해주면 된다. 동일한 학생이 없으므로 i !== j인 조건을 추가하는 것도 잊지 말자. // 나의 코드 let n = 5; let m = 28; let cost = [[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]]; console.log(solutio.. 2021. 8. 22.

티스토리툴바