본문 바로가기

Algorithm137

[투포인터] 연속 부분수열 - (2) 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 N개의 수로 이루어진 수열이 주어진다. 이 수열에서 연속 부분 수열의 합이 특정 숫자 M 이하가 되는 경우가 몇 번 있는지 그 횟수를 세고 출력한다. 만약 1 3 1 2 3 의 수열이 주어지고 M=5라면 합이 5 이하가 되는 연속 부분 수열은 다음과 같다. {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1} 👉 입력 첫 번째 줄에 N과 M이 주어진다. 두 번째 줄에 N개의 원소를 가진 수열이 주어진다. 이때 각 원소들은 1000을 넘지 않는 자연수이다. 👈 출력 연속 부분 수열의 합이 M 이하가 되는 경우의 수를 출력한다. 📝 풀이 function solution(m.. 2021. 12. 17.
[투포인터] 연속 부분수열 - (1) 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 N개의 수로 이루어진 수열이 주어진다. 이 수열에서 연속 부분 수열의 합이 특정 숫자 M이 되는 경우가 몇 번 있는지 세고 그 횟수를 출력한다. 만약 1 2 1 3 1 1 1 2 의 수열이 주어지고 M=6이라면 합이 6이 되는 연속 부분 수열은 다음 세 가지가 된다. {2, 1, 3} {1, 3, 1, 1} {3, 1, 1, 1} 👉 입력 첫 번째 줄에 N과 M이 주어진다. 두 번째 줄에 N개의 원소를 가진 수열이 주어진다. 이때 각 원소들은 1000을 넘지 않는 자연수이다. 👈 출력 연속 부분 수열의 합이 M이 되는 경우의 수를 출력한다. 📝 풀이 function solution(m, arr) { let answer = 0; let.. 2021. 12. 16.
[프로그래머스] 문자열 압축 문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/60057 📋 문제 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede.. 2021. 12. 16.
[투포인터] 공통원소 구하기 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 두 개의 배열이 주어지면 주어진 배열들의 공통 원소를 추출하여 오름차순으로 출력한다. 👉 입력 첫 번째 줄에 첫 번째 배열의 크기 N이 주어진다. 두 번째 줄에 N개의 원소가 주어진다. 세 번째 줄에 두 번째 배열의 크기 M이 주어진다. 네 번째 줄에 M개의 원소가 주어진다. 이때 원소는 각 배열에 대해 중복이 없이 주어지며 N과 M은 1 이상 30,000 이하의 수를 가진다. 👈 출력 두 배열의 공통원소를 오름차순으로 정렬하여 출력한다. 📝 풀이 function solution(arr1, arr2) { let answer = []; let n = arr1.length; let m = arr2.length; let p1 = p2 = .. 2021. 12. 15.
[투포인터] 두 배열 합치기 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 오름차순으로 정렬이 된 두 배열이 주어지면 이 배열들을 오름차순으로 합쳐 출력한다. 👉 입력 첫 번째 줄에 첫 번째 배열의 크기 N이 주어진다. 두 번째 줄에 N개의 배열 원소가 주어진다. 세 번째 줄에 두 번째 배열의 크기 M이 주어진다. 네 번째 줄에 M개의 배열 원소가 주어진다. 이때 주어진 배열의 원소들은 오름차순으로 정렬되어 있으며 N과 M은 1 이상 100 이하의 값을 가진다. 👈 출력 오름차순으로 정렬된 배열을 출력한다. 💡 사용된 개념 투 포인터 알고리즘(Two Pointers) 리스트에 순차적으로 접근해야 할 때 2개의 pointer의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 투 포인터 알고리즘의 예시로 특정한.. 2021. 12. 15.
[완전탐색] K번째 큰 수 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 1부터 100 사이의 자연수가 적힌 N장의 카드가 있으며 이 카드는 같은 숫자의 카드가 여러장 존재할 수 있다. 이 중 3장을 뽑아 3장의 카드에 적힌 수의 합을 구한다. N장의 카드 중 3장을 뽑는 모든 경우의 수에 대해 그 합 중 K번째로 큰 수를 출력한다. 이때 중복되는 값은 제외한다. 👉 입력 카드의 갯수(N)와 K가 입력되고 N개의 카드값이 입력된다. 👈 출력 K번째 수를 출력한다. K번째 수가 존재하지 않으면 -1을 출력한다. 📝 풀이 function solution(n, k, card) { let answer = []; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; .. 2021. 12. 13.
[완전탐색] 졸업 선물 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 선생님은 학생들에게 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했다. 선생님은 상품 하나를 50% 할인된 가격(배송비 포함 X)으로 살 수 있는 쿠폰을 가지고 있으며 선생님이 가지고 있는 예산은 한정되어 있다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 가능한 최대 학생수를 출력한다. 👉 입력 첫 번째 줄에 학생수(N)과 예산(M)이 주어진다. 두 번째 줄부터 N줄에 걸쳐 학생들이 받고 싶은 상품의 가격과 배송비가 입력된다. 단, 상품 가격은 짝수로만 입력되며 최소한 1개 이상의 상품을 살 수 있는 예산이 주어진다. 👈 출력 현재 예산으로 선물할 수 있는 최대 학생 수를 출력한다. 📝 풀이 functi.. 2021. 12. 13.
[완전탐색] 멘토링 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 M번의 시험 결과 등수를 가지고 멘토와 멘티를 정한다. 만약 A학생이 멘토, B학생이 멘티가 되려면 A학생은 M번의 시험에서 모두 B학생보다 높은 등수를 얻어야 한다. M번의 시험 결과가 주어졌을 때 멘토, 멘티의 짝을 만들 수 있는 경우가 총 몇 가지인지 출력한다. 👉 입력 학생 수(N)와 테스트 수(M)가 주어지고 M개의 테스트 결과가 학생번호로 주어진다. 제일 앞에서부터 1, 2, 3, ..., N등의 순서이다. 만약 N=4이고 3, 1, 4, 2의 입력이 주어졌다면 3번 학생이 1등, 1번 학생이 2등, 4번 학생이 3등, 2번 학생이 4등이다. 👈 출력 멘토와 멘티의 짝을 만들 수 있는 경우의 수를 출력한다. 📝 풀이 fun.. 2021. 12. 13.
[완전탐색] 뒤집은 소수 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 N개의 자연수가 입력된다. 각 자연수를 뒤집은 후 그 수가 소수이면 뒤집힌 수를 출력한다. 예를 들어 32가 입력된다면 뒤집은 수 23은 소수이므로 23을 출력한다. 👉 입력 N개의 자연수가 입력된다. 👈 출력 소수를 입력된 순서대로 출력한다. 💡 사용된 개념 소수 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 먼저 소수의 정의를 가지고 구현한 소수를 판별하는 코드는 다음과 같다. function isPrime(num) { if (num === 1) return false; for (let i = 2; i < num; i++) { if (num % i === 0) return false.. 2021. 12. 13.

티스토리툴바