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