정렬과 그리디, 결정알고리즘(이분검색)
1. 선택정렬
선택정렬을 이용하여 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하기.
선택정렬은 우선 자리가 정해져있다. 첫 번째 자리에 가장 작은 녀석을 집어넣는다. 그리고 난 후에 두번째 자리에 그 다음 가장 작은 녀석을 선택해 집어넣는다. 이를 반복.
이중포문을 한다. i for문에서 idx라는 예비 지수를 설정하여 j로 이중 포문을 돌 때 arr[idx]와 arr[j]를 비교하여 가장 작은 값 j를 idx의 값으로 할당한 뒤, arr[idx]와 arr[i]의 값을 서로 바꾸는 로직
function solution(arr) {
let answer = arr;
for (let i = 0; i < arr.length - 1; i++) {
let idx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[idx]) idx = j;
}
[arr[i], arr[idx]] = [arr[idx], arr[i]];
}
return answer;
}
let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr)); //[5,7,11,13,15,23]
2. 버블 정렬
버블정렬을 이용하여 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하기.
✏️ 버블정렬 ? 이웃한 숫자를 바꾸어주는 방식. 이중포문. 선택정렬보다 더 많이 바꿈.(현재 배열 요소와 그 다음 배열 요소를 비교한다음 조건에 걸리면 교환하는 식의 정렬.)
function solution(arr) {
let answer = arr;
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1])
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 끝의 자리(큰수)부터 정해진다.
}
}
return answer;
}
let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr)); // [5,7,11,13,15,23]3. Special Sort (구글 인터뷰) (버블정렬 응용)
N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다.
음의 정수는 앞쪽에 양의정수는 뒷쪽에 있어야 한다. 또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다.
function solution(arr) {
// 나의 풀이
let answer = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < 0) answer.push(arr[i]);
}
for (let i = 0; i < arr.length; i++) {
if (arr[i] > 0) answer.push(arr[i]);
}
return answer;
}
선생님 풀이 - 버블정렬 활용
function solution(arr) {
let answer = arr;
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > 0 && arr[j + 1] < 0)
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
return answer;
}
let arr = [1, 2, 3, -3, -2, 5, 6, -6];
console.log(solution(arr)); // [-3, -2, -6, 1, 2, 3, 5, 6]4. 삽입정렬
삽입정렬을 이용하여 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하기.
✏️ 삽입정렬 ? 왼쪽에서 오른쪽으로 값을 계속 미는 로직으로 이중포문이다. i는 1 부터 끝까지, j는 i-1부터 0까지 돈다.
tmp라는 값을 알맞은 자리에 삽입하면 된다. tmp보다 큰 값은 하나하니씩 밀어버리고 tmp보다 작은 값을 만났을 때 그 뒷자리에 삽입하는 것.
function solution(arr) {
let answer = arr;
for (let i = 1; i < arr.length; i++) {
let tmp = arr[i],
j;
for (j = i - 1; j >= 0; j--) {
if (arr[j] > tmp) arr[j + 1] = arr[j];
else break;
}
arr[j + 1] = tmp; // j가 -1 이 되고 난 후 arr[0] 값 지정해주기
}
return answer;
}
let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr)); // [5,6,7,9,10,11]5. 카카오 캐시문제 변형
삽입 정렬 방식
만약 캐시의 사이즈가 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가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으
로 위치하게 된다. 5 2 3 1 6 ---> 3 5 2 1 6
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하기.
function solution(size, arr) {
let answer = Array.from({ length: size }, () => 0);
arr.forEach((x) => {
let pos = -1;
for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;
if (pos === -1) {
// 미스
for (let i = size - 1; i >= 1; i--) {
answer[i] = answer[i - 1]; //뒤로 값 땡기기
}
} else {
// 히트
for (let i = pos; i >= 1; i--) {
answer[i] = answer[i - 1];
}
}
answer[0] = x;
});
return answer;
}⭐️ 포인트 - 삽입할 값이 이미 배열에 존재할 경우 그 인덱스 값을 저장해줄 것!
// 내장 함수 이용하여 풀기
function solution(size, arr) {
let answer = [];
arr.forEach((x) => {
let pos = -1;
for (let i = 0; i < size; i++) if (x === answer[i]) pos = i;
if (pos === -1) {
answer.unshift(x);
if (answer.length > size) answer.pop(); // size 유지해주기
} else {
answer.splice(pos, 1);
answer.unshift(x);
}
});
return answer;
}
let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr)); //[7, 5, 3, 2, 6]6. 장난꾸러기 현수
오름차순으로 서야하는 데 두명이 자리를 바꾸었다. 바뀐 두 학생의 번호를 출력하는 프로그램
나의 풀이
function solution(arr) {
let answer = [];
let sortArr = arr.slice();
sortArr.sort((a, b) => a - b);
arr.forEach((x, i) => {
if (x !== sortArr[i]) answer.push(i + 1);
});
return answer;
}
let arr = [120, 125, 152, 130, 135, 135, 143, 127, 160];
let arr2 = [120, 130, 150, 150, 130, 150]; //[3,5]
console.log(solution(arr2)); // [3, 8]⭐️ 인자로 받은 배열을 오름차 순으로 정렬하여 서로 값이 다른 부분을 찾아 answer에 넣어주면 된다!
✔️ 참고) 코드 내의 arr.slice()는 깊은 복사를 한다. 얕은 복사이긴 한데 arr내에 기본형 데이터만 있으면 깊은 복사 된다. 하지만 arr내에 또다른 배열이 있으면 깊은 복사가 불가능하다.
7. 좌표 정렬
N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하기. 정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬한다.
//나의 풀이
function solution(arr) {
let answer = arr;
for (let i = 0; i < arr.length; i++) {
let idx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j][0] < arr[idx][0]) idx = j;
if (arr[j][0] === arr[idx][0]) {
if (arr[j][1] < arr[idx][1]) idx = j;
}
}
[arr[idx], arr[i]] = [arr[i], arr[idx]];
return answer;
}
}
//선생님 풀이 (sort 활용)
function solution(arr) {
let answer = arr;
answer.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
});
return answer;
}
let arr1 = [
[2, 7],
[1, 3],
[1, 2],
[2, 5],
[3, 6],
];
console.log(solution(arr1));
1 2
1 3
2 5
2 7
3 68.회의실 배정 (그리디문제)
회의 시작시간과 끝나는 시간을 담은 배열을 받는다. 각 회의가 겹치지 않으면서 회의실을 사용할 수 있는 최대수를 출력하는 프로그램 만들기. 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는시간) 이다.
✏️ 그리디 알고리즘? 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불린다. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘.
function solution(meeting) {
let answer = 0;
meeting.sort((a, b) => {
if (a[1] === b[1]) return a[0] - b[0];
else return a[1] - b[1];
});
let et = 0;
for (let x of meeting) {
if (x[0] >= et) {
answer++;
et = x[1]; // et에 끝나는 시간 넣어주기
}
}
return answer;
}
let arr = [
[1, 4],
[2, 3],
[3, 5],
[4, 6],
[5, 7],
]; //3
let arr2 = [
[3, 3],
[1, 3],
[2, 3],
]; //2
console.log(solution(arr));9. 결혼식 - 그리디 문제
사람들이 결혼식에 와서 떠나는 시간을 담은 배열의 묶음을 인자로 받는다.
동시간대에 존재하는 최대인원을 출력하는 프로그램 만들기
만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정한다.
function solution(times) {
let answer = 0;
let timeLine = [];
for (let x of times) {
timeLine.push([x[0], "s"]);
timeLine.push([x[1], "e"]);
}
timeLine.sort((a, b) => {
if (a[0] === b[0]) {
return a[1].charCodeAt() - b[1].charCodeAt();
} else {
return a[0] - b[0];
}
});
let cnt = 0;
for (let x of timeLine) {
if (x[1] === "s") cnt++;
else cnt--;
answer = Math.max(answer, cnt);
}
return answer;
}
let arr = [
[14, 18],
[12, 15],
[15, 20],
[20, 30],
[5, 14],
];
console.log(solution(arr)); //2⭐️ 시작시간과 끝나는 시간을 담은 새로운 배열을 만들어주어 풀어줄 수 있다.
10. 이분검색
✔️ 이분검색의 시간복잡도 : log(2)N (N이 8일경우 가장 큰 경우의 수 3)
⭐️ 이분검색 ? 가장 왼쪽에 있는 인덱스(lt)와 가장 오른쪽에 있는 인덱스(rt) 중간값(mid)이 target인지 확인한다. 이분검색은 반드시 정렬되어있어야 한다.
만약 target의 값보다 중간값이 크다면 rt = mid -1 로, 반대의 경우라면 lt = mid-1로 바꾸어 계속 mid값이 target과 동일한지 확인하는 로직.
이분 검색 활용 풀이
function solution(target, arr) {
let answer;
arr.sort((a, b) => a - b);
let lt = 0,
rt = arr.length - 1;
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (arr[mid] === target) {
answer = mid + 1;
break;
} else if (arr[mid] > target) rt = mid - 1;
else lt = mid + 1;
}
return answer;
}
나의 풀이
function solution(target, arr) {
let answer;
arr.sort((a, b) => a - b);
answer = arr.indexOf(target) + 1;
return answer;
}
let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr)); //3🚨 유의) break를 꼭 걸어주자. 안그러면 계속 반복됌
11. 뮤직비디오(결정 알고리즘)
총 N개의 노래들을 M개의 DVD로 나누어 모든 영상을 녹화하기로 하였다.
이때 N개의 노래 순서가 바뀌어서는 안된다. 이때 최소한의 용량 값을 출력하는 프로그램 만들기.
DVD개수와 N개의 노래들 순서대로 부른 곡의 길이를 인자로 받는다.
⭐️ 이분 검색을 이용한 lt(최소한의 용량)과 rt(최대한의 용량)의 중간값 탐색 . -> 최솟값과 최댓값의 중간값을 계속 보며, 끝날때까지 계속 좋은 답을 찾는다.
✏️결정 알고리즘? 이분검색을 기반으로 한다.
알고리즘 문제에서 주어진 조건에서의 최대값 혹은 최소값을 구하는 문제 중에 몇 몇 문제는 결정 알고리즘(Decision algorithm)을 활용해서 풀이해야 한다.
결정 알고리즘은 이분 검색을 기반으로 하는 문제로, 전체 데이터를 순회하면 시간 복잡도 O(N)을 갖지만 이분 검색으로 데이터를 검색하면 O(logN)만큼의 시간 복잡도를 갖는다.
답의 유효성 검사 함수 (제일 중요한 부분)
function count(songs, capacity) {
let sum = 0;
let cnt = 1;
for (let x of songs) {
if (sum + x <= capacity) sum += x;
else {
//노래 저장할 수 없는 경우
cnt++;
sum = x;
}
}
return cnt;
}
function solution(m, songs) {
let answer = Number.MAX_SAFE_INTEGER;
let lt = Math.max(...songs), //Math.min(songs) 로 쓰지 않기 유의! separate operator
rt = songs.reduce((a, b) => a + b, 0);
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(songs, mid) <= m) {
answer = mid;
rt = mid - 1;
} else lt = mid + 1;
}
return answer;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(solution(3, arr)); //1712. 마구간 정하기(결정 알고리즘)
말의 수와 마구간의 좌표을 인자로 받는다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하기
//말의 위치와 각 지표간의 차이
function count(stable, dist) {
let cnt = 1;
ep = stable[0];
for (let i = 1; i < stable.length; i++) {
if (stable[i] - ep >= dist) {
cnt++;
ep = stable[i];
}
}
return cnt;
}
function solution(c, stable) {
let answer;
stable.sort((a, b) => a - b);
let lt = 1; // stable[0]으로 하지 않음. 1과 최댓값 사이의 거리값을 구해야하기 때문.
let rt = stable[stable.length - 1];
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(stable, mid) >= c) {
answer = mid;
lt = mid + 1;
} else rt = mid - 1;
}
return answer;
}
let arr = [1, 2, 8, 4, 9];
console.log(solution(3, arr)); //3