자료구조와 알고리즘 (12) 썸네일형 리스트형 알고리즘 문제를 쉽게 해결할 수 있도록 해주는 5가지 단계 udemy에서 인기 있는 강의 내용을 정리해 보았다. 1. Understand Problem 코딩에 들어가기 전에 문제를 명확히 이해하는 게 중요하다. 체크리스트 - 문제를 내 언어로 바꿔서 표현할 수 있는지 이해를 했는지 확인하기 위해서 - input이 무엇인지 - output은 어때야 하는지 - input을 이용해서 output을 뽑아낼 수 있는지? 혹은 뽑아낼 수 있는 정보를 갖고 있는지? 이는 당장에 답을 하지 못 할 수도 있다. - 주요 데이터를 어떻게 정의해야 할지 예) 두 숫자를 받아서 더한 값을 return 하는 함수 - 문제를 내 언어로 바꿔서 표현할 수 있는지 덧셈 구현 - input이 무엇인지 두 숫자인지, int의 범위를 넘어야 하는지, float인지, number 타입만 처리해야 .. 크롬 콘솔에서 알고리즘의 성능을 테스트하는 방법 구현한 함수 또는 알고리즘의 속도가 얼마나 나오는지를 테스트하려면 다음과 같이 performance 객체를 이용한다. function addUpTo(n) { let total = 0; for (let i = 1; i 자바스크립트를 예제로 하는 자료구조와 알고리즘 6 - 해시 테이블(Hash Tables) 자바스크립트에서 해시 테이블은 바로 객체다. (자바에서는 HashMap, 파이썬과 C#에서는 Dictionary라고 부른다.) 엄청 빠른 속도를 자랑하기 때문에 두루두루 쓰인다. const object = { 1: '가', 2: '나', 3: '다' } 해시 테이블은 데이터를 저장할 때 key와 value를 한 쌍으로 한다. 해시 테이블이 key를 받아 Hash Function에 통과 시키면 Hash Function은 value를 메모리 상 어디에 저장할지 알려준다. 마찬가지로 데이터를 가져올 때에도 해시 테이블이 key를 받아 Hash Function을 거쳐 key에 해당하는 value의 위치를 찾아 value를 반환한다. Hash Function은 이렇듯 같은 인풋을 넣으면 같은 아웃풋을 보장하는 특.. 자바스크립트를 예제로 하는 자료구조와 알고리즘 5 - 큐(Queue) 큐는 프린터를 생각하면 쉽다. 모든 페이지를 동시에 인쇄할 수 없다. 먼저 들어온 페이지가 다 인쇄될 때까지 기다리는 시간이 필요하고 이를 큐로 구현할 수 있다. 첫 번째로 들어온 게 첫 번째로 나가는 FIFO(First In First Out) 구조다. 스택과 마찬가지로 큐를 구현하기 위한 메소드도 많지 않다. enqueue는 큐의 뒤쪽부터 데이터를 넣는다. dequeue는 가장 먼저 들어온 큐의 앞쪽 데이터를 꺼내서 확인하고 없애는 메소드다. peek는 dequeue와 유사하다. 큐의 앞쪽 데이터를 확인할 뿐이지 없애지는 않는다. isEmpty는 스택이 비었는지 확인한다. isFull은 스택이 꽉 찼는지 확인한다. 배열의 길이가 고정적이지 않은 자바스크립트에서는 별 의미가 없을 것 같다. (배열의 길.. 자바스크립트를 예제로 하는 자료구조와 알고리즘 4 - 스택(Stack) 스택은 책을 하나씩 쌓아 올리고 내리는 것과 비슷하다. 스택에 데이터를 넣을 때에는 마지막에 넣었던 데이터 위에 쌓는다. 반대로 데이터를 꺼낼 때에는 가장 위쪽에 있는 마지막에 넣었던 데이터부터 가져온다. LIFO(Last In First Out)를 기억하자. 마지막에 넣었던 것이 첫 번째로 나가는 구조다. 워낙 간단해서 다음 메소드만 구현하면 활용할 수 있고 자바스크립트는 배열의 내장 메소드를 이용하면 쉽다. push는 스택에 데이터를 쌓는 메소드다. pop은 스택의 가장 위에 있는 데이터를 꺼내서 확인하고 없애는 메소드다. peek는 pop과 유사하다. 스택의 가장 위에 있는 데이터만 확인할 뿐이지 없애지는 않는다. isEmpty는 스택이 비었는지 확인한다. 위 메소드의 시간 복잡도는 모두 O(1)이.. 자바스크립트를 예제로 하는 자료구조와 알고리즘 3 - 링크드 리스트(Linked List) 링크드 리스트는 노드 한 쪽에 값을 넣고 다른 한 쪽에는 다음 데이터의 위치를 참조할 수 있는 주소 값을 넣어 꼬리를 물고 이어지는 자료구조다. head에는 시작하는 노드의 주소를, tail에는 끝나는 노드의 주소를 넣어 링크드 리스트에 값을 추가 하거나 삭제할 수 있게 해준다. Lookup 링크드 리스트의 특정 값을 찾기 위해서는 head부터 시작해서 원하는 값이 나올 때까지 지속해야 한다. 때문에 최악의 경우 O(n)의 시간 복잡도가 나올 수 있다. Insert 링크드 리스트에 노드를 추가하기 위해서는 최악의 경우 tail이 참조하는 노드 바로 전의 노드까지 head를 타고 들어와야 하므로 O(n)의 시간 복잡도가 나온다. 제일 앞에 추가하는 경우 새로운 노드를 head가 가리키던 노드를 가리키게 하.. 자바스크립트를 예제로 하는 자료구조와 알고리즘 2 - 배열(Array) 자바스크립트의 배열은 객체다. 다른 언어의 배열과는 좀 다르다. 아래의 array와 object는 유사한 구조를 띈다. array[0]과 object[0]가 '가'인 것처럼 배열이나 객체나 key와 value가 한 쌍을 이루면서 값이 담겨 있다. 당연히 같지는 않다. (object와 같은 객체를 유사 배열이라고 한다.) const array = ['가', '나', '다']; const object = { '0': '가', '1': '나', '2': '다' } 시간 복잡도 Access 인덱스(key)로 바로 접근할 수 있기 때문에 자료를 조회하는 데 드는 시간 복잡도는 O(1)이다. const array = ['가', '나', '다']; console.log(array[1]) // '나' Appending.. 자바스크립트를 예제로 하는 자료구조와 알고리즘 1 - Big O Big O 알고리즘의 퍼포먼스를 표현하기 위해 사용한다. 괄호 안의 숫자는 inputs의 증가에 따라 연산의 비율이 어떻게 증가하는지를 비율로 나타낸다. O(1) 주어지는 inputs의 길이가 하나든 둘이든 상관없이 언제나 똑같은 퍼포먼스를 내주기 때문에 O(1)으로 표현한다. const inputs = [1, 2, 3]; // O(1) console.log(inputs[0]); console의 개수는 중요하지 않다. inputs에 상관없이 동일한 퍼포먼스를 낸다는 점을 봐야 한다. const inputs = [1, 2, 3, 4, 5, 6]; // O(1) console.log(inputs[0]); console.log(inputs[1]); console.log(inputs[5]); O(n) input.. 이전 1 2 다음
