Daehyunii's Dev-blog

이번주 부터는 자료구조에 대해서 공부를 하기 시작했다. 자료구조라는 말을 공부를 시작한 이유로 많이 듣게 되었는데 정확하게 확 와닿지는 않았었다. 단어 그대로 자료들을 저장하는 구조라는 것이었는데, 자바스크립트를 공부할때 자료를 저장하는 방법은 배열이나 객체리터럴 등을 통해서 저장을 한다고만 생각하고 있었고 그게 거의 전부라고 생각하는 좁은 시야를 가지고 있었던 것 같다. 하지만 자료 구조를 공부하기 시작하고 나서는 자료들을 어떻게 저장하는지에 따라서 상황에 따라 정말 많은 차이가 존재할 수 있다는 것을 알게 되었다. 단순히 자료를 인덱스 없이 객체의 프로퍼티로 연결해서 처음과 끝만 저장해서 활용하는 단일 연결 리스트와 이중 연결 리스트 또 자료를 어떻게 활용할지에 대해서 먼저 들어온 자료를 먼저 빼는 ..

오늘 공부한 내요은 이진 힙과 해시 테이블이다. 이진 힙은 트리의 한 유형인 힙의 한 유형이다. 이진 힙도 트리의 규칙을 가지고 추가적인 규칙을 갖는다. 이진 힙의 규칙은 간단하다. 부모 노드는 자식 노드 보다 항상 큰 값을 갖거나(최대 이진 힙) 반대로 항상 작은 값을 갖는다.(최소 이진 힙) 또한 자식 노드는 최대 2개를 가질 수 있는데 자식 노드들 사이의 위치는 우선순위가 없이 항상 왼쪽 부터 저장이 된다. 그렇기 때문에 이진 힙은 배열로 표현이 되며, 간단한 수학적 규칙을 활용해서 자료를 저장하게 된다. 그렇기 때문에 이진 힙의 루트 노드에는 항상 가작 큰 값이 오거나 가장 작은 값이 오게 된다. 이러한 점을 활용해서 우선 순위 큐를 만드는데 활용할 수 있다. 우선 순위 큐는 노드에 우선 순위를 ..

19.1 해시 테이블(해시 맵) 해시 테이블이란 키와 값을 쌍으로 저장하는 자료 구조를 말한다. 많은 프로그래밍 언어에 내장되어 있는 자료 구조이다. python은dictionaries, Java Script는 Object와 Maps, Java는 Go, Scala 그리고 Maps, Juby는 Hashes로 알려져 있다. 이 처럼 언어마다 해시 테이블이 내장되어 있고 해시 테이블은 추상적인 개념이기 때문에 여러 가지 방법으로 코딩할 수도 있다. 해시 테이블은 일반적인 배열과는 다르다. 배열은 인덱스를 가지지만 해시 테이블은 순서를 가지지 않는다. 해시 테이블이 좋은 이유는 새로운 값을 추가하거나 제거하는데 아주 빠르고 데이터 그 자체가 해시 테이블 방법에 따라 저장되는 것이 편한 경우가 많다. 19.2 해..

18.1 이진 힙 이진 힙은 이진 검색 트리와 마찬가지로 트리의 한 종류이다. 그러므로 트리에 적용되는 규칙들이 다 동일하게 적용되지만 추가적으로 적용되는 규칙들이 있다. 힙에도 여러가지 종류가 있지만 지금 알아 볼 내용은 힙의 한 종류인 이진 힙이다. 이진 힙은 다시 최소 힙과, 최대 힙으로 구분된다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 자식 노드로 저장되는 왼쪽/오른쪽의 순서는 상관없이 한 레벨 아래에 있는 즉, 자식 노드보다는 항상 부모 노드가 크다.(오른쪽/왼쪽 순서는 중요하지 않고 데이터를 저장할 때 왼쪽부터 값이 저장된다.) 최소 이진 힙은 최대 이진 힙과 반대로 부모 노드는 항상 자식 노드보다 작은 값을 가진다. 자식 노드로 저장되는 왼쪽/오른쪽의 순서는 마..

17.1 트리 순회 트리 순회는 말 그대로 어떤 트리에서든지 사용할 수 있는 개념이다. 예를 들어 이진 탐색 트리든지, 그냥 이진 트리든지 그 외의 어떤 트리들에도 다 사용이 가능한 순회 방법이다. 즉 트리의 특성을 가지고 있다면 트리 순회를 할 수 있다. 트리를 순회하는 방법에는 많은 방법이 존재하고 대표적으로 너비 우선 탐색(Breadth First Search)과 깊이 우선 탐색(Deapth First Search)가 있다. 어떤 탐색 방법이든 모든 노드들을 순회하는 것은 동일하다. 17.2 너비 우선 탐색 너비 우선 탐색(Breadth First Search)은 트리의 같은 레벨에 있는 모든 노드를 거쳐가며 순회를 하는 방식이다. /* 트리) 10 / \ 6 15 / \ / \ 3 8 12 20 ..

오늘은 트리를 순회하는 방법에 대해서 공부했다. 앞서 이진 검색 트리에 대해서 공부했었는데 이진 검색 트리만을 위한 검색 방법이 아닌 트리형태의 자료 구조들을 전부 순회할 수 있는 대표적인 방법들에 대해서 공부했다. 오늘 공부하는 것은 개념적으로는 크게 어렵지 않았으나, 코드를 이해하는데 시간이 꽤 걸렸다. bfs방식은 루트 노드부터 시작해서 같은 레벨에 존재하는 모든 노드들을 먼저 순회한 후 또 다시 그 아래에 위치하는 노드들을 검색하는 방식이고 dfs방식은 루트 노드부터 시작해서 자식 노드로 또 그 노드의 자식 노드로 순회를 이어가면서 탐색하는 방법이다. dfs방식에는 다시 전위, 후위, 중위 방식으로 나뉠 수 있는데 순회한 노드를 마지막에 반환 할 배열에 언제 저장하느냐에 따라 달라지게 된다. 사실..

16.1 트리란? 이진 검색 트리는 이진 트리의 한 종류이고, 이진 트리는 트리 자료 구조의 한 종류이다. 그렇다면 트리란 무엇일까? 트리란, 연결 리스트처럼 노드로 이루어진 데이터 구조이다. 하지만 연결 리스트와 다르게 부모-자식 관계를 가진다. 리스트는 선형 자료 구조이다. 말 그대로 하나의 줄로 이어져 있는 것처럼 보인다. 하지만 트리는 여러 갈래의 줄로 연결될 수 있기 때문에 비선형 자료 구조이다. 주의해야 할 점은 노드들이 자신보다 더 낮은 곳에 있지 않은 다른 노드를 가리키는 경우에는 트리 자료 구조가 아니다. 즉, 노드가 형제 노드를 가리키는 경우, 자식이 부모를 가리키는 경우에는 트리 자료 구조가 아니다. 트리에서는 모든 노드들이 루트노드에서 멀어지는 방식으로 연결된다. 루트는 하나이어야 ..

15.1 스택(Stack) 스택이란 후입선출 원칙을 따르는 데이터 구조를 일컫는 말이다. 즉, 나중에 들어온 데이터가 먼저 제거되는 방식의 자료 구조를 스택이라고 말한다. 설거지를 하기 위해 싱크대에 쌓인 그릇 중 가장위에 있는 그릇을 하나씩 설거지해 나간다고 생각하면 쉽다. 스택을 코딩하는 방법은 여러가지가 있고 연결 리스트를 사용해서 구현할 수도 있다. 즉, 스택이라는 개념은 후입선출 원칙을 지키는 자료 구조들을 말하는 추상적인 개념이다. 15.2 배열로 스택 구현하기 배열을 만들고 해당 배열에 데이터를 추가할 때 push() 메서드를 활용하고, 제거할 때 pop() 메서드만을 사용하거나 shift(), unshift() 메서드만을 사용한다면 배열을 스택으로 사용하는 방법이 된다. 후입선출 원칙을 지..