알고리즘

[알고리즘] 백준 11723번: 집합 (비트마스크) W_node.js

문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1..

[알고리즘] 부분 수열의 합 2

문제 N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 만약 N=5, M=5이고 수열이 다음과 같다면 1 3 1 2 3 합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지입니다. 풀이 function solution(m, arr){ let answer=0; let sum =0; let lt=0; for(let rt=0;rtm) { sum-=arr[lt++]; } //sum>m이 참일 때만 실행. sum에서 현재 lt 값을 빼주고 lt를 증감시킨다. sum>m이 거짓이 될 때까지. answer+..

[알고리즘]연속 부분 수열 1 - 투포인터 알고리즘

문제 N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 만약 N=8, M=6이고 수열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다. 입력예제 N=8, M=6 1 2 1 3 1 1 1 2 강사님의 풀이 function solution(m, arr){ let answer = 0; let sum = 0; let left = 0; //left, right 두개의 포인터로 시작, right는 for문 안에서 증감된다. for(let right = 0; right=m){ //sum이 m보다 크거나 같으면, ..

[알고리즘] 공통원소 구하기 - 투포인터 알고리즘

문제 A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요. (두 집합의 공통원소를 오름차순 정렬하여 출력합니다.) 입력예제 5 1 3 9 5 2 5 3 2 5 7 8 풀이 function solution2(arr1, arr2) { let answer = []; let n = arr1.length; let m = arr2.length; let p1 = 0; let p2 = 0; arr1.sort((a, b) => a - b); arr2.sort((a, b) => a - b); while (p1 < n && p2 < n) { if (arr1[p1] === arr2[p2]) { answer.push(arr1[p1++]); p2++; } else if (..

[알고리즘]k번째 큰 수

문제 현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요. 만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다. 풀이 function solution(n, k, card) { let answer; let set = new Set(); for (let i = 0; i < n - 2; i++) { for (let j = i + 1; j < n - 1; j++) { for (let s ..

[알고리즘]졸업선물 - sort 정렬, 완전탐색

문제 선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는 할인에 포함되지 않습니다. 입력예제 5 28 //학생수 예산 6 6 2 2 4 3 4 5 10 3 풀이 function solution(m, product) { let answer = 0; let n = product.length; product.sort((a, b) => a[0] + a[1] - (b[0..

[알고리즘]멘토링 - 완전탐색

문제 현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니다. 멘토링은 멘토(도와는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다. 선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다. 만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다. M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요. 입력예제 4 3 //학생수 N, 테스트 횟수 M 3 4 1 2 4 3 2 1 3 1 4 2 풀이 function solution(test) { let answer = 0; le..

[알고리즘]뒤집은 소수(소수 판별하기)

문제 n개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하세요. 풀이 function isPrime(num) { if (num === 1) return false; for (let i = 2; i

[알고리즘]자릿수의 합

문제 n개의 자연수가 입력되면, 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력. 단, 자릿수의 합이 같은 경우 원래 숫자가 큰 경우를 답으로 함. 풀이 1 function solution(n, arr) { let answer, max = Number.MIN_SAFE_INTEGER; for (let x of arr) { let sum = 0, tmp = x; while (tmp) { sum += tmp % 10; tmp = parseInt(tmp / 10); } if (sum > max) { max = sum; answer = x; } else if (sum === max) { if (x > answer) answer = x; } } return answer; } let arr = [1..

[알고리즘]문자열 압축

문제 알파벳 대문자로 이루어진 문자열을 입력받아 같은 문자가 연속으로 반복되는경우 반복되는 문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축하여 출력하세요! 풀이 function solution(s) { let answer = ''; let cnt = 1; for (let i = 0; i 1) answer += String(cnt); answer += s[i]; cnt = 1; } } return answer; } let str = 'KKHSSSSSSSE'; console.log(solution(str)); //K2HS7E