\(@^0^@)/

[TDL] 07/21 Today's-Done-List 본문

TDL

[TDL] 07/21 Today's-Done-List

minjuuu 2022. 7. 22. 00:23
728x90

- 유데미 알고리즘 단일 연결 리스트

get 메서드
get메서드는 인덱스 혹은 위치를 의미하는 수를 인자로 받아서 주어진 위치에 있는 노드를 반환하는 메서드.

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    
    get(index){
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
}

let list = new SinglyLinkedList()

list.push("HI")
list.push("THERE")
list.push("!!!")
list.push("HOW")
list.push("ARE")
list.push("YOU")
list.push("?")

get메서드가 제대로 작동하는지 확인하기 위해서, push메서드만 추가하였음.

set 메서드
set메서드는 (1) 위치 혹은 인덱스, (2) 해당 인덱스에 위치한 노드를 업데이트할 값 등 두 개의 인자를 받는다.

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    
    get(index){
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
    
   set(index, val) {
       let foundNode = this.get(index);
       if(foundNode) {
           foundNode.val = val;
           return true;
       }
       return false;
   }
}

let list = new SinglyLinkedList()

list.push("HI")
list.push("THERE")
list.push("!!!")
list.push("HOW")
list.push("ARE")
list.push("YOU")
list.push("?")

list에 존재하지 않는 index에 set메서드를 추가할 경우, false가 반환된다.

insert 메서드
새로운 node를 하나 생성하여, get메서드를 통해 원하는 위치 혹은 인덱스에 리스트를 추가한다.

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
    
    get(index){
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
    
    insert(index, val) {
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        var newNode = new Node(val);
        var prev = this.get(index -1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
}

let list = new SinglyLinkedList()

list.push("HI")
list.push("THERE")
list.push("!!!")
list.push("HOW")
list.push("ARE")
list.push("YOU")
list.push("?")

 

insert메서드를 작동시켜서 리턴 값으로 list를 받기보다, 깔끔하게 true 또는 false를 리턴 받고 싶을 경우,
조건문에 이중 부정 연산자를 추가하여, push 또는 unshift메서드를 사용해서 val을 추가할 경우 true를 리턴해준다.

newNode, prev, temp이라는 변수를 생성하여 newNode에는 새로운 node를 할당하고,
prev에는 기존의 리스트에서 내가 insert를 하고 싶어 하는 인덱스의 이전 인덱스를 넣어준다. (리스트를 연결하기 위해)
temp에는 prev의 next를 넣어줌으로써, 현재 insert를 원하는 인덱스의 앞 뒤 node들을 다 변수에 저장한 셈.

a) prev는 기존 리스트의 이전 인덱스
b) prev의 next로 새로운 node를 넣고,
c) 새로운 node의 next로 insert를 원하는 기존 리스트의 앞 인덱스를 넣는다.
이렇게 해주면 a -> b -> c 가 제대로 연결된다. node가 하나 더 생겼으므로, length++를 해주자.

remove 메서드
기존의 node를 제외하고, 제거하고 싶은 node의 앞 뒤 리스트들을 서로 연결한다.

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    
     pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    
    get(index){
        if(index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while(counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
    
    remove(index) {
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length -1) return this.pop();
        let prevNode = this.get(index -1);
        let removed = prevNode.next;
        prevNode.next = removed.next;
        this.length--;
        return removed;
    }
}

let list = new SinglyLinkedList()

list.push("HI")
list.push("THERE")
list.push("!!!")
list.push("HOW")
list.push("ARE")
list.push("YOU")
list.push("?")

prevNode, removed 변수를 생성해서
prevNode에는 제거하고 싶은 리스트의 이전 리스트를 담고, removed에는 제거하고 싶은 리스트를 담아둔다.
제거하고 싶은 리스트를 제외시키기 위해서 prevNode의 next에 removed.next를 할당한다.
즉, 제거하고 싶은 리스트의 이전 리스트의 next를 제거하고 싶은 리스트의 next로 연결하면서 자연스레 제거하고 싶은 리스트가 빠지는 것.

a) prevNode : 제거하고 싶은 리스트의 이전 리스트
b) removed : 제거하고 싶은 리스트
c) 제거하고 싶은 리스트의 다음 리스트
현재 a -> b -> c로 되어 있는데 b를 제외하기 위해서, a의 next를 c로 연결한다. a -> c
이렇게 될 경우 b는 연결되지 못했기에 자연스럽게 제외된다.

reverse 메서드
연결 리스트 방향을 반대 방향으로 바꾸는 메서드

우선 reverse 메서드가 제대로 된 방향으로 작동하는지 알아보기 위해서 리스트에 있는 노드들을 순서대로 print 하는 메서드를 만들어보자.

print() {
    let arr = [];
    let current = this.head;
    while(current){
        arr.push(current.val)
        current = current.next
    }
    console.log(arr);
}

위에 removed메서드에서 작성했던 리스트들을 print 해보면 아래와 같이 나온다.

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    
    reverse() {
        let node = this.head;
        this.head = this.tail;
        this.tail = node;
        let next;
        let prev = null;
        for( let i = 0; i < this.length; i++){
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return this;
    }
    
    print() {
        let arr = [];
        let current = this.head;
        while(current){
            arr.push(current.val)
            current = current.next
        }
    console.log(arr);
    }
    
}

let list = new SinglyLinkedList()

list.push("HI")
list.push("THERE")
list.push("!!!")
list.push("HOW")
list.push("ARE")
list.push("YOU")
list.push("?")

은근히 헷갈리므로, 간단하게 예를 들어보자.
[aaa, bbb, ccc, ddd, eee]
node

for문
[aaa, bbb, ccc, ddd, eee]
prev  node
aaa -> null
======================
for문
[aaa, bbb, ccc, ddd, eee]
                 next
bbb -> aaa -> null
         prev
                  node
======================
for문
[aaa, bbb, ccc, ddd, eee]
                         next
ccc -> bbb -> aaa -> null
                 prev
                         node
======================
for문
[aaa, bbb, ccc, ddd, eee]
                                next
ddd -> ccc -> bbb -> aaa -> null
                         prev
                                 node
======================
for문
[aaa, bbb, ccc, ddd, eee]
                                          next
eee -> ddd -> ccc -> bbb -> aaa -> null
                                prev
                                          node
======================
eee -> ddd -> ccc -> bbb -> aaa -> null

- 제로베이스 JS 프로젝트 강의

이미지 에디터 만들기

https://dev-minju.tistory.com/279

오후 회고 (만족도: 8)

오늘 자료구조 학습도 그렇고, js 프로젝트 강의도 그렇고 학습하는데 시간이 많이 요소 되는 강의들이었다..
특히 js프로젝트를 붙잡고 있느라고, react 강의는 듣지 못하였지만 그래도 많은 부분을 배운 것 같아서 만족도는 8점.
하지만 계속 이런 식으로 react강의가 미뤄지는 것 같아서 조치를 취해야 할 것 같음.

- 인프런 함수형 프로그래밍 강의

_pipe함수 : 함수를 리턴하는 함수

let slice = Array.prototype.slice;
function _rest(list, num) {
  return slice.call(list, num || 1);
}

function _each(list, iter) {
  for(let i = 0; i < list.length; i++) {
    iter(list[i]);
  }
  return list;
}

function _reduce(list, iter, memo) {
  if (arguments.length == 2) {
    memo = list[0];
    list = _rest(list);
  }
  _each(list, function(val) {
     memo = iter(memo, val);
  });
  return memo;
}
function _pipe() {
    let fns = arguments;
    return function(arg) {
        return _reduce(fns, function(arg, fn) {
            return fn(arg);
        }, arg);
    }
}

let f1 = _pipe(
    function(a) { return a + 1 },
    function(a) { return a + 2 },
    function(a) { return a * a });
    
console.log( f1(1) );    // 16

_go함수 : 첫 번째 인자로는 인자를 받고, 두 번째 인자부터는 함수들을 받아서 결과를 바로 만드는 함수
go는 pipe의 즉시 실행 버전.

let slice = Array.prototype.slice;
function _rest(list, num) {
  return slice.call(list, num || 1);
}

function _each(list, iter) {
  for(let i = 0; i < list.length; i++) {
    iter(list[i]);
  }
  return list;
}

function _reduce(list, iter, memo) {
  if (arguments.length == 2) {
    memo = list[0];
    list = _rest(list);
  }
  _each(list, function(val) {
     memo = iter(memo, val);
  });
  return memo;
}
function _pipe() {
    let fns = arguments;
    return function(arg) {
        return _reduce(fns, function(arg, fn) {
            return fn(arg);
        }, arg);
    }
}

function _go(arg) {
    let fns = _rest(arguments);
    return _pipe.apply(null, fns)(arg);
}

_go(1,
    function(a) { return a + 1 },
    function(a) { return a + 2 },
    function(a) { return a * a });    // 16

_map,_filter를 사용해 user의 데이터를 추출했던 방식을 _go함수를 통해 선언형으로 바꿔보자.

function _each(list, iter) {
	for (let i = 0; i < list.length; i++) {
		iter(list[i]);
	}
	return list;
}

function _filter(list, predi) {
	let new_list = [];
	_each(list, function (val) {
		if (predi(val)) new_list.push(val);
	});
	return new_list;
}

function _map(list, mapper) {
	let new_list = [];
	_each(list, function (val) {
		new_list.push(mapper(val));
	});
	return new_list;
}

let slice = Array.prototype.slice;
function _rest(list, num) {
	return slice.call(list, num || 1);
}

function _reduce(list, iter, memo) {
	if (arguments.length == 2) {
		memo = list[0];
		list = _rest(list);
	}
	_each(list, function (val) {
		memo = iter(memo, val);
	});
	return memo;
}

function _curryr(fn) {
	return function (a, b) {
		return arguments.length == 2
			? fn(a, b)
			: function (b) {
					return fn(a, b);
			  };
	};
}

let _get = _curryr(function (key, obj) {
	return obj === null ? undefined : obj[key];
});

function _pipe() {
	let fns = arguments;
	return function (arg) {
		return _reduce(
			fns,
			function (arg, fn) {
				return fn(arg);
			},
			arg,
		);
	};
}

function _go(arg) {
	let fns = _rest(arguments);
	return _pipe.apply(null, fns)(arg);
}

_map(
	_filter(users, function (user) {
		return user.age >= 30;
	}),
	function (user) {
		return user.name;
	},
);

_go(
	users,
	function (users) {
		return _filter(users, function (user) {
			return user.age >= 30;
		});
	},
	function (users) {
		return _map(users, _get("name"));
	},
	console.log,
);

이제까지 학습했던 함수들이 총출동하였다.. 아직 완벽하게 숙지가 안되어 있기 때문에 복습을 많이 해야 할 것 같다.
강의에서 코드를 더 간결하게 작성하였는데, 따라 하는 순간 에러 폭탄이라 결국 해결하지 못하였다.
저 강의가 ES5인데, ES6로 공부해야 될 것 같아서 이번 섹션까지만 듣고 할인할 때 결제한 후 다시 들을 예정.

저녁 회고 (만족도: 7)

오늘 만족도는 나쁘지 않았지만, 조금만 더 빨리 오면 좋을 것 같음.

[ 출처 : JavaScript 알고리즘 & 자료구조 마스터클래스 ]

728x90
저작자표시

'TDL' 카테고리의 다른 글

[TDL] 07/24 Today's-Done-List  (0) 2022.07.24
[TDL] 07/22 Today's-Done-List  (0) 2022.07.23
[TDL] 07/20 Today's-Done-List  (0) 2022.07.21
[TDL] 07/19 Today's-Done-List  (0) 2022.07.19
[TDL] 07/18 Today's-Done-List  (0) 2022.07.18
'TDL' Related Articles more