본문 바로가기

Programming/데일리 알고리즘

 (34)
이진 탐색 Binary Search 탐색은 배열 형태로 주어진 데이터에서 원하는 값을 가진 데이터를 찾는 문제이다. 이진 탐색은 탐색의 대상이 되는 데이터가 정렬된 상태로 주어진 경우에 효과적으로 탐색을 수행할 수 있다. 배열에서 탐색키 X를 찾는 과정은 다음과 같다. 정렬된 배열에서 가운데 있는 원소와 탐색키 X를 비교하여 두 값이 같으면 원하는 키를 찾았으므로 탐색을 종료한다. 그렇지 않으면 배열은 가운데 원소를 기준으로 왼쪽과 ㄷ오른쪽의 두 개의 부분배열로 분할되는데, 만약 X가 가운데 원소보다 작으면 왼쪽 부분배열을 사용해서 이진 탐색을 다시 수행하고, X가 가운데 원소보다 크면 오른쪽 부분배열을 사용해서 이진탐색을 다시 수행한다. 이러한 과정을 순환적으로 수행하면 배열에서 X를 찾거나 이진 탐색의 대상이 되는 부분배열이 빈 배열이..
[HackerRank] Luck Balance (javascript) 그리디 알고리즘 문제 유형이다. 두 가지 조건에 맞게 내림차순한다. T[i]이 다를 경우 내림차순 T[i]이 같을 경우 L[i]을 내림차순 내림차순한 배열을 순회하며 더하는데, 진 경기일 경우에는 값을 뺀다. 진 경기는 다음 조건을 만족하는 경기이다. k { if (a[1] !== b[1]) { return b[1] - a[1]; } else { return b[0] - a[0]; } }); let answer = 0; for (let i = 0; i < contests.length; i++) { // 최소 k(인덱스로는 k-1번)만큼은 져야하므로, T[i]가 1이고 i가 k번째부터는 이기는 경기이다. if (k
[HackerRank] Minimum Swaps 2 (javascript) 선택 정렬 방식으로 풀었다. 배열의 0번부터 순회하며, 제일 작은 위치를 찾아 나의 위치와 교환한다. function minimumSwaps(arr) { let result = 0; const array = arr.slice(); let i = 0; for (let cur of array) { let j = i + 1; let min = cur; let pointer = i; while (j array[j]) { min = array[j]; pointer = j; } j++; } if (min !== cur) result++; array[i] = min; array[pointer] = cur; i += 1; } return result; }
[HackerRank] Special String Again (javascript) 총 3가지의 경우일 때 same character가 된다. 각각의 문자 1개 문자의 갯수가 1이 아닌 홀수이고, 가운데 문자만 다를 때 문자의 갯수가 짝수이고, 모두 같을 때 function substrCount(n, s) { const array = s.split(""); const stack = Array.from({ length: n }, () => 0); // 배열의 초기화시킨다. // 1, 2번을 체크한다. let sum = 0; let i = 0; while (i < n) { const char = array[i]; let count = 1; let j = i + 1; while (j < array.length && char === array[j]) { count++; j++; } stack[..
[HackerRank] Largest Rectangle (Javascript) 푸는 방법은 총 세가지이다. (참고) stack으로도 풀어봐야겠다. function largestRectangle(h) { // Write your code here const array = h.slice(); let max = Number.MIN_SAFE_INTEGER; for (let i = 0; i 0 && array[i - 1] >= poin..
(210519:BTB) Lesson 6. MaxProductOfThree 발생가능한 배열의 케이스는 총 3가지이고, 각각에 대하여 3가지 곱의 최댓값을 뽑는 방법은 아래와 같다. (오름차순으로 정렬되었다는 전제이다.) 1. 양수, 음수가 섞인 경우 - [-3, -2, 1, 2, 3] : 0~1번 인덱스의 숫자의 곱이 2~3번 인덱스의 숫자의 곱보다 크면, (0, 1, 4)번 인덱스 값의 곱이 답이다. - [-3, -2, 4, 5, 6] : 0~1번 인덱스의 숫자의 곱이 2~3번 인덱스의 숫자의 곱보다 작으면, 2~4번 인덱스의 숫자의 곱이 답이다. 2. 모두 양수일 경우 - [1, 2, 3, 4, 5] : 2~4번 인덱스의 숫자의 곱이 답이다. 3. 모두 음수일 경우 - [-5, -4, -3, -2, -1] : 2~4번 인덱스의 숫자의 곱이 답이다. 즉, 양수, 음수가 섞인 ..
(210519:BTB) Lesson 6. Distinct 유형 : 정렬 풀이 : Set 객체는 중복된 값을 허용하지 않는다는 것을 이용하여 풀 수 있다. function solution(A) { const array = A.slice(); let newSet = new Set(); for (let item of array) { newSet.add(item); } return newSet.size; } console.log(solution([2, 1, 1, 2, 3, 1]));
[HackerRank] Balanced Brackets (Javascript) 풀이 닫힘괄호(), }, ])가 들어왔을 때, stack에 마지막으로 들어있는 값을 확인한다. 마지막 값이 pair((, {, [)이면 pop한다. 아닌 경우는 모두 push한다. stack에 남은 원소 값이 있는 경우 NO를 반환한다. function isBalanced(s) { // Write your code here const array = s.split(""); let stack = []; for (let item of array) { if (item === "{" || item === "[" || item === "(") { stack.push(item); } else { // console.log(item, stack[stack.length - 1]); if (stack.length === ..

티스토리툴바