커리어OT
오늘 오전 11시부터 간단하게 커리어 OT를 들었는데 커리어 담당이신 박신영 매니저님이 진행하셨다. 지피지기백전불태를 키워드로 회사에 대한 정보를 알아보는 방법에 대해서 알려주셨고 캐치, 원티드, 로켓펀치와 같이 어떤 사이트를 이용해야 하는 지 알 수 있어서 좋았다. 오티를 1시간 정도밖에 하지 않아서 금방 끝나고 점심을 먹고 오후에는 자료구조/알고리즘 수업을 진행하였다.
아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[그리디, 우선순위큐 문제]
그리디 -> 현재 상태에서 제일 좋은 것을 선택을 해나가는 것(반례가 있는 지 생각해보기!)
그리디가 안되면 동적 계획법!(Dynamic Programming)
동전교환
배열 형태로 동전이 주어지면 거스름돈을 가장 적은 수의 동전으로 교환할 때, 줄 동전의 최소개수를 구하여라.
📌 내가 푼 방법
X
📌 강사님 방법
function solution(nums, m) {
let answer = 0;
for(let i = nums.length-1; i>=0; i--) {
answer+=(parseInt(m/nums[i]));
m=m%nums[i];
}
return answer;
}
console.log(solution([1, 5, 10], 15));이 경우는 동전의 배수 관계이기 때문에 그리디를 쓰는 것이 맞음 -> 하지만 배수 관계가 아닌 입력에서 그리디 하면 안됨 (1, 5, 12), 15를 만들때 12 1 1 1이라 4개가 선택되는데(그리디) 반례가 5 5 5로 있음
이러한 경우는 다이나믹 프로그래밍으로 해결!
침몰하는 타이타닉
사람들의 몸무게가 배열 형태로 주어지고 구명 보트에 탈 수 있는 몸무게가 주어진다.
이때, 모든 사람들이 탈출하기 위한 구명보트의 최소개수는?
📌 내가 푼 방법
X
📌 강사님 방법
function solution(nums, m) {
let answer = 0;
nums.sort((a, b) => a - b);
let lt = 0;
let rt = nums.length - 1;
while (lt <= rt) {
if (nums[lt] + nums[rt] <= m) {
answer++;
lt++;
rt--;
} else {
answer++;
rt--;
}
}
return answer;
}
console.log(solution([90, 50, 70, 100, 60], 140));nums[lt] + nums[rt]를 이용해서 m보다 작은경우 카운팅 해주고 그렇지 않은 경우 무거운 사람 혼자만 타야하므로 rt만 줄여주면서 조절하면 된다.
while문에서 같다고 해주어야 가운데에 있는 값을 처리해주기 때문에 무조건 같다를 해주어야함!while(lt <= rt)
회의실 배정 // 그리디의 기본문제
2차원 배열 형태로 회의실의 시작시간과 끝나는 시간이 주어지는데 시작시간과 끝나는 시간이 같은 경우도 있음.
각 회의가 겹치지 않고 회의실을 사용할 수 있는 최대수의 회의를 찾아라!
📌 내가 푼 방법
function solution(meeting) {
let answer = [];
meeting.sort((a, b) => {
if (a[1] === b[1]) return a[0] - b[0];
else return a[1] - b[1];
}); // 정렬조건 중요!!!
for (let i = 0; i < meeting.length; i++) {
if (answer.length === 0) {
answer.push(meeting[i]);
}
if (answer[answer.length - 1][1] <= meeting[i][0]) {
answer.push(meeting[i]);
}
}
return answer.length;
}이렇게 하는 것 보다 아래의 방법으로 하는게 나은듯
📌 강사님 방법
function solution(meeting) {
let answer = [];
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];
}
}
return answer;
}
console.log(solution([
[1, 4],
[2, 3],
[3, 5],
[4, 6],
[5, 7]
]));
끝나는 시간을 기준으로 처리하는 것이 중요!!!!
그리디를 하는 이유 --> n^2을 안하기 위해!
그리디에서 정렬을 하더라도 O(nlogn)이 되기 때문에 이렇게 하는것이 좋음
js 에서 제공하는 기본 sort는 stable Sort임. 그래서 회의의 시작시간과 끝나는시간이 같은경우 sort할때 콜백으로 끝나는 시간이 같다면 시작시간이 더 빠른걸로 조건을 주어야함!!!!
만약 끝나는시간이 시작시간보다 같거나 작으면 그 값을 et에 x[1]로 저장하고 그 값을 가지고 다시 비교!if(x[0] >= et)
마지막 남은 수
N길이의 수열이 주어지는데 가장 큰 두개의 수를 뽑아 다음과 같은 행동을 한다.
- a==b이면 수열에서 제외
- a!=b이면 수열에서 제외하고 |a-b|가 수열에 추가
이런식으로 한 후 최종적으로 남는 수를 구하여라
📌 내가 푼 방법
X
📌 강사님 방법
class maxHeap {
constructor() {
this.heap = [];
this.heap.push(Number.MAX_SAFE_INTEGER);
}
insert(val) {
this.heap.push(val);
this.upheap(this.heap.length - 1);
}
upheap(pos) {
let tmp = this.heap[pos];
while (tmp > this.heap[parseInt(pos / 2)]) {
this.heap[pos] = this.heap[parseInt(pos / 2)];
pos = parseInt(pos / 2);
}
this.heap[pos] = tmp;
}
get() {
let res = this.heap[1];
if (this.heap.length === 2) {
return this.heap.pop();
}
this.heap[1] = this.heap.pop();
this.downheap(1, this.heap.length - 1);
return res;
}
downheap(pos, len) {
let tmp = this.heap[pos];
while (pos <= parseInt(len / 2)) {
let child = pos * 2;
if (child < len && this.heap[child] < this.heap[child + 1]) child++;
if (tmp >= this.heap[child]) break;
this.heap[pos] = this.heap[child];
pos = child;
}
this.heap[pos] = tmp;
}
size() {
return this.heap.length - 1;
}
show() {
for (let i = 1; i <= this.size(); i++) {
console.log(this.heap[i]);
}
}
}
function solution(nums) {
let answer;
let maxH = new maxHeap();
for (let x of nums) {
maxH.insert(x);
}
while (maxH.size() > 1) {
let a = maxH.get();
let b = maxH.get();
if (a !== b) {
maxH.insert(a - b);
}
}
if (maxH.size() === 0) answer = 0;
else answer = maxH.get();
return answer;
}
console.log(solution([7, 6, 3, 2, 4, 5, 1])); // 0
for문안에 sort하면 시간복잡도에서 걸림 O(nlogn)
maxheap을 사용해서 풀자! O(2logn)
// maxHeap --> 0번값 엄청 크게, 부모의 값이 항상 자식의 값보다 크다! 다만 부모와 자식의 값이 같을 수는 있음
// 1번값이 루트, 2번 3번이 1번의 자식요소
//부모 인덱스 x 2는 왼쪽 자식,부모 인덱스 x 2 + 1는 오른쪽 자식
// 자식에서 부모인덱스 찾으려고 할 떄 parseInt(자식인덱스/2)
수열의 높이 조정 (다음주 월요일에 하신다고함)
📌 내가 푼 방법
매번 정렬해서 맨왼쪽, 맨 오른쪽 증감
sort를 n번했을듯 --> O(nlogn)
📌 강사님 방법
일단 건너 뛰고 시간 남으면 풀이함
최대 수입 스케쥴 // 강사님 피셜 우선순위 큐 사용의 대표적인 문제라고함
📌 내가 푼 방법
X
📌 강사님 방법
class maxHeap {
constructor() {
this.heap = [];
this.heap.push(Number.MAX_SAFE_INTEGER);
}
insert(val) {
this.heap.push(val);
this.upheap(this.heap.length - 1);
}
upheap(pos) {
let tmp = this.heap[pos];
while (tmp > this.heap[parseInt(pos / 2)]) {
this.heap[pos] = this.heap[parseInt(pos / 2)];
pos = parseInt(pos / 2);
}
this.heap[pos] = tmp;
}
get() {
let res = this.heap[1];
if (this.heap.length === 2) {
return this.heap.pop();
}
this.heap[1] = this.heap.pop();
this.downheap(1, this.heap.length - 1);
return res;
}
downheap(pos, len) {
let tmp = this.heap[pos];
while (pos <= parseInt(len / 2)) {
let child = pos * 2;
if (child < len && this.heap[child] < this.heap[child + 1]) child++;
if (tmp >= this.heap[child]) break;
this.heap[pos] = this.heap[child];
pos = child;
}
this.heap[pos] = tmp;
}
size() {
return this.heap.length - 1;
}
show() {
for (let i = 1; i <= this.size(); i++) {
console.log(this.heap[i]);
}
}
}
function solution(nums, n) {
let answer = 0;
let maxH = new maxHeap();
nums.sort((a, b) => b[1] - a[1]);
let maxD = nums[0][1];
let i = 0;
for (let day = maxD; day >= 1; day--) {
for (; i < nums.length; i++) {
if (nums[i][1] < day) break;
maxH.insert(nums[i][0]);
}
if (maxH.size() > 0) {
answer += maxH.get();
}
}
return answer;
}
console.log(solution([
[50, 2],
[20, 1],
[40, 2],
[60, 3],
[30, 3],
[30, 1]
]));제일 긴 날짜부터 sort를 하여 계산하고, 우선 가장 긴 날에 할 수 있는 값들을 maxHeap에 넣고 get을 하면 가장 큰거 얻어옴 그 뒤로 짤은 날에 할 수 있는 값들을 넣고 다시 최대값 반환 시키기!
동전교환 : 이 문제는 풀지 마세요. 비교용도입니다.
입력: [1, 5, 12], 15
출력: 3
--> 이 문제는 앞의 문제와 다르게 동전의 종류가 배수 관계가 아니기 떄문에 그리디문제가 아닌 다이나믹 프로그래밍(동적 계획법으로 문제를 풀어야함! 그리디로 풀면 출력값이 4나옴
