📌 08 - 회의실 배정(그리디 알고리즘) 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾는 문제이다. 단, 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 = endTime) { answer++; endTime = meeting[i][1]; } } return answer; } let arr = [ [3, 3], [1, 3], [2, 3], ]; console.log(solution(arr));

📌 07 - 좌표 정렬 N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 문제이다. 정렬 기준은 먼저 x값에 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬한다. 👍 풀이 방법 sort() 함수를 이용한다. 0번 인덱스는 x, 1번 인덱스는 y에 해당한다. x값이 같을 경우 y값에 의해 정렬하고 다를 경우 x값에 의해 정렬한다. 📝 풀이 function solution(arr) { let answer = arr; arr.sort((a, b) => { if (a[0] === b[0]) return a[1] - b[1]; else return a[0] - b[0]; }); return answer; } let arr = [ [2, 7], [1, 3], [1, 2], [2, 5..

📌 06 - 장난꾸러기 현수 현수와 짝꿍이 자리를 바꾼 반 학생들의 일렬로 서있는 키 정보가 주어질 때 현수가 받은 번호와 현수 짝꿍이 받은 번호를 차례대로 출력하는 문제이다. 나의 풀이 방법 (❌) 왜 틀렸을까❓ 반 학생들의 키 정보가 주어질 때 현수와 같은 키가 있는 경우 반례가 생긴다. for 문을 돌면서 i + 1 보다 i 가 큰 경우를 찾는다. i + 1이 현수가 받은 번호가 된다. 정렬을 한 후 indexOf() 함수를 이용해 원래 현수가 받아야하는 번호를 찾는다. 이 번호가 현수 짝꿍이 받은 번호이다. 👍 강사님 풀이 방법 배열을 복사하는 방법에는 여러가지가 있지만 여기에서는 Array.from(arr)과 arr.slice()를 소개해주고 있다. 단, 1 레벨(1차원 배열)에 대해서는 깊은 ..

📌 05 - Least Recently Used(카카오 캐시 문제 변형) 만약 캐시의 사이즈가 5이고 작업이 [2, 3, 1, 6, 7] 순으로 저장되어 있다고 가정해보자❗ 1) Cache Miss: 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작업을 CPU가 사용한다면 Cache Miss가 되고 모든 작업이 뒤로 밀린 후 5번 작업은 캐시의 맨 앞에 위치한다. [5, 2, 3, 1, 6] (7번 작업은 캐시에서 삭제된다.) 2) Cache Hit: 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용한다면 Cache Hit이 되고, 3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀린 후 3번 작업은 캐시의 맨 앞에 위치한다. [3, 5, 2, 1, 6..

📌 문제 N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 문제이다. 정렬하는 방법은 삽입 정렬이다. 🧐 삽입 정렬(insertion sort)이란 무엇일까❓ 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 요소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 📝 풀이 🧑🏻‍💻 나의 풀이 방법 function solution(arr) { const answer = []; for (let i = 0; i < arr.l..

📌 03 - Special Sort(구글 인터뷰) N개의 정수가 입력되면 입력된 값을 정렬하는 문제이다. 음의 정수는 앞쪽에 양의 정수는 뒷쪽에 있어야 한다. 또한 양의 정수와 음의 정수의 순서에는 변함이 없어야 한다. 👍 풀이 방법(강사님과 동일) 버블 정렬 문제의 응용으로 풀이 방법 또한 매우 비슷하다. 자료를 교환하는 조건만 바꾸면 된다. j를 돌때마다 서로 인접한 원소 중 앞쪽 원소 j가 양수이고, 뒤쪽 원소 j + 1이 음수이면 교환하면서 자료를 정렬한다. 1회전을 수행할 때마다 정렬이 확정되는 자료가 하나씩 늘어나므로 j가 도는 범위는 하나씩 줄어든다. 📝 풀이 function solution(arr) { // Shallow Copy let answer = arr; for (let i = 0;..

📌 문제 N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 문제이다. 정렬하는 방법은 버블 정렬이다. 🧐 버블 정렬(bubble sort)이란 무엇일까❓ 주어진 배열에서 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 인접한 2개의 요소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 구현이 매우 간단하지만 비효율적인 방법이다. 평균 시간복잡도 O(N^2) 📝 풀이 function solution(arr) { let answer = arr; // 1회전을 수행할 때마다 정렬이 확정되는 요소가 하나씩 증가 for (let i = 0; i < arr.length - 1; i++) { // j가 도는 범위는 하나씩 감소 for (let j = 0; j < arr.length - (1 + i)..

📌 문제 N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 문제이다. 정렬하는 방법은 선택 정렬이다. 🧐 선택 정렬이란 무엇일까? 제자리 정렬(in-place sorting) 알고리즘의 하나 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다. 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다. ... 이하 생략 과정 설명 주어진 배열 중에서 최솟값을 찾는다. 해당 값을 맨 처음에 위치한 값과 교체한다. 맨 처음 위치를 제외한 나머지 요소들을 같은 방법으로 교체한다. (배열의 길이 - 1) 만큼 위의 1 ~ ..