210519 토요일 12~13일차
(인턴하면서 퇴근 후 조금씩 스터디하고 토요일에 복습하면서 진도를 나감)
# 9~11일차 복습
CH5 큐
- 큐는 리스트의 일종으로 끝부분으로 데이터가 삽입되고 앞부분에서 데이터가 삭제되는 구조이다. 일어난 순서대로 데이터를 저장하지만 스택과 반대로 먼저 들어온 순서대로 처리한다. 선입선출.
- enqueue는 큐의 끝부분에 요소 추가, dequeue는 큐의 앞부분에 요소 삭제, 큐의 앞부분 요소를 확인하는 peek, 요소 개수를 확인하는 length, 전체 요소를 삭제하는 length, front()는 맨 앞의 요소, back()은 맨 뒤의 요소를 보여준다.
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue() {
return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
function front() {
return this.dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
}
// 큐가 비었는지 확인
function empty() {
if (this.dataStore.length === 0) {
return true;
} else {
return false;
}
}
let q = new Queue();
q.enqueue("M");
q.enqueue("C");
q.enqueue("J");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue: " + q.front());
console.log("Back of queue: " + q.back());
- 큐로 데이터 정렬하기
큐를 이용하여 기수정렬을 구현할 수 있다. 기수정렬은 두 번의 과정을 거쳐 데이터를 정렬한다. 0~99 정수를 이용한다.
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue() {
return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
function front() {
return this.dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
}
// 큐가 비었는지 확인
function empty() {
if (this.dataStore.length === 0) {
return true;
} else {
return false;
}
}
function count() {
return this.dataStore.length;
}
// @ : 큐로 데이터 정렬하기, 기수 정렬, 1의 자리 기준으로 숫자 정렬 후 10의 자리 기준으로 숫자 정렬.
// @ : 각 숫자당 1개의 큐이므로 9개의 큐가 필요하다.
function distribute(nums, queues, n, digit) {
for (let i = 0; i < n; ++i) {
if (digit === 1) {
// @ : nums[i]%10이면 해당 숫자의 일의 자리 숫자를 기준으로 queues[일의자리숫자]에 enqueue된다.
console.log(nums[i] % 10);
queues[nums[i] % 10].enqueue(nums[i]);
} else {
// @ : Math.floor(nums[i]/10)로 십의 자리 숫자를 구한 뒤 queues[십의자리숫자]에 enqueue한다.
console.log(Math.floor(nums[i] / 10));
queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
}
}
}
// @ : 큐에 저장된 숫자를 수집하는 함수
function collect(queues, nums) {
let i = 0;
for (let digit = 0; digit < 10; ++digit) {
while (!queues[digit].empty()) {
// @ : nums[0~10]에 queues에 기수 정렬한 숫자들을 차례대로 넣어줌, 일의자리숫자 정렬 > 십의자리숫자 정렬시 기수정렬됨
nums[i++] = queues[digit].dequeue();
}
}
}
function dispArray(arr) {
for (let i = 0; i < arr.length; ++i) {
console.log(arr[i] + " ");
}
}
let queues = [];
// # : 각 숫자당 한 개씩 9개의 큐가 필요하다.
for (let i = 0; i < 10; ++i) {
queues[i] = new Queue();
}
let nums = [];
// # : 랜덤한 숫자 0~99를 만들어 nums에 할당한다.
for (let i = 0; i < 10; ++i) {
nums[i] = Math.floor(Math.floor(Math.random() * 101));
}
console.log("Before radix sort: ");
dispArray(nums);
distribute(nums, queues, 10, 1);
console.log();
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
console.log("\n\nAfter radix sort: ");
dispArray(nums);
- 우선순위 큐
보통 큐에서는 먼저 넣은 요소부터 삭제된다. 하지만 선입선출이 아니라 우선순위와 같은 다른 기준으로 요소를 삭제해야 하는 경우도 있다. 이럴 때는 우선순위 큐를 이용한다. 응급실에서는 환자의 상태를 평가해 우선순위 코드를 부여한다. 우선순위가 높은 환자가 낮은 환자보다는 먼저 진료 받는다. code는 우선순위를 나타내며 가장 높은 우선순위는 1,2,3,4,,, 순이다.(숫자가 낮을수록 높다.)
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue() {
return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
function front() {
return this.dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
}
// 큐가 비었는지 확인
function empty() {
if (this.dataStore.length === 0) {
return true;
} else {
return false;
}
}
function count() {
return this.dataStore.length;
}
// # : 우선순위 큐
// # : 예진 간호사가 환자 검사 >> 환자상태평가로 우선순위 코드 부여 >> 우선순위 높으면 먼저 진료받음(우선순위 코드가 같으면 선입선출)
function Patient(name, code) {
this.name = name;
this.code = code; // 우선순위 or 심각성
}
// # : 가장 높은 우선순위(1 > 2 > 3 > 4 > ,,,) 삭제
function dequeue() {
let entry = 0;
for (let i = 0; i < this.dataStore.length; ++i) {
// @ : this.dataStore[entry].code는 가장 작은 code(가장 높은 우선순위)로 유지되어야 한다.
// @ : 따라서 인덱스 i일 때 더 작으면 entry=i로 할당한다.
if (this.dataStore[i].code < this.dataStore[entry].code) {
console.log(
"deq",
this.dataStore[i].code,
this.dataStore[entry].code
);
entry = i;
console.log("ent: ", entry);
}
}
return this.dataStore.splice(entry, 1);
}
// # : 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr +=
this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
}
return retStr;
}
// # : work
let p = new Patient("Smith", 5);
let ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);
p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
console.log(ed.toString());
let seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
// 다음 환자 치료
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
# 1. Queue 클래스를 고쳐서 Deque 클래스를 만드시오. Deque는 큐와 비슷한 자료구조로 리스트의 앞부분과 끝부분 모두에서 요소의 삽입과 삭제가 일어난다. 프로그램을 이용해 구현한 Deque 클래스를 테스트하시오.
push_front() : 자바스크립트는 배열에 shift()라는 맨 앞의 요소를 제거해주는 메서드가 있어 이를 이용해 구현하였다.
pop_back() : length 프로퍼티를 이용해 length-1 위치의 요소를 1개 지우도록 splice 메서드로 구현하였다.
function Deque() {
this.dataStore = [];
this.push_front = push_front;
this.push_back = push_back;
this.pop_front = pop_front;
this.pop_back = pop_back;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
// # : push_front() : 맨 앞에 새로운 요소를 삽입한다.
// # : push_back() : 맨 뒤에 새로운 요소를 삽입한다.
// # : pop_front() : 맨 앞에 요소를 제거한다.
// # : pop_back() : 맨 뒤에 요소를 제거한다.
// ! : splice(맨 앞 인덱스, 0, 추가하려는 요소)를 이용한다. 두 번째 인자의 길이만큼 삭제하지만 0이면 추가.
function push_front(element) {
this.dataStore.splice(0, 0, element);
}
function push_back(element) {
this.dataStore.push(element);
}
function pop_front() {
return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
// ! : back함수에서 length-1을 사용하듯 맨 뒤의 요소에 대한 인덱스를 가져와서 해당 인덱스를 splice로 삭제한다.
function pop_back() {
return this.dataStore.splice(this.dataStore.length - 1, 1); // 배열 앞부분에 저장된 요소를 1개 삭제
}
function front() {
return this.dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
}
// 큐가 비었는지 확인
function empty() {
if (this.dataStore.length === 0) {
return true;
} else {
return false;
}
}
let dq = new Deque();
dq.push_front("M");
dq.push_front("C");
dq.push_front("J");
console.log(dq.toString());
dq.pop_front();
console.log(dq.toString());
dq.pop_back();
console.log(dq.toString());
dq.push_back("A");
dq.push_back("B");
console.log(dq.toString());
console.log("Front of dequeue: " + dq.front());
console.log("Back of dequeue: " + dq.back());
- 우선순위 큐를 낮은 수가 아니라 높은 숫자를 높은 우선순위로 갖도록 구현하시오.
entry를 가장 높은 숫자가 들어있는 인덱스로 유지되어야 한다.
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue() {
return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
function front() {
return this.dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
}
// 큐가 비었는지 확인
function empty() {
if (this.dataStore.length === 0) {
return true;
} else {
return false;
}
}
function count() {
return this.dataStore.length;
}
// # : 우선순위 큐
// # : 예진 간호사가 환자 검사 >> 환자상태평가로 우선순위 코드 부여 >> 우선순위 높으면 먼저 진료받음(우선순위 코드가 같으면 선입선출)
function Patient(name, code) {
this.name = name;
this.code = code; // 우선순위 or 심각성
}
// ! : 가장 높은 우선순위(,,, > 4 > 3 > 2 > 1) 삭제
function dequeue() {
let entry = 0;
for (let i = 0; i < this.dataStore.length; ++i) {
if (this.dataStore[i].code > this.dataStore[entry].code) {
console.log(
"deq",
this.dataStore[i].code,
this.dataStore[entry].code
);
entry = i;
console.log("ent: ", entry);
}
}
return this.dataStore.splice(entry, 1);
}
// # : 출력
function toString() {
let retStr = "";
for (let i = 0; i < this.dataStore.length; ++i) {
retStr +=
this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
}
return retStr;
}
// # : work
let p = new Patient("Smith", 5);
let ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);
p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
console.log(ed.toString());
let seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
// 다음 환자 치료
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
# 12~13일차 학습
CH6 연결 리스트
상황에 따라 배열보다는 연결 리스트가 더 유용할 수도 있다.
6.1 배열의 단점
대부분의 프로그래밍 언어에서는 배열이 길이가 정해져 있어서 배열이 꽉 차면 추가로 데이터를 입력하기가 어렵다. 배열에 데이터를 추가하거나 삭제할 때도 나머지 요소를 이동해야 하므로 어려움이 따른다. 자바스크립트는 배열의 split()을 이용하면 간단하다.
하지만 자바스크립트의 배열은 객체라서 C++이나 자바보다 배열의 효율이 떨어진다.
배열로 작업했을 때 너무 느리다고 판단되면 사용할 수 있다. 일차원의 배열을 사용한 곳 대부분은 연결 리스트로 바꿀 수 있다. 다만 임의의 요소에 접근해야 할 때는 연결 리스트보다는 배열이 낫다.
6.2 연결 리스트 정의
node(노드)라 불리는 객체가 모여 연결 리스트를 구성한다. 각 노드는 객체 레퍼런스를 통해 리스트의 다른 노드와 연결된다. 다른 노드를 참조하는 레퍼런스를 Link라고 한다.
인덱스로 요소를 참조할 수 있는 배열과 달리 연결 리스트의 요소는 다른 요소와의 관계를 통해 원하는 요소를 참조할 수 있다. 예를 들어, Bread가 두 번째 위치에 있다라고 표현하는 게 아니라 "Milk" 다음에 "Bread"가 있다라고 표현한다. 연결 리스트에서는 첫 번째 노드에서 마지막 노드로 이동하는 방식으로 전체 요소를 확인할 수 있다.(종종 연결 리스트에서는 Head 노드를 시작점으로 사용하는데 여기서는 이 노드는 방문 대상에서 제외한다.) 연결 리스트의 마지막은 Null로 끝나는데 연결 리스트의 끝을 가리킨다.
새 노드를 추가하려면 삽입하려는 노드의 이전 노드(previous node) 링크가 새 노드를 가리키도록 바꿔야 하고 새 노드의 링크는 이전 노드가 가리키던 노드를 가리키도록 설정해야 한다.
아래는 "Eggs" 뒤로 "Cookies"라는 노드를 추가한 모습이다.
연결 리스트의 항목을 삭제하는 일도 간단한 편이다. 삭제하려는 노드의 이전에 있는 노드 링크를 삭제하려는 노드가 가리키는 노드로 바꾼 다음, 삭제하려는 노드의 링크를 Null로 설정하면 노드가 삭제된다.
연결 리스트는 다른 다양한 함수도 제공한다. 이 중 특히 삽입과 삭제 동작은 왜 연결 리스트가 유용한지 가장 명확하게 보여준다.
6.3 객체 기반 연결 리스트 설계
연결 리스트에서는 두 클래스를 만들어야 한다. 우선 연결 리스트에 추가할 수 있는 Node 클래스와 LinkedList 클래스를 만든다. LinkedList 클래스는 노드의 삽입, 삭제, 리스트 출력, 기타 연결 리스트에 필요한 기능을 제공한다.
6.3.1 Node 클래스
Node 클래스는 노드의 데이터를 저장하는 element와 연결 리스트의 다음 노드 링크를 저장하는 next, 두 가지 프로퍼티를 포함한다.
// # : 노드 클래스
function Node(element) {
this.element = element;
this.next = null;
}
6.3.2 연결 리스트 클래스
LList 클래스는 연결 리스트의 기능을 제공한다. LList 클래스는 새 노드의 삽입, 기존 노드 삭제, 리스트의 특정 데이터 검색 등의 기능을 제공한다. 새 연결 리스트를 만드는 데 사용할 생성자 함수도 제공한다. 연결 리스트에는 리스트의 헤드를 나타내는 노드에 해당하는 한 개의 프로퍼티만 포함한다.
// # : 연결 리스트 클래스
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.findPrevious = findPrevious;
this.remove = remove;
this.display = display;
}
초기에는 head 노드의 next 프로퍼티를 null로 설정한다. 리스트에 노드가 추가되면 나중에 next 프로퍼티의 값을 바꾼다.
6.3.3 새로운 노드 삽입하기
기존 노드의 뒤에 새 노드를 추가하려면 '기존' 노드를 찾아야 한다. 따라서 연결 리스트에서 특정 데이터를 포함하는 노드를 검색하는 헬퍼 함수 find()를 구현한다.
// # : 새로운 노드 추가하기 : 기존 노드 뒤라고 가정, 기존 노드를 찾아야 한다.(find) 찾으면 해당 노드를 반환한다.
function find(item) {
let currNode = this.head;
// ! : 우선 새 노드를 만들고 head 노드로 설정
while (currNode.element !== item) {
// ! : 다음 노드로 반복 이동하면서 현재 노드의 element 프로퍼티가 탐색하려는 값과 같은 값을 포함하는지 확인한다.
// ! : 기존 노드를 찾으면 새 노드의 next 프로퍼티를 기존 노드의 next 프로퍼티의 값으로 설정한다.
currNode = currNode.next;
}
return currNode;
}
head 노드로 새 노드를 설정한다. 그리고 다음 노드로 반복 이동하면서 현재 노드의 element 프로퍼티가 탐색하려는 값과 같은 값을 포함하는지 확인한다. 원하는 데이터를 찾으면 해당 노드를 반환한다. 데이터를 찾지 못했으면 null을 반환한다.
'기존' 노드를 찾았으면 새 노드의 next 프로퍼티를 '기존' 노드의 next 프로퍼티 값으로 설정한다. 그리고 '기존' 노드의 next 프로퍼티를 새 노드의 next 프로퍼티로 설정한다.
function insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
}
연결 리스트의 요소를 출력하는 함수
function display() {
let currNode = this.head;
while (!(currNode.next === null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
6.3.4 연결 리스트에서 노드 삭제하기
연결 리스트에서 노드를 삭제하려면 바로 이전 노드를 찾아야 한다. 이전 노드를 찾았으면 이전 노드의 next 프로퍼티를 삭제하려는 노드의 다음 노드로 설정해야 한다. findPrevious()는 다음 노드에서 삭제하려는 데이터를 포함하고 있으면 탐색을 멈춘다. 삭제하려는 데이터를 찾았으면 삭제하려는 데이터를 포함하는 노드의 이전 노드를 반환한다. 그래야만 이전 노드의 next 프로퍼티를 고칠 수 있기 때문이다.
// # : 연결리스트에서 노드 삭제하려면 삭제하려는 바로 이전 노드를 찾아야 한다. 이전 노드를 찾았으면 이전 노드의 next를 삭제하려는 노드의 다음 노드로 설정해야 한다.
function findPrevious(item) {
let currNode = this.head;
while (!(currNode.next === null) && currNode.next.element !== item) {
currNode = currNode.next;
}
return currNode;
}function remove(item) {
let prevNode = this.findPrevious(item);
if (!(prevNode.next === null)) {
prevNode.next = prevNode.next.next;
}
}
prevNode.next = prevNode.next.next 는 삭제하려는 노드를 가리키지 않도록 이전 노드의 링크를 우회시켜 원하는 노드를 삭제한다.
6.4 양방향 연결 리스트
연결 리스트는 처음부터 마지막 노드까지 쉽게 탐색할 수 있다. 하지만 역방향으로 노드를 탐색하는 것은 쉽지 않다. 노드에 이전 노드의 링크를 저장하는 프로퍼티를 추가하면 이 문제를 쉽게 해결할 수 있다. 하지만 링크를 추가하면 노드 추가할 때 더 많은 작업을 해야 한다. 대신 노드를 삭제할 때는 더 이상 이전 노드를 찾을 필요가 없어 좀 더 간단해진다.
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
insert 함수는 새 노드의 previous 프로퍼티를 이전 노드로 설정해야 한다.
function insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
}
양방향 연결 리스트의 remove 함수는 이전 노드를 찾을 필요가 없으므로 좀더 간단한데 우선 삭제하려는 데이터를 포함하는 노드를 찾는다. 그리고 삭제하려는 노드 이전 노드의 next 프로퍼티를 삭제하려는 노드의 next 값으로, 삭제하려는 노드 다음 노드의 previous 프로퍼티를 삭제하려는 노드의 previous 값으로 각각 설정한다.
function remove(item) {
let currNode = this.find(item);
if (!(currNode.next === null)) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
양방향 연결 리스트의 마지막 노드로 이동하는 유틸리티 함수를 이용해 역순으로 연결 리스트를 출력하는 동작을 수행할 수 있다.
// # : 양방향 연결 리스트의 "마지막 노드로 이동하는 유틸리티 함수"를 이용해 역순으로 연결 리스트를 출력하는 동작을 수행할 수 있다.
function findLast() {
let currNode = this.head;
while (!(currNode.next === null)) {
currNode = currNode.next;
}
return currNode;
}
findLast 함수를 이용하면 역순으로 양방향 연결 리스트의 요소를 출력할 수 있다.
// # : 역순으로 양방향 연결리스트의 요소 출력
function dispReverse() {
let currNode = this.findLast();
while (!(currNode.previous === null)) {
console.log(currNode.element);
currNode = currNode.previous;
}
}
6.5 순환형 연결 리스트
순환형 연결 리스트는 단방향 연결리스트와 같은 종류의 노드를 포함한다. 유일하게 다른 점은 순환형 연결 리스트에서는 헤드의 next 프로퍼티가 자신을 가리킨다는 것이다.
head.next = head;는 전체 리스트에 적용되어 항상 마지막 노드의 next 프로퍼티는 헤더를 가리킨다.
복잡한 양방향 연결 리스트를 만들지 않고 간단하게 역방향으로 탐색할 수 있다는 것이 강점이다. 순환형 연결 리스트에서는 노드의 끝을 지나 계속 탐색하면 결국 역방향에 있는 노드로 이동할 수 있다.
function LList() {
this.head = new Node("head");
this.head.next = this.head;
this.find = find;
this.insert = insert;
this.display = display;
this.findPrevious = findPrevious;
this.remove = remove;
}
display() 함수는 순환형 연결 리스트에 사용하려면 while 루프 실행 조건을 헤드에서 멈추도록 바꿔야 한다.
function display() {
let currNode = this.head;
while (!(currNode.next === null) && !(currNode.next.element == "head")) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
6.6 기타 연결 리스트 함수
- advance(n) : 연결 리스트에서 n 노드만큼 전진
- back(n) : 양방향 연결 리스트에서 n 노드만큼 뒤로 후진
- show() : 현재 노드만 출력
6.7 연습문제
1. advance(n) 함수를 구현하시오. advance(n) 함수를 호출하면 현재 노드가 n 노드만큼 전진한다.
advance(n)은 insert(newElement, item) 함수에서 let current = this.find(item)으로 기존 노드를 찾아왔을 때 해당 노드(current)의 n 노드만큼 전진시키는 기능을 가진 함수로 해석하여 구현하였다. 단방향 연결 리스트에서는 this.head를 기준으로 탐색하기 때문에 현재 노드를 받아주어야 하는데 insert에서만 이렇게 사용하고 있기 때문이다.
=> 처음에는 전진한다는 것이 연결 리스트의 왼쪽으로 이동하는 것을 뜻한다고 생각했는데 찾아보니 단방향 연결 리스트 특성상 prevNode를 알 수 없기도 하고 오른쪽으로 이동시키는 것임을 알게 되었다.
=> 따라서 전진이란 연결 리스트의 오른쪽 방향으로 이동하는 것을 뜻하며 head(맨 앞) 노드부터 n 노드만큼 전진하도록 구현하는 것이 맞다고 생각해서 다시 설계했다.
// # : 1. advance(n) 함수를 구현하시오. advance(n) 함수를 호출하면 현재 노드가 n 노드만큼 전진한다.
function Node(element) {
this.element = element;
this.next = null;
}
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.findPrevious = findPrevious;
this.remove = remove;
this.advance = advance;
this.display = display;
}
function find(item) {
let currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
function display() {
let currNode = this.head;
while (!(currNode.next === null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function findPrevious(item) {
let currNode = this.head;
while (!(currNode.next === null) && currNode.next.element !== item) {
currNode = currNode.next;
}
return currNode;
}
function remove(item) {
let prevNode = this.findPrevious(item);
if (!(prevNode.next === null)) {
prevNode.next = prevNode.next.next;
}
}
function advance(n) {
let currNode = this.head;
for (let i = 0; i < n; ++i) {
if (!(currNode.next === null)) {
console.log("if O , next 요소", currNode.next.element);
currNode = currNode.next;
}
}
return currNode;
}
let cities = new LList();
cities.insert("Con", "head");
cities.insert("Rus", "Con");
cities.insert("Car", "Rus");
cities.insert("Alm", "Car");
cities.display();
console.log();
console.log("adv 3 : ", cities.advance(3));
console.log();
cities.display();
2. back(n) 함수를 구현하시오. back(n) 함수를 호출하면 현재 노드가 n 노드만큼 후진한다.
단방향 연결 리스트를 기준으로 하는 게 아니라 양방향 연결 리스트로 구현해야 하는 것 같은데 6.6의 설명에서는 연결 리스트라고 한다.
=> 양방향 연결 리스트로 구현했다.
역순으로 출력된 것을 보면 Alm이 맨 앞에 와있고 back()의 함수가 호출될 때 맨 뒤의 요소가 Alm이다. Alm에서 2번 후진시켰으므로 Run이 된다.
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.display = display;
this.remove = remove;
this.findLast = findLast;
this.dispReverse = dispReverse;
this.back = back;
}
function insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
}
function remove(item) {
let currNode = this.find(item);
if (!(currNode.next === null)) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
// # : 양방향 연결 리스트의 "마지막 노드로 이동하는 유틸리티 함수"를 이용해 역순으로 연결 리스트를 출력하는 동작을 수행할 수 있다.
function findLast() {
let currNode = this.head;
while (!(currNode.next === null)) {
currNode = currNode.next;
}
return currNode;
}
// # : 역순으로 양방향 연결리스트의 요소 출력
function dispReverse() {
let currNode = this.findLast();
while (!(currNode.previous === null)) {
console.log(currNode.element);
currNode = currNode.previous;
}
}
function display() {
let currNode = this.head;
while (!(currNode.next === null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function find(item) {
let currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
function back(n) {
let currNode = this.findLast();
console.log("맨뒤요소:", currNode);
for (let i = 0; i < n; ++i) {
if (!(currNode.previous === null)) {
currNode = currNode.previous;
}
}
return currNode;
}
let cities = new LList();
cities.insert("Con", "head");
cities.insert("Run", "Con");
cities.insert("Car", "Run");
cities.insert("Alm", "Car");
console.log("역순 출력");
cities.dispReverse();
console.log();
console.log("맨 뒤의 요소부터 back 2 : ", cities.back(2));
3. 현재 노드의 데이터를 출력하는 show() 함수를 구현하시오.
function show() {
let currNode = this.head;
return currNode.element
}
let cities = new LList();
cities.insert("Con", "head");
cities.insert("Run", "Con");
cities.insert("Car", "Run");
cities.insert("Alm", "Car");
cities.display();
console.log();
console.log("현재 노드 : ",cities.show());
4. 대화형으로 입력된 테스트 점수를 단방향 연결 리스트로 저장하는 프로그램을 구현하시오.
score를 입력하여 "head'의 뒤의 위치에 insert하도록 구현했는데 연속적으로 입력 받기 위해서는 nodejs에서 대화형 구현에 대해서 더 알아봐야 한다. 상당히 불편하게 되어 있다.
처음에는 "head"의 뒤에 점수를 저장시켜준 다음 if문으로 scores(연결 리스트)의 마지막 원소가 null이 아닐 때 새로운 요소를 그 뒤로 저장해주는 방식을 사용할 것 같다.
// # : 4. 대화형으로 입력된 테스트 점수를 단방향 연결 리스트로 저장하는 프로그램을 구현하시오.
function Node(element) {
this.element = element;
this.next = null;
}
function LList() {
this.head = new Node("head");
this.find = find;
this.insert = insert;
this.findPrevious = findPrevious;
this.remove = remove;
this.display = display;
this.lastElement = lastElement;
}
function find(item) {
let currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
function display() {
let currNode = this.head;
while (!(currNode.next === null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function findPrevious(item) {
let currNode = this.head;
while (!(currNode.next === null) && currNode.next.element !== item) {
currNode = currNode.next;
}
return currNode;
}
function remove(item) {
let prevNode = this.findPrevious(item);
if (!(prevNode.next === null)) {
prevNode.next = prevNode.next.next;
}
}
function lastElement() {
let currNode = this.head;
while (!(currNode.next === null)) {
currNode = currNode.next;
}
return currNode;
}
scores = new LList();
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", function (score) {
scores.insert(score,"head")
rl.close();
});
rl.on("line", function (score) {
const lastEl = scores.lastElement()
if(lastEl === null){
scores.insert(score,"head")
}else{
scores.insert(score,lastEl)
}
rl.close();
});
https://stitchcoding.tistory.com/13
Node JS 표준 입력 받기
https://nodejs.org/api/readline.html Readline | Node.js v14.6.0 Documentation Readline# Source Code: lib/readline.js The readline module provides an interface for reading data from a Readable stream..
stitchcoding.tistory.com
5. 양방향 연결 리스트를 이용해 6-4를 다시 구현하시오.
6-4는 양방향 연결 리스트로 구현되어 있다.(반복)
6. 요세푸스와 40명의 유대인이 로마 군인에게 붙잡힐 위기에 처했다. 유대인 병사들은 포로로 잡히느니 죽음을 택하기로 했다. 사람으로 원을 만든 다음 사람이 남지 않을 때까지 매 세 번째 병사를 죽여 나가기로 작전을 세웠다. 요세푸스와 다른 한 명은 일찍 죽임을 당하는 위치에 서고 싶지 않아 어디에 서야 최후까지 생존할 수 있을지 빨리 계산해야 했다. n 명의 사람이 원을 만들고 매 m 번째 사람을 죽이는 프로그램을 구현하시오. 그리고 마지막으로 남을 두 사람을 계산하시오. 순환형 연결 리스트를 이용해 문제를 해결한다.
n명의 사람과 m번째 사람을 죽이기 위해 n, m을 입력 받는 것은 따로 구현하지 않았고 미리 입력한 n명의 사람을 한글 이름 생성기로 만들어서 이 순환형 연결 리스트를 이용해 미리 입력한 m번째 사람을 매번 죽이고 마지막으로 남은 생존자들을 출력할 수 있도록 구현하였다.
이를 위해 아래의 3개 메서드가 필요했다.
- generateRandomName : 성과 이름을 Math.random()함수와 Math.floor를 이용해서 만들고 합쳐서 한 명의 병사를 만들었다.
// 한글 이름 생성기
const generateRandomName = () => {
const lastName = "김이박";
const firstName =
"피어나는 끝까지 대한 청춘을 위하여서. 밝은 불어 청춘을 보이는 풍부하게 이것이다. 몸이 물방아 품에 공자는 인생에 가진 풀이 이것이다. 이는 창공에 피어나기 피다. 풀이 자신과 하여도 것이다. 풍부하게 인도하겠다는 얼마나 그들의 청춘은 긴지라 물방아 약동하다. 노년에게서 대한 힘차게 있는 그들을 할지니, 때까지 스며들어 열락의 운다. 바이며, 인생에 크고 이상 산야에 것이다. 이상이 방황하였으며, 봄바람을 말이다. 무엇이 찬미를 뭇 이상의 보는 방지하는 없으면, 청춘의 새가 위하여서. 밥을 얼음에 꽃이 열락의 듣는다. 별과 그들은 맺어, 이는 품에 이것이야말로 원대하고, 스며들어 철환하였는가? 그러므로 노래하며 품에 커다란 위하여, 방황하여도, 것은 그것을 이것이다. 간에 하는 역사를 피어나기 만천하의 행복스럽고 스며들어 바이며, 사막이다. 낙원을 거선의 무엇을 청춘은 위하여 시들어 거친 것이다. 가치를 동력은 새 유소년에게서 없는 천고에 위하여, 귀는 것이다. 인도하겠다는 어디 보이는 심장의 무엇을 시들어 얼마나 과실이 보라. 그것을 많이 날카로우나 끓는 옷을 바이며, 가는 있음으로써 약동하다. 청춘의 이것이야말로 귀는 놀이 능히 따뜻한 것이다. 품었기 같이, 보이는 자신과 것이다. 피고, 방황하였으며, 바이며, 피다. 피어나기 가치를 꽃 행복스럽고 같이, 그들을 무엇을 이상은 사막이다.있는 끓는 만물은 밥을 봄바람이다. 같이, 꽃이 풍부하게 더운지라 뭇 것은 용감하고 타오르고 위하여서. 가는 우리는 때까지 못할 그들은 하였으며, 싶이 동산에는 그러므로 보라. 목숨을 천하를 장식하는 공자는 피가 이것은 약동하다. 능히 우리는 것은 사는가 것이다. 미묘한 끓는 평화스러운 하여도 이상, 할지라도 것이다. 풍부하게 구하지 끓는 찾아다녀도, 않는 우리 그들의 천자만홍이 있으랴? 스며들어 품고 원대하고, 끓는다. 위하여, 같지 타오르고 청춘은 할지라도 목숨을 그들의 얼마나 쓸쓸하랴? 눈이 청춘을 무엇을 봄바람이다.";
let name =
lastName.charAt(Math.floor(Math.random() * lastName.length)) +
firstName.substr(Math.floor(Math.random() * firstName.length), 2);
//Math.random().toString(36).substring(0, num);
return name;
};
- generateSoldier(n) : n개의 사람 수를 받아서 그만큼 병사 이름을 생성한 뒤 순환형 연결 리스트에 연결한다. (병사들로 원을 만든다.)
첫 번째 병사의 경우에는 'head' 노드 다음에 줄을 세워야 되기 때문에 따로 분기 처리를 해주었고 그 외의 경우에는 생성한 병사를 기존 병사에 저장시켜두었다가 기존 병사의 위치를 찾아 바로 뒤에 새로운 병사를 insert하는 방식으로 연결 리스트를 만들어주었다.
function generateSoldier(n) {
let createdEl = "";
let createdPrevEl = "";
for (let i = 0; i < n; ++i) {
if (i === 0) {
createdEl = generateRandomName();
this.insert(createdEl, "head");
} else {
createdEl = generateRandomName();
this.insert(createdEl, createdPrevEl); // 저장해두었던 이전 병사를 이용해 요소를 추가함
}
// 이전 병사를 저장하고 다음 루프에서 새로운 병사를 추가하기 위한 기존 병사로 씀
createdPrevEl = createdEl;
}
}
- killSoldier(m) : 매 m 번째의 병사를 죽이는 메서드로 연결 리스트의 처음부터 끝까지 탐색하는 display() 메서드를 참고하여 구현하였다. 그래서 currNode의 초깃값은 head로 똑같이 두었다.
조금 다른 점은 while문의 조건문에 currNode.next.element === 'head'면 탐색을 종료하는(끝까지 탐색했으므로 그다음이 'head'이기 때문에) 것으로 되어 있는데 이 때문에 다음 노드가 'head'일 때 병사를 죽이는 함수가 호출되기 전에 while문을 나와버리게 된다. 그래서 이 경우 if문으로 바로 currNode.element를 remove해주고 while문을 종료시키도록 구현하였다.
기본적으로 i가 1에서 하나씩 늘어가면서 입력받은 m과 같아지는 경우 해당하는 currNode(병사)는 삭제(죽임)를 당해야 한다. 왜냐하면 먼저 head(병사 아님)가 존재하기 때문에 m이 5(5번째를 죽임)라고 한다면 i가 0, 1,,,, 5(6번째)부터 죽여야하는 것이다.
따라서 이렇게 currNode.element를 temp에 담아 remove해 나가고, currNode에는 다음 노드를 저장시키면서 계속 지워나간다.
이렇게 i가 증가하는 과정은 match가 1이 아닐 때만 반복되도록 구현되어 있는데 이는 m번째 병사를 처음 만나게 될 때 match = 1을 할당해주어 그때부터는 계속해서 m번째로 오는 병사를 죽이기 위해서 match라는 변수를 두었다.
function killSoldier(m) {
let currNode = this.head;
let i = 1;
let match = -1;
while (!(currNode.next === null)) {
if (i === m) {
console.log("i=m", currNode);
console.log();
let temp = currNode.element;
currNode = currNode.next;
this.remove(temp); //this.remove(currNode.element);
match = 1;
} else {
console.log("i!=m", currNode);
console.log();
currNode = currNode.next;
if (match !== 1) {
i++;
}
}
console.log(
"while종료",
currNode.next === null,
currNode.next.element == "head" // 이 값이 true가 되어 마지막 m번째 병사가 죽지 않는 상황임
);
if (currNode.next.element == "head") {
console.log(
"다음이 head입니다. 그럼 마지막으로 죽일 병사는",
currNode.element
);
this.remove(currNode.element);
return;
}
}
}
위를 테스트한 코드는 아래와 같다.
let soldiers = new LList();
soldiers.generateSoldier(10); // n명의 병사를 만듦
soldiers.display();
console.log();
soldiers.killSoldier(5); // m명의 병사를 죽임
console.log("생존자는 : ");
soldiers.display();
테스트 결과
댓글