# GTx

24개의 포스트
post-thumbnail

[edx] Minimum Spanning Tree

그래프 내의 모든 vertice를 연결하는 sub graph 가운데, edge의 weight 총합이 가장 작은 경우를 의미한다.Cycle을 이루면 안되기 때문에 항상 tree의 형태를 가진다.일반적인 spanning tree는 DFS, BFS로도 구할 수 있으나, MS

2022년 5월 26일
·
0개의 댓글

[edx] Dijkstra's algorithm

일반적으로는 BFS를 사용하면 vertice간 최단거리를 구할 수 있다. 다만, 이 경우는 edge에 weight가 없을 경우에 한정한다.Weight가 존재하는 경우, 다른 방식이 필요하다.그래프 내의 한 vertice에서 다른 vertice까지의 최단거리를 구하는 일

2022년 5월 25일
·
0개의 댓글

[edx] 그래프 기초

그래프는 비-선형적인 자료구조이며, vertice(node)와 vertice사이를 연결하는 edge를 총망라한 자료구조이다. 결과적으로, 일종의 연결망을 생성한다고 볼 여지가 있다.그래프의 용어는 다음과 같다.BST/LinkedList 또한 그래프의 일종이다.그래프에

2022년 5월 25일
·
0개의 댓글

[edx] Pattern matching 알고리즘

주어진 text에서 주어진 특정 pattern이 존재하는지, 필요시 몇번 등장하는지를 알 수 있는 알고리즘들을 말한다.Brute-force의 발상을 따르면, 텍스트의 1번 string부터 시작하여 패턴과 일치하는지 일일히 비교하는 방법을 쓸 수 있다. 이 경우, 패턴의

2022년 5월 24일
·
0개의 댓글

[edx] 정렬 알고리즘 2

이 형태의 정렬 알고리즘들은 데이터의 모음을 더 작게 나누고 분리함을 통해, 데이터를 적게 참조할 수 있도록 하여 시간 복잡도를 개선한다.주어진 array를 재귀를 이용해 최대한 분리했다가, 정렬한 array를 recursive stack으로 차곡차곡 반환하는 방법이다

2022년 5월 23일
·
0개의 댓글

[edx] 정렬 알고리즘 1

Array, 혹은 List의 순서를 알 수 있는 데이터를 특정 순서대로 위치를 바꾸는 알고리즘들은 많다.각각의 특징으론 시간복잡도, stability, adaptivity, 메모리 사용도를 들 수 있다.주어진 array의 중복 값을 원래 순서대로 정렬한다면 stable

2022년 5월 23일
·
0개의 댓글

[edx] 알고리즘 기초

알고리즘은 특정한 문제를 해결하기위한 절차를 의미한다.비유를 들자면 일종의 자동차 길찾기와 비슷하다. 특정 장소에서 다른 장소로 자동차를 이용하여 가는 방법은 하나가 아니라 매우 여럿일 수 있다. 즉, 특정 문제를 해결하는 알고리즘은 하나가 아니다.그렇기때문에, 알고리

2022년 5월 22일
·
0개의 댓글

[edx] 2-4 tree

2-4 tree는 node 1개에 여러 데이터를 가질 수 있고, 그에따라 자식의 수도 다른 tree이다.Node의 데이터는 1개부터 3개까지이고, 자식의 수는 데이터의 수 + 1까지이다.가장 중요한 특징은, 모든 leaf의 depth가 같아야 한다는 점이다.2-4 tr

2022년 5월 21일
·
0개의 댓글

[edx] AVL tree

BST는 탐색의 효율을 담보하기 위한 자료구조이지만, tree의 현재 형태에 따라 탐색 효율이 다르다. 평균적으로, 이론적으로는 O(log n)이지만, 형태가 좋지 못한 경우 O(n)으로 크게 효율이 감소한다.AVL은 height와 balance factor개념을 도입

2022년 5월 20일
·
0개의 댓글

[edx] HashMap

Map은 key-value짝의 모음으로 이루어진 자료구조이다. 탐색을 지원하고, 순서가 없다는 특징을 가지고 있다.개별 key는 유일해야하고, 변형도 불가능해야하지만, value는 동일할 수 있다.Hashmap은 array를 기반으로 하는 자료구조이며, 특정 index

2022년 5월 20일
·
0개의 댓글

[edx] SkipList

1. 개요 2. 쓰임새

2022년 5월 19일
·
0개의 댓글

[edx] Binary Heap

1. 개요 2. 동작

2022년 5월 19일
·
0개의 댓글

[edx] Binary Search Tree

어떤 Array에서 특정 데이터가 존재하는지 그렇지 않은지 찾는 경우, 0번째 index에서부터 마지막까지 비교해가면서 찾는 방법이 가장 떠올리기 쉬운 방법이다. 이 경우, O(n)의 시간이 걸린다.하지만, 만약 Array가 작은 것에서부터 큰 순서대로 정렬되어있다면,

2022년 5월 18일
·
0개의 댓글

[edx] Tree 기초

앞서 살펴본 List와 Stack, Queue등은 메모리 소모도 적은편이고, 사용함에 있어 시간도 오래걸리지 않는다.하지만, 만약 원하는 데이터가 중간에 있다면, 그 이전의 데이터들을 모두 삭제해야만 얻을 수 있다.위와 같은 특성으로 인해, 탐색이 매우 불편하다. 대부

2022년 5월 17일
·
0개의 댓글

[edx] Stack&Queue

Stack과 Queue는 Linear한 성질을 지닌 자료구조이다.Linear하다는 것은 다음의 특성을 가진다.자료구조에 적용한다면, 유한한 수의 선행객체와 후행객체를 가지는 객체의 모음이라고 볼 수 있다.Stack은 Last In, First Out의 특징을 가진 Li

2022년 5월 17일
·
0개의 댓글

[edx] List: LinkedList

LinkedList는 Array를 이용하지 않은 List로, 데이터를 저장하고 있는 Node의 모음집이라 할 수 있다. 그래서 데이터가 메모리에 연속적으로 위치하지 않으며, 리사이즈도 필요 없다. 또한, ArrayList는 Index를 통한 접근이 가능했지만, Link

2022년 5월 16일
·
0개의 댓글

[edx] List: ArrayList

List는 indexing을 통해 접근 가능한 연속적인 데이터 값을 의미하며, 최소한 다음의 동작들이 가능해야한다.addAtIndex: 리스트의 특정 인덱스에 주어진 데이터를 저장removeAtIndex: 리스트의 특정 인덱스에 저장되어 있는 데이터를 삭제get: 리스

2022년 5월 16일
·
0개의 댓글

[edx] Array

Array는 연속적으로 데이터를 저장하는 자료구조로, 거의 모든 데이터를 호환한다. 다만, Array는 데이터를 저장하기 전에도 최초 선언한 크기대로 메모리를 점유(statically allocated)하고 있으며, 이를 임의로 늘릴 수는 없다. 더 큰 Array를 선

2022년 5월 16일
·
0개의 댓글

[edx] 자료구조 기초

자료구조의 목적은 데이터를 공간과 시간 양편에서 더 효율적으로 다룰 수 있도록 하는 것으로 볼 수 있다.현실에서 물건을 보관하고 이를 찾아 이용하는 일은 분류만 적절히 한다면 큰 차이가 없을 가능성이 높지만, 컴퓨터에서는 다르다. 컴퓨터는 자료를 메모리에 할당하는 것과

2022년 5월 16일
·
0개의 댓글

[edx] 다형성(Polymorphism)

1. 개요 2.

2022년 5월 13일
·
0개의 댓글