전체태그 보기

#자료구조 (33개의 포스트)

junyong92
정의 그래프 그래프(Graph)는 연결되어 있는 데이터들의 관계를 표현하는 자료구조이다. 다양한 형태를 가질 수 있는 여러개의 노드(Node)와 노드 사이를 잇는 엣지(Edge)로 이루어져 있다. 그래프를 분류하는 방법에는 여러가지가 있다. 엣지의 상태에 따른 분류로는단방향 그래프(Undirected), 양방향 그래프(Directed), 가중치 그...
junyong92
Linked List 정의 링크드 리스트(Linked List)는 노드(자료)들이 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조이다. 각 노드는 데이터와 포인터를 가지고 있다. 포인터는 다음 혹은 이전의 노드와의 연결을 담당한다. 자동적으로 길이가 늘어나는 배열이라고 생각할 수 있겠는데, 사실 지금 공부하고 있는 자바스크립트에서는 큰 의미...
dudrkdl777

Set과 Map 완정정복하기!!-Map

2019년 10월 13일0개의 댓글
Map key-value 형식으로 데이터를 저장. key는 중복 불가, value는 중복가능 image.png = key를 기준으로 알파벳 오름차순 정렬된 모습 - LinkedHashMap 입력 순서를 기억, 순서 보장 image.png HashMap과 HashTable의 차이 일반적으로 동기화가 필요 없다면 HashMap을,...
dudrkdl777

Set과 Map 완정정복하기!!-Set

2019년 10월 13일0개의 댓글
Set set은 linkedList와 달리 데이터의 중복을 허용하지않는다. 인덱스로 객체를 관리하지 않으므로 데이터를 검색할때는 iterator() 메서드로 iterator(반복자)를 생성하고 데이터를 가져와야한다. Set의 종류 HashSet 대표적인 set 컬렉션 구현 클래스. 중복 데이터 저장 X 순서 보장 X image....
pa324

자료구조 - 그래프

2019년 10월 6일0개의 댓글
그래프 - 그래프란 사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구이다. - 그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있다. - 인접행렬은 2차원 배열을 이용하고, 인접 리스트는 리스트를 사용한다. 인접행렬을 이용한 그래프 - 0번째 인덱스에서 0번...
pa324

자료구조 - 이진탐색

2019년 10월 6일0개의 댓글
이진탐색 - 이진탐색(Binary Search)은 배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘이다. - 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. - 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 탐색 시간이 O(logN)의 시간 복잡도를 가진다. image.png image.pn...
litien

[면접스터디] 트리

2019년 10월 5일0개의 댓글
1.이진트리, 완전 이진트리, 이진 탐색트리에 대해 설명하라 - 트리는 하나의 루트를 가지고(엄밀한 그래프 이론에서는 그렇지 않지만 일반적으로 사용하는 트리는 보통 이렇다) 자식노드를 가지며 cycle이 존재하지 않는자료구조이다. - 이진트리는 자식노드를 최대 2개까지 가질 수 있는 트리 - 완전 이진트리는 말단노드를 제외한 모든 노드가 2개의 자식노드를 ...
pa324

우선순위 큐

2019년 10월 5일0개의 댓글
우선순위 큐 - 우선순위 큐는 '우선순위'를 가진 데이터를 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용되고 있다. - 우선순위 큐는 운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. - 우선순위 큐는 트리 구조로 보는 것이 합리적이다. 일반적으로 우선순...
pa324

이진트리

2019년 10월 3일0개의 댓글
트리 - 트리는 나무의 형태를 뒤집은 것과 같은 형태의 자료구조 이다. - 트리의 최상단노드를 루트노드라고 한다. - 노드들은 가지로 연결된다. - 트리에서 가장 끝 노드는 리프노드라고 한다. - 트리의 깊이는 루트 노드에서 특정 노드까지의 길이를 의미한다. image.png image.png image.png 이진트리 이진트리는...
pa324

계수정렬 && 기수정렬

2019년 10월 3일0개의 댓글
계수 정렬 - 계수 정렬(Counting Sort)는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘 이다. - 각 데이터를 바로 크기를 기준으로 분류하므로 O(N)의 시간 복잡도를 가진다. 먼저 아래와 같이 총 4개의 원소가 있는 배열을 만든다. image.png 하나의 원소를 발견할 때 마다, 해당 원소의 값을 1씩 증가 시킨다. 맨 처음...
litien

[면접 스터디] 선형자료구조2

2019년 9월 29일0개의 댓글
1. 정렬되어 있지 않은 링크드리스트에서 중복된 원소를 없애라 - 임시 버퍼를 사용 할 수 있을 때 링크드리스트를 순회하면서, Hash 테이블에 저장 Hash 테이블에 이미 저장된 데이터라면 삭제한다. 시간복잡도는 O(n)이 소요된다.
smooth97

자료구조

2019년 9월 28일0개의 댓글
자료구조란? 사전적인 의미는 자료(Data)의 집합을 의미하고, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다. 자료구조를 사용하는 목적 Data를 더 효율적으로 저장하고 관리하기 위해 사용되며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이...
pa324

자료구조 - 퀵 정렬

2019년 9월 28일0개의 댓글
퀵 정렬(Quick Sorting) - 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로 평균적으로 NlogN의 시간복잡도를 가진다. - 분할 정복 알고리즘의 하나로, 평균적으로 매우 ...
pa324

자료구조 - 큐

2019년 9월 26일0개의 댓글
큐(queue) 정의 - 큐는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료구조 이다. - 스케쥴링, 탐색 알고리즘 등에서 다방면으로 활용된다. - push,pop연산이 있다. image.png 큐(queue) 구현 - 큐는 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현방법으로 나눠진다. - 가장 기본적인 자료구조로 난이도는 낮...
자료구조와 알고리즘 기본 정리
kmp1007s
자료구조(Data Structure)? - 데이터를 표현하는 방법 및 구조 알고리즘(Algorithm)? - 데이터를 처리하는 방법 시간복잡도 시간복잡도 비교 - 문제를 해결하는데 걸리는 시간으로 Big-O 표기법을 사용한다 - 빅오를 구할 때 계수와 낮은 차수의 항은 제거한다 - 시간 복잡도를 구하는 방법은 핵심 연산의 반복횟수를 구하면 된다 ...
litien

[면접 스터디] 선형 자료구조

2019년 9월 24일0개의 댓글
1. Stack과 Queue를 설명하고, 탐색,삭제,삽입의 시간복잡도는 어떻게 되는가? Stack은 선입선출(Last-In-First-Out)구조로 먼저 들어온 데이터가 top의 위치하여 먼저 나간다. 삽입, 삭제는 O(1)의 가능하며 탐색은 O(N)의 시간이 소요된다. 함수 호출, 시스템 콜등에 stack이 사용된다. Queue는 선입후출(First-I...
chanste
과제아닌 진짜 첫 TIL h1Stack, Queue, Linked List, Graph까지 혼자서 찾아보고,h1 블로그를 만들어 이에 대해 내가 이해한 내용을 TIL형식으로 블로깅했다. Stack과 Queue는 각각 프링글스, 편의점에 진열된 우유를 떠올리며 비교적 쉽게 이해하며 넘어갈 수 있었으나 C++이나 python을 통해 구현한 레퍼런스가 많아 구...
dankim
Instantiation Patterns 자료구조 Stack, Queue 으로 구현 Class 선언이 나오기 전 사용되었던 4가지 방법 Pseudoclassical (prototype 선언 방식은 현재도 많이 쓰임) 1. Functional 2. Functional-shared 3. Prototypal ...
dankim

2019.09.18 Graph

2019년 9월 18일0개의 댓글
Graph image.png image.png 출처 : GeeksforGeeks https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/ 1. 단순히 노드(node)와 노드를 연결하는 간선(엣지 edge)를 하나로모아 놓은 자료 구조 2. Root 노드 개념 없음 3. ...
dankim

2019.09.18 Hash Table

2019년 9월 18일0개의 댓글
Hash Table image.png 출처 : https://study.cs50.net/hashtables 1. Hash Table? - Key에 Value를 저장하는 데이터 구조 (자바스크립트의 Object와 유사) - 동일한 값이 입력되면 언제나 동일한 출력값을 보장해야한다 - hashFunction()을 통해 테이블 내에 위치한 key값을...