알고리즘과 자료구조/자료구조 (12) 썸네일형 리스트형 자바스크립트로 구현하는 이진 힙 들어가는 말 | 시간복잡도 그래프와 Big 5이번 시간에는 이진 힙에 대해서 정리해봅니다. 이진 힙은 자료구조 중에서 이진 트리의 한 유형이며 그 중에서도 완전 이진 트리로 불립니다. 완전 이진 트리이므로 보다 삭제, 삽입, 정렬 연산이 쉬운 점이 장점이고, 삽입과 삭제 연산 자체가 log n 시간복잡도를 가지기 때문에, 효율적인 연산이기도 합니다. 예를 들어, 입력 크기가 n일 때, 수행 시간은 log n에 비례하여 증가합니다. 즉, 입력 크기가 두 배가 되면 수행 시간은 log(2n) = log n + log 2로 증가합니다. 이는 두 배가 되는 경우에도 증가폭이 매우 작음을 의미합니다. 아래 시간 복잡도 그래프를 보면 상수 시간복잡도인 O(1) 바로 위에 O(log n) 이 있는 것을 볼 수 있.. [자료구조] 이진탐색트리와 연산 이진탐색트리이진탐색트리는 각 노드에 최대 두 개의 자식을 가지는 것은 이진트리와 같으나, 한 가지 눈에 띄는 차이점이 존재한다. 바로, 부모 노드의 왼쪽 자식 노드는 부모 노드보다 작은 값을 가져야 하고, 오른쪽 자식 노드는 반대로 큰 값을 가져야 한다. 즉, 다음과 같은 형태가 되어야 한다. 이 규칙은 자식 노드를 가지는 모든 부모 노드가 공통적으로 가지는 규칙 이므로 꼭 지켜주어야 한다. 이진탐색 트리 구현 | Node Class이진탐색트리는 연결리스트하고 비교 했을 때 Node 클래스를 가지는 것은 동일하다. 다만, 트리의 Node 클래스는 head 라고 하는 참조 필드가 아닌, 왼쪽 자식 노드를 참조하는 left 와 오른쪽 자식 노드를 참조하는 right 가 있다. 즉, 다음과 같은 형식으로.. [자료구조] 이진(+탐색)트리 전 개요 이번 시간에는 이진트리에 대해 알아보는 시간을 가져보고자 한다. 자세한 메서드 구현 내용보다는 앞으로 정리해 나갈 이진트리에 대한 개요라고 볼 수 있다. 이진 트리 이진트리는 각 노드가 왼쪽 자식과 오른쪽 자식으로 불리는 리프 노드를 갖는 데이터 구조를 의미한다. 이진트리에서 각 노드는 값을 가질 수 있고, 이들은 다시 자신만의 자식 노드를 최대 2개 가질 수 있는 형식으로 아랫 방향으로 뿌리를 넓혀 가는 특징을 보인다. 이진트리 만들기 이진트리의 Node 구조도 앞서 언급한 특성에 맞게 데이터(값), 자식을 참조하는 2개의 포인터를 가지고 있다. 이 포인터들은 부모 노드의 자식 노드가 없는 경우를 가정해서 null 이 기본 할당되고, 존재하는 경우에는 해당 자식 노드를 가리키는 참조를 담게 된다. 따라.. [자료구조] 배열을 이용한 스택과 큐 구현 들어가기 전 앞서 시간 까지는 연결 리스트에 대해서 정리하였고, 이번에는 스택과 큐에 대해서 알아보고 이에 대한 구현을 시도해보고자 한다. 마지막에는 내가 생각하기에 배열을 이용한 경우 생길 수 있는 장단점에 대해 언급하며 끝내고자 한다. 스택과 큐 스택 우선 스택의 경우에는 후입선출(Last In First Out) 의 구조를 지니는데, 마지막에 들어온 요소가 먼저 나가는 특징을 보인다. 흔히 자바스크립트에서 실행 컨텍스트가 쌓이는 구조가 스택 자료구조를 따르며 그래서 이름 또한 호출 스택 ( Call Stack)으로 불린다. 큐 큐를 한 단어로 정리하면 대기줄이다. 보통 영화관 입장이나 놀이공원 입장을 생각해보면 먼저 온 사람이 앞에서 표를 끊고, 늦게 온 사람은 다음 순서를 기다려며 대기하고 있다... 자바스크립트에서 사용되는 주요 배열 메서드의 시간복잡도에 대해서 알아보자? [배경] 자료구조에 대해 공부하다보니 자료구조에 대해 공부하다보니 갑자기 궁금해진 것이 하나 있다. 이 때 까지 당연하게 사용하던 배열 메서드들의 시간복잡도는 어떻게 될까? 내부적인 구현은 숨겨져 있으니 일일이 계산할 수는 없더라도 눈에 보이는 동작만 봤을 때 해당 메서드들이 어떤 시간복잡도를 가지는지 알아보면 재밌을 것 같아서 해당 포스트를 작성해본다. [기초 개념] 시간복잡도에 대한 개념 시간복잡도는 알고리즘이 문제를 푸는데 걸리는 시간을 의미한다. 여기서 시간이란 실제 시간을 의미하기 보다는 연산의 크기를 측정한 값이라고 이해하면 된다. 예를 들어 아주 전통적인 for 문을 사용하여 배열을 순회한다고 가정할 때, 이 때 배열의 길이인 n 이 증가할 때 마다 순회 하는데 필요한 연산의 횟수도 증가하게.. [자료구조] 이중연결리스트 remove 함수(메서드) 만들기 들어가기 전 이제 이중연결리스트의 remove 함수 구현에 대한 부분까지 도전하는 시기가 되었다. 사람들은 연결리스트가 쉬운 자료구조라고 하는 것 같은데, 내가 보기에는 참조 관계를 이어주고 끊어주는 것 부터, 리스트의 특정 위치에 노드를 추가함으로써 생기는 여러 문제들을 해결하는게 그리 쉬운 것 같지는 않다. 계속 뜯어보고, 원리를 생각하며 공부해보니 조금씩 해당 자료구조의 필요성과 이점, 단점 등이 보이기 시작하고 있는데, 이것이 구현 능력으로 이어지기 위해서는 꾸준히 노력해야 함을 인지하고 들어가 본다. 이중 연결리스트에서 노드를 제거하려면? 이중 연결리스트에서 노드를 제거하는 방법은 첫 번째 노드를 제거하거나, 마지막 노드를 제거하거나, 아니면 중간에 있는 노드를 제거하는 등 응용에 따라서 다양하.. [자료구조] 이중 연결 리스트, Add 함수 구현까지 이중연결리스트? 어감에서 알 수 있듯이 이중으로 참조 포인터가 연결되어 있는 노드를 가지는 리스트를 의미한다. 따라서 각 노드들은 값과 함께 이전 노드에 대한 참조와 다음 노드에 대한 참조를 가지며, 이러한 특징으로 인해 정방향과 역방향 모두에서 순회할 수 있다. 이런 점에서 보면 단일 연결리스트에 비해 참조 포인터를 하나 더 가짐으로써 메모리 공간을 더 사용한다는 단점이 있지만, 그것보다 이득이 더 커보이는 것 같다. 이중 연결리스트 이전에는.. 이중연결 리스트 이전에 단일 연결리스트가 있다. 단일 연결리스트를 구현해보면서 느꼈던 큰 단점은 횡단으로만 이동이 가능하여 검색이나 식제 등의 기능에 있어서 유연성이 많이 부족하다는 점이었다. 반면에, 이중 연결리스트의 경우에는 이전 노드에 대한 참조와 다음 .. [자료 구조] 여기 까지 구현해본 단일 연결 리스트의 장점과 단점에 대한 생각 단일 연결 리스트를 구현해보면서 느낀 장점과 단점 배열과 비교했을 때는 이런게 장점인 것 같다. 일단 본인이 판단하기로 단일 연결 리스트의 장점은 배열과 달리 연속적인 메모리 공간 할당을 필요로 하지 않기 때문에, 메모리 관리 측면에서 매우 효율적이라는 생각이 들었다. 또한, 노드의 추가 및 삭제, 검색, 조회 등에 있어서도 일반적인 배열에 비해서, 참조관계를 바탕으로 노드를 순회하며 찾아가면 되기 때문에, 비번한 삽입 및 삭제가 반복되는 상황에서는 배열 보다 더 활용하기 좋아보였다. 자바스크립트에서 기본적으로 사용되는 arr =[ ] 의 경우에는 배열의 앞 부분에 요소를 추가하게 되면, 각 요소들이 메모리 공간을 연속적으로 할당받아 사용하므로 기존의 요소들이 새요소로 인해서 한 자리씩 뒤로 밀리게 되는.. 이전 1 2 다음
