프론트엔드 개발자의 기록 공간

🚩 순열 구하기 📖 문제 설명 : N 개의 자연수 중 M 개를 뽑는 경우의 수 출력 중복은 제외되므로 한 번 뽑은 수는 뽑을 수 없다. 1,2 수 중 2개를 뽑을 때, [1,2], [2,1]의 경우만 가능하다. 💡 같은 수는 중복해서 뽑으면 안되므로 해당 수에 대한 사용 표시를 체크하는 배열을 사용한다. // 순열 구하기 (DFS) const permutation = [] function DFS(n, m, i, visited, arr) { if (arr.length >= m) { console.log(...arr) permutation.push(arr) return } for (let j = 0; j < n.length; j++) { if (visited[j] === 0) { visited[j] = 1 ..

🚩 중복 순열 구하기 📖 문제 설명 : 1부터 N까지 번호중 M번을 뽑는 경우의 수를 모두 출력 중복도 가능하므로 [1,1] , [2,2] 등의 중복 숫자도 가능하다. 💡 재귀를 이용한다. // 중복순열 구하기 (다중 for문과 재귀의 차이점) function DFS(n, m, i, arr) { // 모든 n 탐색 완료 if (i >= n || arr.length > m) { return } // n 만큼 조합 for (let j = 1; j = m) console.log(...arr) } // 다중 for문의 한계 : m값에 따라 이중for, 삼중for...조건이 바뀜 function forFn(n) { for (let i = 1; i

🚩 합이 같은 부분집합(DFS : 아마존 인터뷰) 📖 문제 설명 : N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하는지 판단 💡 배열의 전체 합을 이용한다. 두 개의 부분집합의 원소가 같다는 것은 결국 집합의 원소 총합이 하나의 부분 집합의 뺀 결과의 값이 부분 집합의 값과 같다는 것이다. 재귀 함수를 이용해서 각각의 요소를 포함하는 경우, 포함하지 않는 경우로 나누어 판단한다. let flag = false // 합이 같은지 판단 변수 function recursion(arr, i, sum, total) { if (flag) return if (i >= arr.length) { if (total - sum =..

🚩 마구간 정하기 문제 (이분탐색 활용) 📖 문제 설명 : N 개의 위치를 나타내는 마구간이 있고, C 마리의 말이 있을 때, 마구간에 말을 배치했을 때 가장 가까운 두 말의 거리의 최대를 구해라. 즉, 가장 넓은 간격으로 넣을 수 있는 최대 거리를 구하는 문제이다. (말끼리 넓게 떨어져 있을수록 좋다) 💡 마구간의 좌표는 고정이 아니므로 오름차순으로 정렬한다. 제일 첫 마구간에 첫 말을 집어넣고 이분 검색을 통해 나머지 말들을 차례로 넣으면서, 넣은 말의 수와 주어진 말의 수를 비교하면서 이분 탐색 범위를 조절하여 최댓값을 추출하면 된다. // 마구간 정하기 (결정 알고리즘) // O(nlogn) function solution(a, N) { let answer = 0 let maxDistance = ..

🚩 뮤직비디오 문제 (이분탐색 활용) 📖 문제 설명 : 레코드의 수와 각 노래들의 재생 시간이 주어질 때, 레코드에 적절히 배분하였을 때, 레코드가 필요한 최소 용량을 구하는 문제이다. 즉 레코드가 3개, 노래가 순서대로 5, 6, 7, 8분짜리가 있다고 했을 때, 최소 용량은 11이 필요하다. 5분, 6분의 노래가 하나의 레코드, 7,8분짜리가 각 하나의 레코드에 들어가는 경우가 최소 용량이기 때문. 💡 노래 리스트 중에 제일 긴 노래를 시작 지점, 노래 리스트의 총합을 끝 지점으로 두어 이분 탐색을 진행한다. 왜냐하면 노래 리스트들의 수 만큼 레코드가 있다고 했을 때, 한 개씩 사용해도 최소 용량은 제일 큰 노래이기 때문이다. 그리고 레코드가 하나 일때는 모든 노래가 담겨있기 때문이다. // 이분 탐..

🚩 결혼식 문제 (투포인트) 📖 문제 설명 : 결혼식에 참석하는 친구들의 도착 시간과 떠나는 시간이 제각각이다. 이때 최대로 겹치는 친구들의 시간을 구해라. (자세한 내용은 강의 및 문제지 참고) * A의 떠나는 시간과 B의 도착시간이 같을 경우 겹치는 시간에서 제외한다. 즉, 떠나는 시간 미 포함 💡 도착시간, 떠나는 시간 기준으로 각각 나누어서 정렬 후 투 포인트로 시간 판단 function solution(arr) { let answer = 0 let arrival = [] // 도착 시간 let exit = [] // 퇴장 시간 arr.forEach((element) => { arrival.push(element[0]) exit.push(element[1]) }) arrival.sort((a, b..

🚩 LRU 삽입 정렬 응용 📖 문제 설명 : 캐시의 개수와 작업의 개수가 주어질 때, LRU 알고리즘과 유사하게 작업을 할 수 있게 구성하면 된다. (자세한 내용은 강의 및 문제지 참고) 💡Tip. includes, indexOf 메소드 사용 // LRU 삽입 정렬 응용 (카카오 캐시 문제 변형) // O(n^2) function solution(S, arr) { let answer = [...arr] let cache = new Array(S).fill(0) answer.forEach((el) => { // Cache Miss if (!cache.includes(el)) { // 한 칸씩 뒤로 미룬 후 처음에 작업 삽입 for (let i = cache.length - 2; i >= 0; i--) { ..