tech
DataStructure & Algorithm
Siyoon Jeon
2021. 6. 11. 12:06
Implementation Stack
Stack 구현을 위한 기본적인 코드가 작성되어 있습니다. Stack 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
맴버 변수
- 데이터를 저장할 Object 타입의 storage
- 스택의 가장 상단을 가리키는 Number 타입의 포인터 top
메서드
- size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
- push(): 스택에 데이터를 추가할 수 있어야 합니다.
- pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
주의사항
- 내장 객체 Array.prototype에 정의된 메서드는 사용하면 안됩니다.
- 포인터 변수 top의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 0으로 하여 데이터가 추가될 위치를 가리키도록 합니다.
사용 예시
const stack = new Stack(); stack.size(); // 0 for(let i = 1; i < 10; i++) { stack.push(i); } stack.pop(); // 9 stack.pop(); // 8 stack.size(); // 7 stack.push(8); stack.size(); // 8 ...
//! 01_[Stack] 구현
class Stack {
constructor() {
this.storage = {};
this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
}
size() {
return this.top;
}
// 스택에 데이터를 추가 할 수 있어야 합니다.
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.top === 0) {
return;
}
const result = this.storage[this.top -1];
delete this.storage[this.top-1];
this.top -= 1;
return result;
}
}
//레퍼런스
class Stack {
//stack constructor를 생성합니다.
constructor() {
this.storage = {};
this.top = 0;
}
// stack의 사이즈를 구합니다.
// this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로 size를 구할 수 있습니다.
// this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 0부터 1씩 증감하며 표현하기 때문에 전체 요소의 개수를 나타낼 수 있습니다
size() {
return this.top;
}
//stack에 element를 추가합니다.
//새롭게 추가될 요소의 인덱스를 나타내는 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.this.top은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
push(element) {
this.storage[this.top] = element;
this.top += 1;
}
// stack에서 element를 제거한 뒤 해당 element를 반환합니다.
// 만약 size가 0이라면 아무 일도 일어나지 않습니다.
// top-1로 최상단을 설정한 후 변수에 저장하고, 스택에서 삭제합니다.
// 하나를 제거했으니 top도 감소합니다.
pop() {
if (this.size() <= 0) {
return;
}
const result = this.storage[this.top - 1];
delete this.storage[this.top - 1];
this.top -= 1;
return result;
}
}Implementation Queue
Queue 구현을 위한 기본적인 코드가 작성되어 있습니다. Queue 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
맴버 변수
- 데이터를 저장할 Object 타입의 storage
- 큐의 가장 앞을 가리키는 Number 타입의 포인터 front
- 큐의 가장 뒤를 가리키는 Number 타입의 포인터 rear
메서드
- size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
- enqueue(): 큐에 데이터를 추가할 수 있어야 합니다.
- dequeue(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
주의사항
- 내장 객체 Array.prototype에 정의된 메서드는 사용하면 안됩니다.
- 포인터 변수 front, rear의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 0으로 합니다.
사용 예시
const queue = new Queue(); queue.size(); // 0 for(let i = 1; i < 10; i++) { queue.enqueue(i); } queue.dequeue(); // 1 queue.dequeue(); // 2 queue.size(); // 7 queue.enqueue(10); queue.size(); // 8 queue.dequeue(); // 3 queue.dequeue(); // 4 queue.size(); // 6 ...
//02_[Queue] 구현
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return this.rear-this.front;
}
// 큐에 데이터를 추가 할 수 있어야 합니다.
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.rear-this.front === 0) { //this.size() 사이즈 메소드 사용 방법
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}
//레퍼런스
class Queue {
//가장 앞에 있는 요소를 front,
//가장 뒤에 있는 요소를 rear 라고 했을 때
//queue constructor 생성
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
// queue의 사이즈를 구합니다.
// queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있습니다.
size() {
return this.rear - this.front;
}
// queue에 element를 추가합니다.
// 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
// 만약 size가 0이라면 아무 일도 일어나지 않습니다.
// this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
dequeue() {
if (this.size() === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}브라우저 뒤로 가기 앞으로 가기
문제
개발자가 되고 싶은 김코딩은 자료구조를 공부하고 있습니다. 인터넷 브라우저를 통해 스택에 대한 검색을 하면서 다양한 페이지에 접속하게 되었는데 "뒤로 가기", "앞으로 가기"를 반복하면서 여러 페이지를 참고하고 있었습니다. 그런데 새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었습니다. 이러기를 반복하다가 김코딩은 스택 자료구조를 떠올리게 되었습니다.
브라우저에서 "뒤로 가기", "앞으로 가기" 기능이 어떻게 구현되는지 궁금해진 김코딩은 몇 가지 조건을 아래와 같이 작성하였지만 막상 코드를 작성하지 못하고 있습니다.
조건
- 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
- 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
- 앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.
- 브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않습니다.
인터넷 브라우저에서 행동한 순서가 들어있는 배열 actions와 시작 페이지 start가 주어질 때 마지막에 접속해 있는 페이지와 방문했던 페이지들이 담긴 스택을 반환하는 솔루션을 만들어 김코딩의 궁금증을 풀어주세요.
입력
인자 1: actions
- String과 Number 타입을 요소로 갖는 브라우저에서 행동한 순서를 차례대로 나열한 배열
인자 2: start
- String 타입의 시작 페이지를 나타내는 현재 접속해 있는 대문자 알파벳
출력
- Array 타입을 리턴해야 합니다.
주의사항
- 새로운 페이지 접속은 알파벳 대문자로 표기합니다.
- 뒤로 가기 버튼을 누른 행동은 -1로 표기합니다.
- 앞으로 가기 버튼을 누른 행동은 1로 표기합니다.
- 다음 방문할 페이지는 항상 현재 페이지와 다른 페이지로 접속합니다.
- 방문한 페이지의 개수는 100개 이하입니다.
- 반환되는 출력값 배열의 첫 번째 요소 prev 스택, 세 번째 요소 next 스택은 배열입니다. 스택을 사용자 정의한다면 출력에서는 배열로 변환해야 합니다.
입출력 예시
let actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1]; let start = "A"; let output = browserStack(actions, start); console.log(output); // [["A"], "B", ["A", "D"]] actions = ["B", -1, "B", "A", "C", -1, -1, "D", -1, 1, "E", -1, -1, 1]; output = browserStack(actions, start); console.log(output); // [ ["A", "B"], "D", ["E"]]
//03_[Stack] 브라우저 뒤로가기 앞으로가기
function browserStack(actions, start) {
// TODO: 여기에 코드를 작성합니다.
let prevPage = [];
let nextPage = [];
let currPage = start;
let result = [];
for(let i=0; i<actions.length; i++) {
// 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
// actions => 새로운 페이지,-1,1
if(typeof actions[i] === 'string') {
prevPage.push(currPage)
nextPage = [];
currPage = actions[i]
}
// 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고
// prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
else if (actions[i] === -1 && prevPage.length !== 0) {
nextPage.push(currPage)
currPage = prevPage[prevPage.length-1]
prevPage.pop()
}
//앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고
//next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.
else if (actions[i] === 1 && nextPage.length !== 0) {
prevPage.push(currPage)
currPage = nextPage[nextPage.length-1]
nextPage.pop()
}
//브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는
//스택에 push 하지 않습니다. prevPage.length !== 0 && nextPage.length !== 0
}
result.push(prevPage, currPage, nextPage)
return result;
}
//레퍼런스
function browserStack(actions, start) {
// 뒤로 가기와 앞으로 가기 스택의 변수를 설정합니다
let prevStack = [];
let nextStack = [];
let current = start;
// actions 배열을 전부 탐색하기 위해 반복문을 설정합니다.
for(let i = 0; i < actions.length; i++) {
// 만약 actions 배열의 요소가 -1이고(뒤로가기를 눌렀고), prevStack의 길이가 0이 아닐 때(이전으로 돌아가는 페이지가 있다면)
if(actions[i] === -1 && prevStack.length !== 0) {
// prevStack에서 pop한 요소를 prevPage로 할당합니다.
// nextStack에 current를 삽입합니다.
// current를 prevPage에 할당합니다.
let prevPage = prevStack.pop();
nextStack.push(current);
current = prevPage;
// 만약 actions 배열의 요소가 1이고(앞으로가기를 눌렀고), nextStack의 길이가 0이 아닐 때(다음으로 넘어가는 페이지가 있다면)
} else if(actions[i] === 1 && nextStack.length !== 0) {
// nextStack에서 pop한 요소를 nextPage로 할당합니다.
// prevStack에 current를 삽입합니다.
// current를 nextPage에 할당합니다.
let nextPage = nextStack.pop();
prevStack.push(current);
current = nextPage;
// 만약 actions 배열의 요소가 알파벳이라면 (새로운 페이지라면)
} else {
// prevStack에 current를 삽입합니다.
// current에 현재 알파벳 요소를 할당합니다.
// 새로운 페이지는 앞으로 갈 수 없기 때문에 nextStack을 비웁니다.
prevStack.push(current);
current = actions[i];
nextStack = [];
}
}
// 배열에 prevStack, current, nextStack을 순서대로 담아 반환합니다.
return [prevStack, current, nextStack];
}동화책 출간
문제
동화책 전문 회사 동화스테이츠의 출간팀은 동화책 출간 작업을 하고 있습니다. 각 동화책 출간 진도가 100%일 때 출간할 수 있습니다. 각 동화책 출간 담당자는 다르며, 담당자의 업무 속도도 다르기 때문에 커리큘럼 순서 상 뒤에 있는 책이 앞에 있는 책보다 먼저 출간이 완료될 수 있습니다. 이때, 뒤에 있는 책은 앞에 있는 책이 출간될 때 함께 출간됩니다.
[예시]
- 개선 작업이 30% 진행된 책을 하루에 20% 작업할 수 있는 담당자가 맡을 경우 3일간 작업 후 4일째 출간할 수 있고 50% 작업할 수 있는 다른 담당자가 맡을 경우에는 2일째 출간할 수 있습니다.
- 개선 작업이 95% 진행된 책을 하루에 1% 작업할 수 있는 담당자가 맡고 30% 진행된 다음 책을 하루에 30% 작업할 수 있는 다른 담당자가 맡는다면 5일째에 두 개 책이 출간됩니다.
- 며칠 째에 출간하는 건 아무런 상관이 없습니다. 다만, 그날에 몇 개가 출간되는지는 아주 중요합니다.
- 4일째에 출간할 수 있는 책이 0 번째에 있고, 2일째에 출간할 수 있는 책이 1 번째에 있다면 4일 하루동안 출간할 수 있는 책은 2권입니다.
커리큘럼 상 먼저 배포되어야 하는 순서대로 동화책 출간 진도가 나열된 배열 books와 각 동화책 출간 담당자의 업무 속도가 나열된 배열 speeds가 주어질 때 한 번에 몇 개의 책이 배포될 수 있는지를 반환하는 improveBook 함수를 완성해 주세요.
입력
인자 1:books
- Number 타입을 요소로 갖는 '퍼센트' 단위의 동화책 출간의 현재 진도가 나열된 배열
인자 2: speeds
- Number 타입을 요소로 갖는 '퍼센트' 단위의 동화책 출간 담당자의 '하루'에 작업할 수 있는 업무 속도가 나열된 배열
출력
- Array 타입을 리턴해야 합니다.
- 모든 스프린트가 배포되는 날까지, 배포가 가능한 날에 배포될 수 있는 스프린트 수를 나열한 배열
주의사항
- 동화책 출간 진도는 100 미만의 자연수입니다.
- 담당자 업무 속도는 100 이하의 자연수 입니다.
- 개선해야 하는 동화책 출간의 개수는 100개 이하입니다. (books, speeds 배열의 길이)
- 각 동화책 출간는 커리큘럼 상의 먼저 배포되어야 하는 순서대로 나열됩니다.
- 업무 속도는 해당 동화책 출간 담당자가 하루 동안 작업할 수 있는 작업량의 비율입니다.
- 배포는 배포될 수 있는 개선 완료된 책을 모아 하루에 한 번만 할 수 있습니다.
- speeds와 books 배열의 인덱스를 기준으로 동화책과 담당자가 정해집니다.
- books[0]번째 동화책 출간을 speeds[0]번째 담당자가 맡습니다. 만약, books[0]이 97이고 speeds[0]이 1이라면, 해당 책은 4일 뒤에 한꺼번에 출간됩니다.
입출력 예시
let books = [93, 30, 55]; let speeds = [1, 30, 5]; // 각각 7일, 3일, 9일 뒤에 출간할 수 있습니다. // 7일째에 출간할 수 있는 책은 2권이고, 9일째에 츨간할 수 있는 책은 1권입니다. let output = improveBook(books, speeds); console.log(output); // [2, 1] books = [95, 90, 99, 99, 80, 99]; speeds = [1, 1, 1, 1, 1, 1]; output = improveBook(books, speeds); console.log(output); // [1, 3, 2]
//04_[Queue] 동화책 출간
function improveBook(books, speeds) {
let isTaken = [];
let daysCount = 0;
let publishCount = 0;
let result = [];
for(let i = 0; i < books.length; i++){
while(books[i] < 100){
books[i] = books[i]+speeds[i]
daysCount++
}
isTaken.push(daysCount);
daysCount=0;
}
while(isTaken.length > 0){
let firstBook = isTaken[0]
while(firstBook >= isTaken[0]){
publishCount++;
isTaken.shift();
}
result.push(publishCount);
publishCount=0;
}
return result;
}
// function improveBook(books, speeds) {
// let answer = []; //답을 적는 배열입니다.
// let workDay = []; //책을 완성하는 데 필요한 시작을 나열한 배열입니다.
// let quotient = 0; //각 담당자마다 책이 발행되는 '일'수입니다.
// let remainder = 0; //각 담당자마다 책이 발행되는 시간을 제외한 min입니다.
// // books 배열을 순회합니다.
// for(let i = 0; i < books.length; i++) {
// // 각 담당자마다 책이 발행되는 시간을 계산합니다.
// quotient = Math.floor((100 - books[i]) / speeds[i]);
// //7/1 =>7 일수
// //70/30 => 2 일수인데
// //45/5 => 9
// remainder = (100 - books[i]) % speeds[i];
// //0
// //10 분이 더 필요하기 때문에 일을 더해줍니다. => 하루 더 지나가야지 출판 가능.
// //0
// // 만약 나머지(remainder)가 0보다 크면 몫(quotient)에 1을 더합니다.
// if(remainder > 0){
// quotient = quotient + 1;
// }
// // workDay 배열에 차례대로 담습니다.
// // workDay 배열은 books배열에서 "책이 발행되는 시간"만을 추출해 넣은 배열입니다.
// workDay.push(quotient);
// }
// // [7,3,9]
// // workDay 배열이 0보다 클 때까지 반복합니다. => 계속 반복?
// while(workDay.length > 0){
// // workDay에서 0번째 인덱스보다 큰 크기의 인덱스를 찾아 deployIndex에 할당합니다.
// let deployIndex = workDay.findIndex(fn => workDay[0] < fn);
// //7보다 큰 수는 9 => 인덱스는 2
// if(deployIndex === -1){
// // 만약 찾지 못했다면 answer에 workDay 배열의 길이를 넣은 후, workDay 내부의 요소를 전부 삭제합니다.
// answer.push(workDay.length);
// workDay.splice(0, workDay.length);
// } else {
// // 만약 찾았다면, 해당 인덱스를 answer에 넣고, workDay에서 그만큼 제외합니다.
// //[2,1]
// //[9]
// answer.push(deployIndex);
// workDay.splice(0, deployIndex);
// }
// }
// // 결과물을 반환합니다.
// //[2,1]
// return answer;
// }
// // function improveBook(books, speeds) {
// // let newBooks = [];
// // let result = [];
// // debugger;
// // function circle(books, speeds) {
// // for(let i = 0; i < books.length; i++){
// // newBooks.push(books[i] + speeds[i])
// // }
// // if(newBooks[0] >= 100){
// // const checkBooks = newBooks.map(function(el){
// // if(el >= 100){
// // return "완료"
// // }
// // })
// // if(checkBooks.includes(undefined) === false){
// // result.push(checkBooks.length)
// // return result
// // }
// // result.push(checkBooks.indexOf(undefined));
// // newBooks = newBooks.slice(checkBooks.indexOf(undefined));
// // speeds = speeds.slice(checkBooks.indexOf(undefined));
// // if(newBooks.length > 0){
// // circle(newBooks, speeds)
// // }
// // if(newBooks.length > 0){
// // return result
// // }
// // }
// // return circle(newBooks, speeds)
// // }
// // }
//레퍼런스
function improveBook(books, speeds) {
let answer = [];
let workDay = [];
let quotient = 0;
let remainder = 0;
// books 배열을 순회합니다.
for(let i = 0; i < books.length; i++) {
// 각 담당자마다 책이 발행되는 시간을 계산합니다.
quotient = Math.floor((100 - books[i]) / speeds[i]);
remainder = (100 - books[i]) % speeds[i];
// 만약 나머지(remainder)가 0보다 크면 몫(quotient)에 1을 더합니다.
if(remainder > 0){
quotient = quotient + 1;
}
// workDay 배열에 차례대로 담습니다.
// workDay 배열은 books배열에서 책이 발행되는 시간만을 추출해 넣은 배열입니다.
workDay.push(quotient);
}
// workDay 배열이 0보다 클 때까지 반복합니다.
while(workDay.length > 0){
// workDay에서 0번째 인덱스보다 큰 크기의 인덱스를 찾아 deployIndex에 할당합니다.
let deployIndex = workDay.findIndex(fn => workDay[0] < fn);
if(deployIndex === -1){
// 만약 찾지 못했다면 answer에 workDay 배열의 길이를 넣은 후, workDay 내부의 요소를 전부 삭제합니다.
answer.push(workDay.length);
workDay.splice(0, workDay.length);
} else {
// 만약 찾았다면, 해당 인덱스를 answer에 넣고, workDay에서 그만큼 제외합니다.
answer.push(deployIndex);
workDay.splice(0, deployIndex);
}
}
// 결과물을 반환합니다.
return answer;
}프린터
문제
김코딩은 최근 인쇄할 일이 많이 생겨 창고에서 안 쓰던 프린터를 꺼냈습니다. 이 프린터의 성능을 테스트하여 새로운 프린터를 장만할지 결정하려고 합니다. 김코딩은 프린터의 인쇄 작업 목록의 크기와 최대 용량을 가정하고 각기 다른 용량의 문서를 차례대로 인쇄하여 모든 문서가 인쇄되는데 최소 몇 초가 걸리는지 테스트하기로 했습니다. 프린터 인쇄 작업 목록의 제한사항은 다음과 같습니다.
[제한사항]
- 인쇄 작업 목록은 칸으로 이루어져 있습니다.
- 각 칸에는 한 개의 문서만 위치할 수 있습니다.
- 문서는 1초에 한 칸만 이동할 수 있습니다.
- 인쇄 작업 목록의 크기는 bufferSize이고 최대 용량 capacities 만큼 문서를 담을 수 있습니다.
만약, 인쇄 작업 목록의 크기가 2이고 최대 용량이 10Kib라면 크기가 [7, 4, 5, 6] Kib인 문서들이 최단 시간 안에 순서대로 모두 인쇄되는 과정은 다음과 같습니다.
- 1초가 지나면 인쇄 작업 목록에는 7Kib 크기의 문서가 추가됩니다.
- 2초일 때 인쇄 작업 목록의 최대 용량이 10Kib이기 때문에 4Kib 문서는 작업 목록에 들어갈 수 없습니다. 동시에 7Kib 문서는 작업 목록에서 1칸 앞으로 이동합니다.
- 3초일 때 7Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 4Kib 문서는 인쇄 작업 목록에 추가됩니다.
- 4초일 때 4Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다. 동시에 5Kib 문서는 인쇄 작업 목록에 추가됩니다.
- 5초일 때 4Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 5Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다. 최대 용량 10Kib 제한으로 6Kib 문서는 인쇄 작업 목록으로 추가될 수 없습니다.
- 6초일 때 5Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 6Kib 문서가 인쇄 작업 목록에 추가됩니다.
- 7초일 때 6Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다.
- 8초일 때 6Kib 문서가 마지막으로 인쇄됩니다.
위 예시에서와 같이 모든 문서가 출력되는데 걸리는 최소 시간은 8초가 걸립니다.
김코딩이 가지고 있는 프린터의 제한사항인 인쇄 작업 목록의 크기 bufferSize, 최대 용량 capacities가 주어집니다. 인쇄할 문서의 크기가 나열된 배열 documents가 모두 인쇄되는데 걸리는 최소 시간을 반환하는 솔루션을 만들어 주세요.
입력
인자1: bufferSize
- Number 타입의 인쇄 작업 목록 크기
인자 2: capacities
- Number 타입의 인쇄 작업 목록에 추가될 수 있는 최대 용량
인자 3: documents
- Number 타입을 요소로 갖는 문서 크기가 나열된 배열
출력
- Number 타입을 리턴해야 합니다.
주의사항
- bufferSize는 1 이상 100 이하입니다.
- capacities는 100Kib 이하입니다.
- 인쇄할 문서의 개수(배열의 길이) 1이상 100 이하입니다.
- 문서 하나의 크기는 capacities를 초과하지 않습니다.
입출력 예시
let bufferSize = 2; let capacities = 10; let documents = [7, 4, 5, 6]; let output = queuePrinter(bufferSize, capacities, documents); console.log(output) // 8
//05_[Queue] 프린터
function queuePrinter(bufferSize, capacities, documents) {
debugger;
let container = [];
let result = [];
for(let i = 0; i < bufferSize; i++){
container.push(0);
}
let insertDoc = documents.shift();//도큐먼츠에서 하나 뺀놈을 변수에 담아서
container.push(insertDoc); //컨테이너에 삽입
result.push(container.shift())//위에서 도큐먼츠의 요소가 하나 들어왔으므로 result에 넣어주는것
let sumOfContainer = container.reduce((x,y)=>(x+y),0);//컨테이너의 합 ?? 계속 알아서 초기화 되는가?
while(sumOfContainer > 0){
result.push(container.shift());//무조건 1초에 하나씩 빠져야함
if(container.length === 0 && documents.length === 0){
return result.length
}
sumOfContainer = container.reduce((x,y)=>(x+y),0)
if(sumOfContainer + documents[0] <= capacities){
container.push(documents.shift());
}else if(sumOfContainer + documents[0] > capacities){
container.push(0)
}
sumOfContainer = container.reduce((x,y)=>(x+y),0)
}
}
// function queuePrinter(bufferSize, capacities, documents) {
// // queuePrinter(작업 목록 크기, 최대 용량, [Number타입의 문서 크기])
// // 인쇄 작업 목록은 칸으로 이루어져 있습니다.
// // 각 칸에는 한 개의 문서만 위치할 수 있습니다.
// // 문서는 1초에 한 칸만 이동할 수 있습니다.
// // 인쇄 작업 목록의 크기는 bufferSize이고 최대 용량 capacities 만큼 문서를 담을 수 있습니다.
// // 1초 - 문서: [4,5,6], 작업목록: [][7]
// // 2초 - 문서: [4,5,6], 작업목록: [7][]
// // 3초 - 문서: [5,6], 작업목록: [][4], 인쇄: [7]
// // 4초 - 문서: [6], 작업목록: [4][5]
// // 5초 - 문서: [6], 작업목록: [5][], 인쇄: [4]
// // 6초 - 문서: [], 작업목록: [][6], 인쇄: [5]
// // 7초 - 문서: [], 작업목록: [6][]
// // 8초 - 문서: [], 작업목록: [][], 인쇄: [6]
// let lodingTime = 0;
// let workSpace = [];
// workSpace.length = bufferSize; //2 => [0,1]
// let currentCapacity = workSpace.reduce((a,b) => a+b) //최대 용량
// workSpace[bufferSize-1] = documents[0] //첫 문서를 작업목록 끝에 추가해줍니다.
// lodingTime++ //lodingTime 1초 증가
// for(let i=0; i<documents.length; i++) {
// workSpace[bufferSize-1] = documents[i] //첫 문서를 작업목록 끝에 추가해줍니다.
// lodingTime++ //lodingTime 1초 증가
// if(currentCapacity <= capacities) {
// workSpace[i] = workSpace[bufferSize-1]
// workSpace[bufferSize-1] = documents[i+1]
// lodingTime++
// }
// else {
// workSpace[0]
// lodingTime++
// }
// }
// return lodingTime;
// }
// // function queuePrinter(bufferSize, capacities, documents) {
// // //도큐먼츠가 없어질 때까지
// // let container = [];
// // let result = [];
// // let bucket = 0;
// // for(let i = 0; i < buffersize; i++){
// // container.push(0);
// // }
// // while(????여기조건 힘드네 > 0){
// // let sumOfContainer = for(let i = 0; i < container.length; i++){
// // bucket = bucket + container[i]
// // }
// // result.push(container[0]) //result로 넣어주는 과정
// // container.shift()
// // if(sumOfContainer + documents[0] <= capacities){
// // container.push(documents[0]) //컨테이너에 넣어주고
// // documents.shift()//문서함에서 빼고
// // }else if(sumOfContainer + documents[0] > capacities){
// // container.push(0)
// // }
// // if(documents.length === 0 && sumOfContainer === 0){
// // return result.length
// // }
// // }
// // }
//레퍼런스
function queuePrinter(bufferSize, capacities, documents) {
let count = 0;
let queue = [];
let totalBufferVolume = 0;
// queue에 bufferSize만큼 0을 삽입합니다. (queue에 들어갈 요소의 고정 갯수를 만들어 주는 과정입니다.)
for(let i = 0; i < bufferSize; i++){
queue.push(0);
}
// ~23번째 줄까지의 코드는 프린터를 처음 실행했을 때를 다룹니다.
// documents 배열에서 제일 앞의 있는 요소를 하나 빼내 currentDocument에 할당합니다.
let currentDocument = documents.shift();
// queue의 제일 앞에 currnetDocument를 삽입하고, 제일 마지막 요소를 없앱니다.
queue.unshift(currentDocument);
queue.pop();
// totalBufferVolume(총 용량)에 currnetDocument의 크기를 합칩니다.
totalBufferVolume = totalBufferVolume + currentDocument;
// 1 초가 지났다는 것을 count를 증가하며 나타냅니다.
count++;
// totalBufferVolume(총 용량)가 0이 될 때까지 반복합니다.
while(totalBufferVolume){
// totalBufferVolume(총 용량)에 queue에 있는 마지막 요소의 용량을 제거합니다.
totalBufferVolume = totalBufferVolume - queue.pop();
// documents 배열에서 제일 앞의 있는 요소를 하나 빼내 currentDocument에 할당합니다.
currentDocument = documents.shift();
// 만약 현재 문서와 총 용량을 더했을 때, 최대 용량(capacities)보다 작거나 같다면
if(currentDocument + totalBufferVolume <= capacities){
// queue에 currentDocument를 삽입하고 totalBufferVolume(총 용량)에 currentDocument 용량을 추가합니다.
queue.unshift(currentDocument);
totalBufferVolume = totalBufferVolume + currentDocument;
// 만약 현재 문서와 총 용량을 더했을 때, 최대 용량(capacities)보다 크다면
}else{
// 다시 documents에 currentDocument를 집어넣고 queue에는 0을 삽입합니다.
documents.unshift(currentDocument);
queue.unshift(0);
}
// 한 번 반복할 때마다 count(초)를 올립니다.
count++;
}
// count를 반환합니다.
return count;
}Implementation Tree
Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
맴버 변수
- 입력 데이터를 담을 수 있는 value
- 하위 노드를 저장할 수 있는 Array 타입의 children
메서드
- insertNode(value): 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 합니다.
- contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
주의사항
- value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.
사용 예시
const rootNode = new Tree(null); for(let i = 0; i <= 4; i++) { if(rootNode.children[i]) { rootNode.children[i].insertNode(i) } rootNode.insertNode(i); } rootNode; // {value: null, children: Array(5)} rootNode.contains[5]; //false rootNode.contains[1]; //true ...
//06_[Tree] 구현
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 됩니다.
this.value = value;
this.children = [];
}
// 트리의 삽입 메서드를 만듭니다.
insertNode(value) {
// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
// TODO: 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
const childNode = new Tree(value);
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// TODO: 값이 포함되어 있다면 true를 반환하세요.
// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
for(let i=0; i<this.children.length; i++) {
if (this.children[i].value === value) {
return true;
}
else {
if (this.children[i].contains(value)) { //*** if문 안에 재귀함수 넣기!
return true;
}
}
}
// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
return false;
}
}
//레퍼런스
class Tree {
//tree의 constructor를 구현합니다.
//tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정합니다.
constructor(value) {
this.value = value;
this.children = [];
}
//tree의 자식 노드를 생성 한 후에, 노드의 children에 push해 줍니다.
insertNode(value) {
const childNode = new Tree(value);
this.children.push(childNode);
}
// tree에서 value값을 탐색합니다.
// 현재 노드의 value 값이 찾는 값과 일치한다면 return합니다.
contains(value) {
if (this.value === value) {
return true;
}
// 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색합니다.
for (let i = 0; i < this.children.length; i += 1) {
const childNode = this.children[i];
if (childNode.contains(value)) {
return true;
}
}
return false;
}
}Implementation Graph
Graph 구현을 위한 기본적인 코드가 작성되어 있습니다. Graph 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해 주세요.
맴버 변수
- 버텍스와 간선을 담을 Array 타입의 matrix
메서드
- addVertex(): 그래프에 버텍스를 추가해야 합니다.
- contains(vertex): 그래프에 해당 버텍스가 존재하는지 여부를 Boolean으로 반환해야 합니다.
- addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
- hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
- removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
주의사항
- 인접 행렬 방식으로 구현해야 합니다.
- 구현해야 하는 그래프는 방향 그래프입니다.
- 구현해야 하는 그래프는 비가중치 그래프입니다.
- 구현해야 하는 그래프는 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다. (0, 1, 2, ... --> 정점)
- 인접 행렬 그래프는 정점이 자주 삭제되는 경우에는 적합하지 않기 때문에 정점을 지우는 메소드는 생략합니다.
사용 예시
const adjMatrix = new GraphWithAdjacencyMatrix(); adjMatrix.addVertex(); adjMatrix.addVertex(); adjMatrix.addVertex(); console.log(adjMatrix.matrix); /* TO 0 1 2 0 [0, 0, 0], FROM 1 [0, 0, 0], 2 [0, 0, 0] */ let zeroExists = adjMatrix.contains(0); console.log(zeroExists); // true let oneExists = adjMatrix.contains(1); console.log(oneExists); // true let twoExists = adjMatrix.contains(2); console.log(twoExists); // true adjMatrix.addEdge(0, 1); adjMatrix.addEdge(0, 2); adjMatrix.addEdge(1, 2); let zeroToOneEdgeExists = adjMatrix.hasEdge(0, 1); console.log(zeroToOneEdgeExists); // true let zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2); console.log(zeroToTwoEdgeExists); // true let oneToZeroEdgeExists = adjMatrix.hasEdge(1, 0); console.log(oneToZeroEdgeExists); // false console.log(adjMatrix.matrix); /* TO 0 1 2 0 [0, 1, 1], FROM 1 [0, 0, 1], 2 [0, 0, 0] */ adjMatrix.removeEdge(1, 2); adjMatrix.removeEdge(0, 2); let oneToTwoEdgeExists = adjMatrix.hasEdge(1, 2); console.log(oneToTwoEdgeExists); // false zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2); console.log(zeroToTwoEdgeExists); // false console.log(adjMatrix.matrix); /* TO 0 1 2 0 [0, 1, 0], FROM 1 [0, 0, 0], 2 [0, 0, 0] */
//07_[Graph] adjacency matrix 구현
// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
constructor() {
this.matrix = []; //배열
}
addVertex() {
//버텍스를 추가합니다.
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {
this.matrix[i].push(0); //2.[[0,0]]
}
this.matrix.push(new Array(currentLength + 1).fill(0)); // 1. [[0]] 3.[[0,0],[0,0]]
}
contains(vertex) {
//TODO: 버텍스가 있는지 확인합니다.
return this.matrix[vertex] !== undefined //자동으로 true/false 가능!
}
addEdge(from, to) { //from~to 0~2 0,1,2 3개 /1~2 1,2 2개
const currentLength = this.matrix.length;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//TODO: 간선을 추가할 수 없는 상황에서는 추가하지 말아야 합니다.
if ( from+1 > currentLength || to+1 > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//TODO: 간선을 추가해야 합니다. 배열이름[열의길이][행의길이];
return this.matrix[from][to]=1;
}
hasEdge(from, to) {
//TODO: 두 버텍스 사이에 간선이 있는지 확인합니다.
return this.matrix[from][to] === 1
}
removeEdge(from, to) {
const currentLength = this.matrix.length;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//TODO: 간선을 지울 수 없는 상황에서는 지우지 말아야 합니다.
if (from+1 > currentLength || to+1 > currentLength || from < 0 || to < 0) {
return;
}
//TODO: 간선을 지워야 합니다.
return this.matrix[from][to]=0;
}
}
//레퍼런스
// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
//graph의 constructor를 구현합니다.
constructor() {
this.matrix = [];
}
//vertex를 추가합니다.
addVertex() {
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {
this.matrix[i].push(0);
}
this.matrix.push(new Array(currentLength + 1).fill(0));
}
//vertex를 탐색합니다.
//this.matrix에 vertex가 존재한다면 true를 리턴하고, 반대의 경우라면 false를 리턴합니다.
contains(vertex) {
return !!this.matrix[vertex];
}
//vertex와 vertex를 이어주는 edge를 추가합니다.
addEdge(from, to) {
const currentLength = this.matrix.length - 1;
// 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
// from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
if (
from > currentLength ||
to > currentLength ||
from < 0 ||
to < 0
) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
// this.matrix[from][to]의 값을 1로 바꿔줘서 edge로 연결이 되어 있음을 표시합니다.
this.matrix[from][to] = 1;
}
// from vertex와 to vertex 사이에 edge를 가지고 있는지 여부를 판단합니다.
hasEdge(from, to) {
return !!this.matrix[from][to];
}
// from vertex와 to vertex 사이에 관련이 없다면, edge를 제거 합니다.
removeEdge(from, to) {
const currentLength = this.matrix.length - 1;
// 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
// from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
if (
from > currentLength ||
to > currentLength ||
from < 0 ||
to < 0
) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
// this.matrix[from][to]의 값을 0으로 바꿔줘서 관련이 없음을 표시합니다.
this.matrix[from][to] = 0;
}
}Implementation Binary Search Tree
Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Binary Search Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
맴버 변수
- 입력 데이터를 담을 수 있는 value
- 노드를 왼쪽에 저장할 수 있는 Array 타입의 left
- 노드를 오른쪽에 저장할 수 있는 Array 타입의 right
메서드
- insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
- contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
- preorder(callback): 전위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
- inorder(callback): 중위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
- postorder(callback): 후위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
주의사항
- value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.
사용 예시
const rootNode = new BinarySearchTree(10); rootNode.insert(7); rootNode.insert(8); rootNode.insert(12); rootNode.insert(11); rootNode.left.right.value; // 8 rootNode.right.left.value; //11 let arr = []; rootNode.preorder((value) => value * 2); arr; // [20, 14, 16, 24, 22] ...
//08_[Binary Search Tree] 구현
class BinarySearchTree {
constructor(value) {
// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
this.value = value;
this.left = null;
this.right = null;
}
// 이진 탐색 트리의 삽입하는 메서드를 만듭니다.
insert(value) {
// 입력값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 있어야 합니다.
// 보다 작다면, Node의 왼쪽이 비어 있는지 확인 후 값을 넣습니다.
if (value < this.value) {
if (this.left === null) {
this.left = new BinarySearchTree(value);
} else {
// TODO: 비어 있지 않다면
// 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
// TIP: 재귀함수를 사용합니다.
this.left.insert(value)
}
// 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣습니다.
} else if (value > this.value) {
if (this.right === null) {
this.right = new BinarySearchTree(value);
} else {
// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
// TIP: 재귀함수를 사용합니다.
this.right.insert(value);
}
//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
} else {
// 아무것도 하지 않습니다.
return;
}
}
// 앞서 구현했던 트리에 비해 이진 탐색 트리는 입력값과 트리 노드의 값의 크기를 비교하고 있습니다. 왜 그런 것일까요?
// 왼쪽 < 오른쪽 => 들어가야하기 때문에 비교를 해서 노드값을 입력해줍니다.
// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// TODO: 값이 포함되어 있다면 true를 반환하세요.
if (this.value === value) {
return true;
}
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문이 있어야 합니다.
if (value < this.value) {
// TODO: 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
// TODO:일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색합니다.
// if (this.left.value === value) {
// return true;
// } else {
// if(this.left.contains(value)===true) return true
// }
if(this.left && this.left.contains(value)) return true
}
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
if (value > this.value) {
// TODO: 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
// TODO:일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다.
// if (this.right.value === value) {
// return true;
// } else {
// if(this.right.contains(value)===true) return true
// }
return !!(this.right && this.right.contains(value))
}
// 없다면 false를 반환합니다.
return false;
}
/*
트리의 순회에 대해 구현을 합니다.
지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
*/
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
preorder(callback) {
callback(this.value);
if (this.left) {
this.left.preorder(callback);
};
if (this.right) {
this.right.preorder(callback);
};
}
// 이진 탐색 트리를 중위 순회하는 메서드를 만듭니다.
inorder(callback) {
//TODO: 전위 순회를 바탕으로 중위 순회를 구현하세요.
if (this.left) {
this.left.inorder(callback);
};
callback(this.value);
if (this.right) {
this.right.inorder(callback);
};
}
// 이진 탐색 트리를 후위 순회하는 메서드를 만듭니다.
postorder(callback) {
//TODO: 전위 순회를 바탕으로 후위 순회를 구현하세요.
if (this.left) {
this.left.postorder(callback);
};
if (this.right) {
this.right.postorder(callback);
};
callback(this.value);
}
}
//레퍼런스
class BinarySearchTree {
//BST의 constructor를 구현합니다.
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
// tree에 value를 추가합니다.
insert(value) {
// 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행합니다.
if (value < this.value) {
// this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
if (this.left === null) {
this.left = new BinarySearchTree(value);
}
// this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
else {
this.left.insert(value);
}
}
// 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행합니다.
else if (value > this.value) {
// this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
if (this.right === null) {
this.right = new BinarySearchTree(value);
}
// this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
else {
this.right.insert(value);
}
} else {
// 이미 value값을 포함하고 있습니다.
}
}
// tree의 value값을 탐색합니다.
contains(value) {
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (value === this.value) {
return true;
}
// 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행합니다.
if (value < this.value) {
return !!(this.left && this.left.contains(value));
}
// 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행합니다.
if (value > this.value) {
return !!(this.right && this.right.contains(value));
}
}
//tree를 전위 순회 합니다.
preorder(callback) {
callback(this.value);
if (this.left) {
this.left.preorder(callback);
}
if (this.right) {
this.right.preorder(callback);
}
}
// tree를 중위 순회 합니다
inorder(callback) {
if (this.left) {
this.left.inorder(callback);
}
callback(this.value);
if (this.right) {
this.right.inorder(callback);
}
}
//tree를 후위 순회 합니다
postorder(callback) {
if (this.left) {
this.left.postorder(callback);
}
if (this.right) {
this.right.postorder(callback);
}
callback(this.value);
}
}인접 행렬 생성하기
문제
방향이 있는 간선과 방향이 없는 간선들의 목록들을 받아 2차원 배열의 인접행렬을 반환하는 함수를 작성하세요.
조건
각 간선은 3가지 정보를 담고 있습니다.
- 0번째: 간선의 시작 정점 (0 이상의 정수)
- 1번째: 간선의 도착 정점 (0 이상의 정수)
- 2번째: 방향성 ('undirected' 일시 무향, 'directed' 일시 방향)
입력
인자 1: edges
- Number 타입의 방향/무향인 간선들의 목록이 담긴 배열
출력
- Array 타입을 리턴해야 합니다.
- 2차원 배열의 인접 행렬
주의사항
- 정점 0에서 정점4로 이어주는 간선이 존재할 경우 정점 1, 2, 3도 존재합니다.
- 반환하는 인접행렬은 2차원 배열이며, 행(row)는 바깥 배열, 열(column)은 안쪽 배열입니다.
- let matrix = [[0, 0], [0, 0]]
- matrix[0] === 0번째 행
- matrix[0][0] === 0번째 행의 0번째 열
- 두 정점간의 간선의 유무는 0과 1로 표시합니다.
- 0: 두 정점간에 간선이 존재하지 않을 경우
- 1: 두 정점간에 간선이 존재할 경우
- 아래의 2차원 배열에서 세로축은 시작 정점, 가로축은 도착 정점입니다.
const matrix = [ [0, 0, 0], [0, 0, 0], [0, 0, 0], ];
입출력 예시
let output1 = createMatrix([ [0, 3, "directed"], [0, 2, "directed"], [1, 3, "directed"], [2, 1, "directed"], ]); console.log(output1); /** * [ * [0, 0, 1, 1], * [0, 0, 0, 1], * [0, 1, 0, 0], * [0, 0, 0, 0] * ] */ let output2 = createMatrix([ [0, 2, "directed"], [2, 4, "undirected"], [1, 3, "undirected"], [2, 1, "directed"], ]); console.log(output2); /** * [ * [0, 0, 1, 0, 0], * [0, 0, 0, 1, 0], * [0, 1, 0, 0, 1], * [0, 1, 0, 0, 0], * [0, 0, 1, 0, 0], * ] */
//10_[Graph] 인접 행렬 생성하기
function createMatrix(edges) {
// 입력값: 간선이 담긴 배열 [간선 시작, 간선 도착, 방향성] => 출력값:2차원 배열의 인접 행렬
// addVertex => 0 // 방향성 => 'undirected' 양뱡향으로 정방향, 반대 방향 2개의 간선 존재, 'directed' 일시 방향으로 하나만 존재
// 1. from : 가장 작은 요소 "0"
// to: 1번째 정보 중 가장 큰 수으로 채워진 행렬을 만듭니다.
// 2. 각 요소를 차례로 실행하면서 0을 1로 바꾸어줍니다.
// 3. 주의 : 양방향일 때 배열 뒤집어주는 함수(리버스)를 이용해서
// 'undirected'일때는 리버스해서 한 번 더 돌려줍니다.
// 4. 2차원 배열인 인접 행렬을 리턴합니다.
let from = 0;
let to = 0;
let result = [];
debugger;
//1째 인수만 모은 배열
const arrivalArray = edges.map((ele) => ele[1])
to = Math.max(...arrivalArray);
//가장 큰 도착점 추출 완료
for (let i=0; i<to+1; i++) {
result.push(new Array(to + 1).fill(0));
}
//2차원 배열 완성시키기
//from과 to를 재할당하고 간선을 만들어보겠습니다!
for(let i=0; i<edges.length; i++) {
from = edges[i][0]
to = edges[i][1]
result[from][to] = 1;
if(edges[i][2] === "undirected") {
from = edges[i][1]
to = edges[i][0]
result[from][to] = 1;
}
}
return result;
}
//레퍼런스
function createMatrix(edges) {
// 행렬의 크기를 구합니다.
// max 변수를 0으로 할당하고, edges를 전부 순회해 제일 큰 숫자를 max에 할당합니다.
// max보다 크지 않을 경우엔 바꾸지 않습니다.
let max = 0;
for (let i = 0; i < edges.length; i++) {
// edges의 한 요소에는 숫자 이외에 방향성도 있으니, 숫자까지만 slice를 하여 비교합니다.
const curMax = Math.max(...edges[i].slice(0, 2));
curMax > max ? (max = curMax) : null;
}
// matrix의 뼈대를 잡습니다.
// max로 구한 최대값에 1을 더하여 array를 만들고(0번째부터 있기 때문입니다) 전부 0으로 채운 뒤
// map을 사용해 각 요소마다 배열로 바꿔줍니다. 배열의 크기를 이번에도 최대값에 1을 더한 뒤, 0으로 채웁니다.
const result = new Array(max + 1).fill(0).map((row) => new Array(max + 1).fill(0));
// edges를 순회하며 무향인 곳엔 각각의 간선에 1로 바꾸어 주고, 방향이 있는 간선엔 해당 간선에만 1로 바꾸어 줍니다.
// 만약, [0, 3, "directed"]가 들어왔다면,
// 만들어 둔 result의 0 번째 row에 3 번째 col에 1을 추가합니다.
// [ 0, 0, 0, 1 ] => 0번째 버텍스가 갈 수 있는 간선 중, 3 번으로 가는 간선만 갈 수 있습니다.
edges.forEach((edge) => {
const [row, col, direction] = edge;
if (direction === "undirected") {
result[col][row] = 1;
}
result[row][col] = 1;
});
// result를 반환합니다.
return result;
}인접 행렬 길찾기
문제
주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.
입력
인자 1: matrix
- Array 타입을 요소로 갖는 인접 행렬이 담긴 2차원 배열
인자 2: from
- Number 타입의 시작 정점
인자 3: to
- Number 타입의 도착 정점
출력
- boolean 타입을 리턴해야 합니다.
입출력 예시
const result = getDirections( [ [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0], ], 0, 2 ); console.log(result); // true
- 정점 0에서 2로 가는 길이 존재하는지 확인합니다.
- 0 --> 1 로 가는 간선이 존재하고, 1 --> 2 로 가는 간선이 존재하기 때문에 true를 반환합니다.
//11_[Graph] 인접 행렬 길찾기
function getDirections(matrix, from, to) {
let pass = [from];
let findDirection = function (matrix, from, to) {
if (matrix[from][to] === 1) {
return true;
}
for (let i = 0; i < matrix[from].length; i++) {
if (matrix[from][i] === 1 && pass.includes(i) === false) {
if (findDirection(matrix, i, to)) {
return true;
}
}
}
return false;
};
return findDirection(matrix, from, to);
}
//레퍼런스
function getDirections(matrix, from, to) {
// queue를 간단하게 생성하고, 첫 시작점으로 from을 할당합니다.
const queue = [from];
const enqueue = (n) => queue.push(n);
const dequeue = (n) => queue.shift();
// 방문했다는 것을 표시하기 위해 1차원 행렬을 생성합니다.
const isVisited = new Array(matrix.length).fill(false);
// 첫 정점 방문 여부를 표시합니다.
isVisited[from] = true
// queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다.
while (queue.length > 0) {
// queue에서 정점을 하나 빼서 now에 할당합니다.
const now = dequeue();
// 목적지인지 검사하고, 목적지라면 true를 반환합니다.
if (now === to) return true;
// 해당 정점의 간선들을 확인합니다.
for (let next = 0; next < matrix[now].length; next++) {
// 만약, 간선이 있고 방문하지 않았다면
if (matrix[now][next] && !isVisited[next]){
// queue에 next를 넣습니다. (다음 정점으로 가기 위해)
enqueue(next);
// 해당 정점을 방문했다는 것을 표시합니다.
isVisited[next] = true
}
}
}
// 길이 없다면 false를 반환합니다.
return false;
}