Algorithm & 자료구조/(인프런) 자바스크립트 알고리즘 문제풀이

[알고리즘] 마구간 정하기

문제 N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ... , xN의 좌표를 가지며, 마구간 간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요. 풀이 const arr = [1, 2, 8, 4, 9]; const C = 3; function count(positions, distance) { // 말은 최소 하나 이상 들어갈 것이기 때문에 cnt 는 최소 1..

[알고리즘] 모든 아나그램 찾기

문제 S문자열에서 T문자열과 아나그램이 되는 S의 부분 문자열의 개수를 구하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 부분 문자열은 연속된 문자열이어야 합니다. 입력 : 두 문자열 S 와 T, T 문자열의 길이는 S문자열보다 작거나 같습니다. 출력 : S 단어에 T문자열과 아나그램이 되는 부분 문자열의 개수를 출력합니다. 풀이 이 문제는 슬라이딩 윈도우 알고리즘과 맵 객체를 활용하여 풀 수 있는 문제이다. T 와 S의 0부터 T.length - 1 까지의 문자열에 대해서 각 문자를 키로, 포함하고 있는 갯수를 밸류로 하는 맵 객체를 만든다. 두 개의 포인터로 T의 길이만큼 범위를 잡아서 S 문자열을 이동하며 T와 S 문자열의 일부분을 비교한다. T 길이 만큼 범위를 잡는다는 것은,..

[알고리즘] 최대매출

문제 현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출 기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다. 만약 N = 10이고 10일 간의 매출 기록이 아래와 같습니다. 이 때 k = 3 이면, 12 15 11 20 25 10 20 19 13 15 연속된 3일간의 최대 매출액은 11 + 20 + 25 = 56만원 입니다. 여러분이 현수를 도와주세요. 풀이 1번 풀이 // 1번째 시도한 코드 // : lt와 rt를 선언해서, rt를 증가하면서 더하고, // rt - lt 가 k - 1 보다 클 경우(index가 0부터 시작하므로 -1을 해줌) // sum 에서 lt를 빼면서 증가 // sum에 rt를 더하고 max 값과 비교하여 max를 갱신하여 리턴 fu..

[알고리즘] 연속 부분수열 2 (투포인터 알고리즘)

문제 N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속 부분수열의 합이 특정 숫자 M 이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 풀이 const M = 5; const arr = [1, 3, 1, 2, 3]; function solution1(M, arr) { const N = arr.length; let lt = 0; let count = 0; let sum = 0; for (let rt = 0; rt M) sum -= arr[lt++]; // 이..

[알고리즘] 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

문제 S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다. 입력설명 첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다. S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다. bacaAacba abc 풀이 function compareMaps(map1,map2){ // 두 map의 사이즈가 같은지 비교 if(!map1.size === map2.size) return false; // 두 map의 key, value 값이 같은지 확인 for(let [key,val] of map1){ if(!map2.has(key) || ..

[알고리즘] 순열구하기

문제 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 풀이 function solution(m, arr){ let answer = ''; const n = arr.length; const visited = new Array(n).fill(0); let tmp = new Array(m).fill(0); function DFS(L){ if(L===m){ answer+=`${tmp}\n`; } else{ for(let i = 0; i < n; i++){ if(visited[i]===0){ visited[i]=1; tmp[L]=arr[i]; DFS(L+1); visited[i]=0; } } } } DFS(0); return answer; } let arr =[3,..

[알고리즘] 중복순열 구하기

문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력 첫 번째 줄에 자연수 N(3

[알고리즘] 최대점수 구하기(DFS)

문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 입력설명 첫 번째 줄에 문제의 개수N(1

[알고리즘] 합이 같은 부분집합(DFS)

문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력설명 첫 번째 줄에 자연수 N(1=arr.length){ for(let i = 0; i0)cnt.push(tmp); } else{ visited[n]=1; DFS(n+..

[알고리즘] 아나그램 (해쉬)

문제 Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 강사님의 풀이 function solution(str1, str2){ let answer='YES'; let hash = new Map(); for(let x of str1){ if(has..