📌 09 - 결혼식(그리디 알고리즘) 피로연 장소에 동시에 존재하는 최대 인원수를 구하는 문제이다. 한 친구가 오는 시간이 13, 가는 시간이 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정한다. 나의 풀이 방법 오는 시간(s)과 가는 시간(e)을 나누어 따로 배열을 만든 다음 오름차순 정렬을 한다. 투 포인터 알고리즘을 사용하여 p1이 p2보다 크거나 같으면 새로운 배열에 가는 시간(e)를 추가하고 p2++을 한다. p1이 p2보다 작다면 오는 시간(s)를 추가하고 p1++을 한다. for 문을 돌면서 's'가 나오면 cnt++을 해주고 'e'가 나오면 cnt--를 해준다. 피로연 장소에 들어오거나 나가는 사람이 발생할 때마다 피로연 장소에 존재하는..

📌 문제(정렬 알고리즘) 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 📝 풀이 const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); function solution(input) { let answer; const [size, ...arr] = input; // 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력 let newArr = [...new Set(arr)]; ..

📌 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;..