본문 바로가기

Algorithm54

[해시] 학급 회장 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 학급 회장 후보로 기호 A, B, C, D, E 후보가 등록했다. 학급 회장 투표는 학생들이 각 후보의 기호를 적어 내는 것으로 이루어진다. 이때 투표 결과가 발표되면 어떤 후보가 학급 회장으로 선출되었는지를 구하고 학급 회장의 기호를 출력한다. 👉 입력 첫 번째 줄에 반 학생 수 N이 주어진다. 두 번째 줄에 N개의 투표 용지에 쓰인 각 후보의 기호가 문자열로 주어진다. 이때 주어진 문자열은 문자 사이의 기호나 공백이 없다. 👈 출력 학급 회장으로 뽑힌 후보의 기호를 출력한다. 💡 사용된 개념 Hash 다양한 길이를 가진 데이터(key)를 고정된 길이를 가진 데이터로 매핑한 값이다. key를 매우 큰 값이라 가정했을 때 이 값을 자.. 2021. 12. 17.
[슬라이딩윈도우] 최대 매출 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 가게를 운영하는 현수 아빠는 현수에게 N일 간의 매출 기록을 주고 연속된 K일 간의 최대 매출액이 얼마인지 구하라고 했다. N개의 매출액이 주어졌을 때 연속된 K일 간의 최대 매출액을 구해 출력한다. 만약 10일간의 매출 기록이 12 15 11 20 25 10 20 19 13 15 로 주어졌고 K=3이라면 연속된 3일 간의 최대 매출액은 11 + 20 + 25 = 56 만원이다. 👉 입력 첫 번째 줄에 N과 K가 주어진다. N은 5 이상의 수를 가지며 K는 2 이상 N 이하의 수를 가진다. 두 번째 줄에 N개의 숫자가 주어진다. 이때 각 숫자는 0 이상, 500 이하의 정수이다. 👈 출력 연속된 K일 간의 최대 매출액을 출력한다. 💡.. 2021. 12. 17.
[투포인터] 연속 부분수열 - (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.

티스토리툴바