자료구조 2023. 9. 26.
자료구조 힙 Heap - 정의, 최대 힙, 최소 힙, 우선순위 큐
힙 Heap 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드에 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙 max heap 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 ≥ 자식 노드의 키 값 루트 노드: 키 값이 가장 큰 노드 최소 힙 min heap 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 ≤ 자식 노드의 키 값 루트 노드: 키 값이 가장 작은 노드 힙의 예 힙이 아닌 이진 트리 힙 - 삽입 17 삽입 23 삽입 힙 - 삭제 힙에서는 루트 노드의 원소만을 삭제할 수 있다 루트 노드의 원소를 삭제하여 반환한다 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다 힙의 활용 1 우선순위 큐 우선순위 큐를 구현하는 가장 ..
자료구조 2023. 9. 23.
자료구조 LinkedList - 정의, Singly Linked List, Double Linked List
Linked List 연결리스트 Singly Linked List Double Linked List 부록) 연결스택 & 연결큐 연결 리스트 특성 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다 자료구조의 크기를 동적으로 조정할 수 있어 메모리의 효율적인 사용이 가능하다 노드 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위 구성 요소 데이터 필드저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함 원소의 값을 저장하는 자료구조 링크 필드 다음 노드의 주소를 저장하는 자료구조 헤드 리스..
자료구조 2023. 9. 11.
자료구조 Queue - 원형 큐, 우선순위 큐
원형큐 우선순위 큐 삽입정렬 원형 큐 Circular Queue 원형 큐의 구조 초기 공백 상태 front = rear = 0 Index의 순환 front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함 이를 위해 나머지 연산자 mod 사용함 front 변수 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠 삽입 위치 및 삭제 위치 삽입 위치 삭제 위치 선형큐 rear = rear+1 front = front+1 원형큐 rear = (rear+1) mod n front = (front+1) mod n 원형 큐의 연산 과정 1) create Queue 2) enQ..
자료구조 2023. 9. 8.
자료구조 Queue - 정의, 특성, 선형 큐
질풍노도였던 21세 시절을 지나고 22살 이후 나에게 큐란 이 남성밖에 없었다. 큐 (Queue) 큐 선형큐 큐의 활용 Queue 큐(Queue)의 특성 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조 선입선출구조 (FIFO: First In First Out) 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입 (First In) 된 원소는 가장 먼저 삭제 (First Out) 된다 큐의 구조 및 기본 연산 큐의 선입선출 구조 큐의 기본 연산 삽입: enQueue 삭제: deQueue 연산 기능 enQueue(item) 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 deQueue() 큐의 앞쪽(front)에서 원소를 삭제..
자료구조 2023. 9. 6.
자료구조 Stack - 정의, 특성, 구현
Stack 스택(stack)의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된자료는 선형 구조를 갖는다 선형 구조: 자료 간의 관계가 1대1의 관계를 갖는다 비선형 구조: 자료 간의 관계가 1대N의 관계를 갖는다 (예: 트리) 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out)이라고 부른다. 예를 들어 스택에 1, 2, 3 순으로 자료를 삽입한 후 꺼내면 역순으로 3, 2, 1 순으로 꺼낼 수 있다. 스택의 구현 스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저장할 저장소 C언어에서는 배열 사용 저장소 자체를 스택이라 부르기도 한다 스택에서 ..
자료구조 2023. 8. 26.
자료구조 Array - 이차원 배열
2차원 배열 2차원 배열의 선언 2차원 이상의 다차원 배열은 차원에 따라 Index를 선언 2차원 배열의 선언: 세로길이 (행의 개수), 가로길이 (열의 개수) 를 필요로 함 int[][] twoDimArr = new int[2][4] // (2행 4열의 2차원 배열 선언) 배열 순회 n X m 배열의 n * m 개의 모든 원소를 빠짐없이 조사하는 방법 행 우선 순회 int i; // 행의 좌표 int j; // 열의 좌표 for i from 0 to n-1 for j from 0 to m-1 Array[i][j] // 필요한 연산 수행 열 우선 순회 int i; // 행의 좌표 int j; // 열의 좌표 for j from 0 to m-1 for i from 0 to n-1 Array[i][j] //..
자료구조 2023. 8. 24.
자료구조 Array - 검색, 선택 정렬, 카운팅 정렬
230808 Array (2) 검색(Search) 선택 정렬(Selection Sort) 카운팅 정렬 검색 Search 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 목적하는 탐색 키를 가진 항목을 찾는 것 탐색 키(search key): 자료를 구별하여 인식할 수 있는 키 검색의 종류 순차 검색 (sequential search) 이진 검색 (binary search) 인덱싱 (indexing) 순차 검색 Sequential Search 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행 시간이 급격히 증가하여..
자료구조 2023. 8. 18.
자료구조 Array - 알고리즘, 배열, 버블 정렬
230807 Array (1) 알고리즘 배열 정렬 버블 정렬 (Bubble Sort) 알고리즘 (명) 알고리즘: 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다. 간단하게 다시 말하면 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다. ex) 1부터 100까지 합을 구하는 문제 컴퓨터 분야에서 알고리즘을 표현하는 방법은 크게 두 가지 의사코드와 순서도 무엇이 좋은 알고리즘인가? 정확성: 얼마나 정확하게 동작하는가 작업량: 얼마나 적은 연산으로 원하는 결과를 얻어내는가 메모리 사용량: 얼마나 적은 메모리를 사용하는가 단순성: 얼마나 단순한가 최적성: 더 이상 개선할 여지 없이 최적화되었는가 주어진 문제를 해결하기..
자료구조 2023. 5. 17.
데이터구조 힙(Heap) python
Heap 힙은 특정한 규칙을 갖는 자료구조로, 최대값과 최소값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한다. 언젠가 수업 들으면서 이중 트리에 대해 배운 것 같은데 기억이 휘발되었다…. 아마 가지치기 형태로 데이터를 구성한 다음 두 개씩 값을 비교하여 순서를 바꾸는 거였나…. Heap의 좋은 점은 따로 정렬하지 않아도 가장 큰 값과 작은 값을 알아서 찾아준다는 것이다. 자식 노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개로 한정한다. 최대 힙 (max heap)key(T.parent(v))≥key(v) 각 노드의 키 값이 그 자식 노드의 키 값보다 작지 않은 힙 최소 힙 (min heap)ket(T.parent(v))≤key(v) 각 노드의 키 값이 그 ..
자료구조 2023. 4. 7.
데이터 구조 큐(Queue) python
드디어 큐(NOT TBZ)와 데이터 구조 공부를 제대로 해 본다.... 학교 다닐 때 공부 좀 할걸.... Queue 선입선출(First In First Out) 기반의 자료 구조 데이터를 추가한 순서대로 제거할 수 있음 활용 - 비동기 메세징 (asynchronous messaging) - 스트리밍 (streaming) - 너비 우선 탐색(breath first search) 구현 방법 1. List queue = [1, 2, 3] queue.append(4) queue.append(5) print(queue) # [1, 2, 3, 4, 5] queue.pop(0) # 1 queue.pop(0) # 2 print(queue) # [3, 4, 5] - .append 뒤에서 데이터 추가 - .pop(0) ..
