[Basic] Data43 [Algorithm] 거품 정렬 (Bubble Sort) 거품 정렬 (Bubble Sort) Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 프로세스 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬.. 2023. 2. 27. [Data Structure] 비선형 - Heap(힙) Heap(힙) Binary Tree(이진트리) 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다. 루트 노드의 키 값이 트리의 최솟값 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다. 루트 노드의 키 값이 트리의 최댓값 최대 힙 → 힙 정렬 알고리즘 → 우선순위 큐 2023. 2. 21. [Data Structure] 비선형 - Tree(트리) 트리 구조는 맨 위의 사진과 같이 하나의 뿌리로부터 시작되어서 가지가 여러 갈래로 뻗어있는 자료 구조를 말한다. 트리 구조가 어디서 많이 봤다고 하면 착각은 아니다. 스포츠를 좋아하는 사람이라면 많이 봤을 것이라고 생각되는 토너먼트 대진표도 트리 구조이다. 아래서부터 차례로 올라가서 가장 꼭대기까지 가는 것이 토너먼트이다. 트리구조는 반대로 위의 뿌리 노드부터 시작해서 아래로 내려가는 구조다. Tree (트리) 노드로 이루어진 비선형 자료 구조 그래프가 계층적 구조를 가진 형태 최상위 노드(루트)를 가지고 있음 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 .. 2023. 2. 21. [Data Structure] 비선형 - Graph(그래프) Graph(그래프) 객체 간의 연결을 시각화한 것으로 정점(Vertex)간의 관계를 표현하는 자료구조 단순히 노드(N, node)와 그 노드를 연결한 간선을 하나로 모아놓은 자료 구조. 즉, 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다. nodes/vertices(노드) 사이에 edge(엣지)가 있는 collection directed(방향) 그래프는 일방통행 undirected(무방향) 그래프는 양방향 → 소셜 미디어 네트워크를 나타내는 데 사용 → 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용 → GPS에서 위치와 경로를 나타내는 데 사용 그래프의 용어 정점(vertex) : 그래프를 형성하는 노드 간선(edge) : 그래프에서 노드 간의 연결 (정점 간에 '선') - 아크라.. 2023. 2. 21. [Data Structure] 비선형 - Hash Table(해시 테이블) Hash Table(해시 테이블) 해시 테이블은 '키-값'쌍으로 데이터를 저장하는 자료구조 중 하나로 빠른 검색, 빠른 삽입이 가능하다는 특징을 가진다. 해시 테이블이 빠르게 데이터에 접근할 수 있는 이유는 내부적으로 배열(버킷)을 사용해서 데이터를 저장하기 때문이다. 배열에 저장된 데이터를 데이터 고유의 인덱스로 접근하기 때문에 평균적으로 O(1)의 시간 복잡도로 검색할 수 있다. 고유 인덱스는 데이터의 키 값에 해시 함수(hash function)을 적용해 생성한다. Hash Function 적절한 해시 함수를 사용하는 것은 매우 중요하다. 각각 데이터는 데이터 고유의 인덱스를 가져야 하는데, 어설픈 해시 함수를 사용할 경우 인덱스가 많이 겹치는 경우가 발생할 수 있기 떄문이다. 이 경우를 'coll.. 2023. 2. 21. [Data Structure] 선형 - Queue(큐) Queue (큐) 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다. 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out) 또는 LILO(Last-In, Last-Out) 방식. Ex) 큐 구현 class Queue { constructor() { this.storage = {}; // 여기에 담는다. this.front = 0; this.rear = 0; } size() { return Object.keys(this.storage).length; } // 큐에 데이터를 추가 할 수 있어야 한다. enqueue(element) { this.storage[this.rear] = element; this.rear += .. 2023. 2. 21. [Data Structure] 선형 - Stack(스택) Stack (스택) 순서가 보존되는 선형 데이터 구조 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO (Last In First Out) 또는 FILO(First-In, Last-Out)데이터 관리방식을 따름 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 데이터를 제한적으로 접근할 수 있는 구조 → 실행 취소 → 수학적 표현식을 구문 분석하고 평가 → 재귀 프로그래밍에서 함수 호출을 구현 2023. 2. 21. [Data Structure] 선형 - Linked List(연결 리스트) Linked List (연결 리스트) 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조 동적인 데이터 추가/삭제에 유리하다. 각 요소는 Node 각 Node에는 key와 다음 노드를 가리키는 포인터인 next가 포함 (참조한다) 첫 번째 요소는 Head 마지막 요소는 Tail → Alt + Tab을 사용하여 프로그램 간 전환 → 갤러리 연결 리스트의 장점 리스트 길이가 가변적이라 배열의 단점을 커버 할 수 있다. 연결 리시트의 단점 어떤 노드를 Search하거나 데이터를 변경할때 바로 찾아낼 수 없다. 사용 데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이면 링크드리스트를 쓰는것이 좋고, 주로 데이터의 변경이나 탐색을 위한것이라면 배열을 쓰는것이 좋다. 2023. 2. 21. [Data Structure] 선형 - Array(배열) Array(배열) 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다. 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있다. → 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용 → 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용 데이터를 나열하고, 각 데이터를 인덱스에 대응해주고 인덱스로 데이터를 접근할 수 있도록 구성된 데이터 구조 파이썬에서는 리스트 타입이 배열기능을 제공 배열이 왜 필요할까? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 배열의 장점 - 인덱스로 인한 빠른 접근 가능 배열의 단점 - 미리 배열의 크기를 설정해줘야함으로 데.. 2023. 2. 20. [Data Structure] 자료구조란? 자료구조란? (Data Structure) 사전적인 의미는 자료(Data)의 집합의 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이라고 한다. 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였다. 자료구조를 쓰는 목적 이러한 자료구조를 사용하는 목적은 명확하다. 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다. 자료구조의 선택 기준 적은 양의 데이터를 처리할 때는 어떤 자료구조를 사용하든 큰 차이가 없다. 그러나 대량의 데이터를 한 번에 처리함에 있어서 어떤 자료구조를 사용하.. 2023. 2. 20. 이전 1 2 3 4 5 다음
