본문 바로가기

Programming310

그래프 Graph 리스트와 스택, 큐는 1:1 구조의 자료구조, 트리는 1:다의 자료구조였습니다. 그렇다면 다:다 관계를 가진 자료구조도 존재할 것 같다는 생각이 듭니다. 그래프는 이처럼 다:다의 관계를 가진 자료구조 입니다. 1. 그래프 지하철 노선도 처럼 한 역에서 찍어서 다른 역에 도달하는 방법까지는 수많은 방법이 있습니다. 그리고 한 역은 하나의 역만 연결될 수도 있고 수많은 역과 연결되어 있을 수도 있습니다. 이 지하철 노선도가 그래프를 가장 잘 나타내주고 있습니다. 그래프는 다:다의 관계를 가진 정점과 간선으로 이루어진 자료구조입니다. 정점은 객체(Vertex)를 나타내고 간선(Edge)은 객체끼리의 연결을 의미합니다. 이때 그래프 G는 G=(V, E)와 같은 형태로 정의합니다. 간선 V는 객체i와 2. 그래프.. 2021. 10. 4.
힙 Heap 힙(Heap) 혹은 히프는 완전 이진 트리 종류 중 하나 입니다. 히프는 여태까지 트리를 계속 해서 연결 자료구조로 구현한 것과는 다르게 1차원 배열을 이용해서 구현할 수 있는 자료구조 이기도 합니다. 1. 힙 Heap 힙은 이진 트리의 노드들 중에서 키값이 가장 큰 값또는 가장 작은 값을 찾기 위한 자료구조입니다. 이때 가장 큰 값을 찾으면 최대 힙, 가장 작은 값을 찾으면 최소 힙이라고 합니다. 또 다른 특징은 힙은 같은 키값을 가진 노드를 가질 수 없다는 점 입니다. 그래서 최대 힙에서는 가장 큰 키값을 가진 노드가 루트 노드가 되고, 최소 힙에서는 가장 작은 키값을 가진 노드가 루트 노드가 됩니다. 힙을 1차원 배열로 구현하기 때문에 배열의 인덱스를 통해 트리간의 부모 자식관계를 쉽게 알 수 있다.. 2021. 10. 2.
프록시 패턴 Proxy Pattern 프록시(Proxy)는 '대리'라는 의미를 가지고 있습니다. 지금까지 배웠던 패턴들의 내용이 이름을 따라서 동작했으므로 우리는 프록시 패턴도 무언가를 대리하는 패턴임을 알 수 있습니다. 1. 프록시 패턴 소개 프록시 패턴은 실제 시능을 수행하는 객체를 대신해서 프록시 객체가 기능을 대신 수행해 주는 패턴입니다. 그런데 뭔가 대리로 기능을 수행하는 경우가 잘 떠오르지는 않습니다. 우리는 프록시 객체를 다음과 같은 두 가지 상황에서 이용하게됩니다. 실제 기능을 하는 객체가 자원을 많이 소모하는 경우 실제 객체에 대해서 접근 제어가 필요한 경우 2. 프록시 패턴 구현 프록시 패턴은 간단하게 뼈대만을 가지고 구현해 보겠습니다. 개인적으로 예를 들어서 구체적으로 설명을 처음 들었을 때 긴가민가 했던 경험이 있어서 .. 2021. 10. 2.
[Javascript] 웹 스토리지 Web Storage DB 공부를 하다가 문득 생각해 봅니다. 웹 개발을 하다가도 잠깐 저장하고 싶은 정보가 있는데 그럴때마다 DB를 연동하고 서버를 켜두는 것은 굉장한 낭비가 될거같은데 어디다 저장해야하지? 하는 생각에 찾아보니까 스토리지(Storage)라는 기술이 존재하고 있었습니다. 1. 웹 스토리지 사실 웹에서 정보를 저장해 두는 수단엔 대표적으로 '쿠키'라는 것이 존재합니다. 하지만 이 쿠키는 크기가 매우작고 네트워크 통신이 필요하기에, 쿠키의 최대 크기(약 4KB)보다 큰 정보를 담거나, 네트워크 통신이 필요하다면 사용하는데 문제가 발생합니다. 무엇보다 쿠키는 자바스크립트만으로 조작하는 것이 어렵다는 단점이 있습니다. 그래서 이런점을 보완하기 위해 웹 스토리지를 이용하게 되었습니다. 웹 스토리지는 브라우저에 내장된.. 2021. 10. 2.
AVL 트리 이진 탐색 트리는 트리 구조마다 연산시간이 천차만별입니다. 다음 그림처럼 같은 노드를 가져도 구조에 따라서 연산시간이 다르게 됩니다. 같은 3개의 노드, 같은 요소인데도 8이라는 요소를 탐색 할 때 왼쪽 편향 트리는 노드를 2번 거치는 연산을 하고, 오른쪽 그림의 이진 트리는 오른쪽으로 한 번 이동하는 연산만을 수행하면 됩니다. 이처럼 노드가 늘어날수록 그 차이가 커집니다. 이처럼 노드가 늘어나서 불균형해질수록 이진 트리의 연산횟수가 증가하는 단점이 있는데, 이 단점을 보완한 트리를 균형 이진 탐색 트리 혹은 균형 트리라고 합니다. 이 균형 트리에는 B 트리, AVL 트리 2-3-4 트리 등이 있는데 오늘은 이 중에서 AVL 트리에 대해서 알아보려고 합니다. 1. AVL 트리 Adelson-Velskii.. 2021. 10. 1.
이진 탐색 트리 처음에 트리를 소개하며 조직도이야기를 했듯이, 트리라는 자료구조는 어떤 자료를 찾는데 이점을 갖는 구조입니다. 하지만 트리의 높이가 높아지면 탐색하는데 오래걸리거나, 위치를 안다고 해도 도달하는데 연산이 필요합니다. 그래서 우리는 트리를 특정 기준으로 나누어서 만들려고 합니다. 이것이 이진 탐색 트리입니다. 1. 이진 탐색 트리 이진 탐색 트리는 트리를 실제로 사용하기 위해 정의한 구조입니다. 이때 특정 기준에 따라서 트리 노드를 정렬하는데 보통 노드의 원소 크기를 기준으로 정렬합니다. 이때 노드의 원소를 우리는 키(key)라고 부르고, 이 값에 따라 탐색 등의 연산을 실행하게 됩니다. 우리는 종종 업앤 다운 게임을 합니다. 특정 숫자를 부르고 이 숫자보다 특정 숫자가 크면 업, 작으면 다운이라고 말하죠.. 2021. 9. 30.
300x250

티스토리툴바