티스토리

꾸준합니다

검색하기

블로그 홈

꾸준합니다

hy1as.tistory.com/m

hy1as 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

그래프 (3) : 가장 짧은 경로 이번 포스팅에서는 가중 그래프와 최단 거리 찾기에 자주 사용되는 알고리즘에 대해 알아보도록 하겠습니다. 1. 가중 그래프(Weighted graph) 란? 그래프에는 다양한 변형이 존재합니다. 그래프 간선에 정보를 추가하는 가중 그래프 역시 또 하나의 유용한 그래프 유형입니다. 위 그래프와 같이 간선에 비용, 거리 등을 데이터를 부여하여 사용됩니다. 코드로 구현한다면 아래와 같이 구현할 수 있습니다. class WeightedGraphVertex { data; // 배열 대신 해시 테이블 사용하여 가중치 삽입 adjacentVertices; constructor(data) { this.data = data; this.adjacentVertices = new Map() } addAdjacentVertex(.. 공감수 0 댓글수 0 2023. 4. 1.
그래프 (2) : 탐색의 방향? 그래프에서의 탐색은 우리가 일반적으로 알고 있는 자료구조에서 일반적으로 쓰이는 연산으로서의 의미 이외에도 여러 의미와 쓰임새를 가지고 있습니다. 이번 포스트에서는 그 의미와 쓰임새를 알아보고 탐색을 진행하는 방법에는 어떠한 것이 있는지 이야기해 보겠습니다. 1. 그래프에서의 탐색 그래프 용어에서 탐색은 몇가지 의미를 함축하고 있습니다. 단순한 의미로는 특정 정점(vertex)이 어디에 존재하는지 찾는 것입니다. 또 하나는 그래프 내에서 정점에 접근할 수 있을 때 그 정점과 연결된 또 다른 특정 정점을 찾는 것을 의미합니다. 경로(path)라는 용어는 그래프 용어로 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻합니다. 그래프의 탐색은 특정 정점 찾는 것 이외에도 두 정점이 서로 연결되어있는 상태인지 .. 공감수 0 댓글수 0 2023. 3. 30.
그래프 (1) : SNS가 이거에요 이번 포스팅에서는 데이터 간의 관계에 특화된 자료구조인 그래프에 대해서 이야기해 보겠습니다. 1. 그래프란? 그래프는 관계를 표현하는데 특화된 자료구조로서 데이터 간 연결 상태를 쉽게 보여줍니다. 그래프에서는 각각의 구성 요소를 가리키는 단어가 존재합니다. 그래프의 노드를 정점(vertex), 그 정점을 연결하는 선을 간선(edge)라고 부릅니다. 간선으로 연결된 정점들은 서로 인접한다(adjacent)라고 말합니다. 그리고 인접한 정점들을 가리켜 이웃(neighbor)라고 부릅니다. 그래프에서는 다른 정점과 연결되지 않은 정점이 존재할 수 있습니다. 모든 정점이 연결되어있는 그래프를 가리켜 연결 그래프(connected graph)라고 부릅니다. 2. 방향 그래프 SNS를 예로 들어보면 A라는 사람이 .. 공감수 0 댓글수 0 2023. 3. 29.
트라이 : 텍스트 데이터 특화 트리 검색창의 자동 완성 기능의 동작 방법에 대해 궁금해하신 적이 있으신가요? 단어의 자동완성을 위해 검색창은 DB에 저장된 전체 데이터에 접근합니다. 이런 단어들에 대해서 어떤 자료구조로 저장하고 있을까요? 정렬되지 않은 배열로 저장되었다면 탐색 시 전체 배열을 탐색해야 하기에 $ O(N) $ 의 시간이 걸리게 됩니다. 정렬된 배열은 어떨까요? 정렬되어 있기 때문에 단계를 진행할수록 많은 후보군이 사라지고 $ O(logN) $ 만큼의 단계 안에 탐색을 마칠 수 있습니다. 정렬된 배열도 매우 빠르지만 무려 상수 시간 안에 자동 완성 기능을 실행할 수 있는 자료 구조가 존재합니다. 오늘은 해당 자료구조에 대해 포스팅 해보도록 하겠습니다. 1. 트라이 (Trie)란? 트리의 한 종류인 트라이 (trie)는 자동 .. 공감수 0 댓글수 0 2023. 3. 27.
힙과 우선순위 큐 : 제일 큰 값, 작은 값 이번 포스트에서는 특정 시나리오에서 유용하게 사용될 수 있는 트리 자료구조의 카테고리에 있는 힙 (Heap)에 대해 알아보도록 하겠습니다. 힙은 데이터 셋에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알고 있어야 할 때 유용하게 쓰입니다. 또 힙의 기능을 제대로 파악하기 위해 우선순위 큐 (Priority queue) 또한 함께 알아보도록 하겠습니다. 1. 우선순위 큐 (Priority queue)란? 일반 큐 (Queue)는 FIFO (First-In, First-Out)로 항목을 처리하고 자료구조의 양끝에서만 데이터를 처리합니다. 큐의 데이터에 접근하려면 데이터의 삽입된 순서에 우선권이 있습니다. 스택과 큐 - 제약을 통한 문제 해결 전략 이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자.. 공감수 0 댓글수 0 2023. 3. 25.
이진 탐색 트리 : 검색, 삽입, 삭제 모두 O(logN) 데이터를 특정 항목을 기준으로 정렬하고 싶을 수 있습니다. 퀵 정렬 알고리즘과 같은 방법으로 정렬을 할 수 있겠지만 정렬에는 비용이 발생합니다. 또 정렬된 자료구조에서 데이터의 변경이 발생하는 경우 변경 때마다 정렬된 상태를 지키기 위해서 정렬 비용을 계속해서 지불해야만 합니다. 삽입과 삭제가 빠르면서도 정렬이 되어있는 자료구조가 있다면 어떨까요? 놀랍게도 그러한 자료구조가 존재합니다. 그게 바로 오늘 포스팅할 "트리"입니다. 1. 트리 (Tree)란? 트리는 노드 기반 자료 구조이면서 구성 요소인 각 노드는 여러 노드로의 링크를 포함할 수 있습니다. 그 모습이 마치 나무를 연상시킨다 하여 트리라 명명하였습니다. 2. 트리의 고유 용어 트리 자료구조에는 트리에서만 사용하는 고유 용어가 존재합니다. 가장 .. 공감수 0 댓글수 0 2023. 3. 24.
연결리스트 : 대량 삽입과 삭제에 유리한 Node 기반 자료구조 컴퓨터 과학의 많은 자료 구조들은 Node라는 개념에 기반해 만들어져 있습니다. Node란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각을 의미합니다. 이번 포스트에서 알아볼 연결 리스트는 이러한 Node 기반 자료 구조 중 가장 간단한 자료구조라고 할 수 있습니다. 지금부터 연결리스트에 대해 알아보도록 하겠습니다. 1. 연결 리스트 (Linked List) 란? 연결리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료구조입니다. 배열은 연속되는 메모리에 항목들을 배치하고 이러한 점 덕분에 인덱스를 통해 항목에 바로 접근할 수 있습니다. 그렇다면 메모리에 흩어져있는 항목(Node)들을 가진 연결리스트는 어떻게 항목에 접근할까요? 이 답이 바로 연결 리스트의 핵심입니다. 각 Node는 추가정보, 연결리.. 공감수 0 댓글수 0 2023. 3. 18.
스택과 큐 - 제약을 통한 문제 해결 전략 이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자료구조에 대해 알아보겠습니다. 스택과 큐는 임시데이터를 처리할 수 있는 도구입니다. 임시데이터란 사용 후에는 의미 없는 데이터로서 제거해도 무관합니다. 스택과 큐는 임시데이터를 처리하며 주로 처리 "순서"에 중점을 둡니다. 1. 스택 ( Stack )이란? 스택이 데이터를 저장하는 방법은 배열과 같습니다. 다만 몇 가지의 제약 사항을 가지고 있습니다. 데이터는 스택의 끝에만 삽입 가능 => push 데이터를 스택의 끝에서만 삭제 가능 => pop 마지막 원소( Top )만 읽기가 가능 => peek 스택의 연산은 보통 두 문장으로 LIFO ( Last-In, First-Out / 후입선출 )으로 표현합니다. 항상 삽입된 마지막 항목이 첫 번째로 출.. 공감수 0 댓글수 0 2023. 3. 11.
해시 테이블 - 빠른 검색 이번 포스트에서는 해시 테이블에 대하여 알아보겠습니다. 개발을 하면서 효율성을 고려한다면 필수적이라 할 수 있을 정도로 해시테이블은 매우 빠른 자료구조인데요. 그만큼 사용할 수 있는 케이스 또한 다양합니다. 그럼 지금부터 해시테이블에 대해서 알아보겠습니다. 1. 해시 테이블 ( Hash Table )이란? 대부분의 프로그래밍 언어들은 해시 테이블 자료구조를 구현하고 있으며 각각 해시, 맵, 해시맵, 딕셔너리, 연관 배열 등의 여러 가지 이름으로 불리고 있습니다. 해시 테이블은 Key - Value 쌍으로 이루어진 자료 구조로 선언은 다음과 같이 합니다. const hashTable = { "abc" : 123, "def" : 456 }; 또한 아래의 형태로 자료구조 내의 데이터에 접근할 수 있습니다. h.. 공감수 0 댓글수 0 2023. 3. 11.
배열 - 가장 기초적인 자료구조 ( 3 ) 배열 시리즈의 마지막 포스트입니다. 이번 포스트에서는 배열 자료구조에 제약사항 한 가지를 더한 집합이라는 자료구조에 대해서 알아보며 특정 조건으로 인해 달라지는 연산의 효율성에 대해서 이야기해보겠습니다. 1. 집합이란? 집합이란 꽤 친숙하고 실생활에 밀접해있는 단어인데요. 중복값을 허용하지 않는 자료구조를 뜻합니다.컴퓨터 과학에서 여러 가지 형태로 집합을 구현하고 있지만 여기서는 배열을 기반으로 한 집합을 이야기해보겠습니다. 2. 배열기반 집합의 연산 배열 기반 집합의 연산 중 읽기, 검색, 삭제 의 경우 일반 배열 자료 구조와 동일한 단계를 가집니다. 하지만 삽입의 경우 원소가 중복되지 않아야 한다는 집합의 제약사항으로 인해 별도의 단계가 발생합니다. 삽입하려는 원소가 배열 내에 존재하지 않아야 하기에.. 공감수 0 댓글수 0 2023. 3. 3.
배열 - 가장 기초적인 자료구조 ( 2 ) 지난 포스트에 이어 이번 포스트는 배열의 자료 구조 연산 과정을 알아보고 또 그 연산들의 계산 단계를 세어 보도록 하겠습니다. 읽기 배열에서는 특정 인덱스로 한 번에 접근해서 값을 확인할 수 있기에 읽기 연산의 계산 단계는 1 단계 입니다. 우선 컴퓨터는 주소를 알고 있다면 모든 메모리 주소에 대하여 한 번에 접근할 수 있습니다. 컴퓨터는 최초로 배열을 생성할 때 배열의 시작 메모리 주소를 별도의 메모리에 저장해 놓는데요. 읽기를 요청받으면 저장해놓은 배열의 시작 메모리 주소에 인덱스 값을 더하여 별도의 과정 없이 한 번에 접근합니다. 검색 읽기가 인덱스를 제공하고 값을 가져왔다면, 검색은 값을 제공하고 인덱스를 구합니다. 특정 값의 위치를 알 수 없기에 배열의 시작 메모리부터 순차적으로 확인하는 과정을.. 공감수 0 댓글수 0 2023. 3. 3.
배열 - 가장 기초적인 자료구조 ( 1 ) 이번 포스트에서는 컴퓨터 과학에서 가장 기초적인 자료구조라고 할 수 있는 배열에 대해서 포스팅해보겠습니다. 배열에 대한 분석과 더불어 알고리즘에서 말하는 "속도" ( 시간 복잡도 ) 란 무엇인가에 대해서도 조금 이야기해보도록 하겠습니다. 1. 배열이란? 배열이란 앞서 썼던 것과 같이 컴퓨터 과학에서 가장 기초가 되는 자료구조로서 "단순한 데이터 원소들의 리스트" 이 한 문장으로 정의할 수 있습니다. 조금 더 자세히 정의하자면 컴퓨터가 데이터 저장을 위해 연속되는 메모리를 할당하고 이를 통해 읽기, 탐색, 삽입, 삭제 등이 이루어질 수 있는 자료구조가 배열이라 할 수 있습니다. 2. 배열의 요소 크기 : 배열에 저장되어 있는 원소의 개수를 뜻합니다. 인덱스 : 배열 내 특정 데이터의 위치를 나타냅니다. (.. 공감수 0 댓글수 0 2023. 3. 3.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.