일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 멀티프로세서
- 백준 장학금
- 연결리스트
- 점근적 표기법
- 최소힙
- 백준장학금
- 엔티티 그래프
- spring
- 운영체제
- heapq
- 프로세스
- jpa n+1 문제
- 스케줄링
- AVL트리
- HTTP
- MSA
- JPA
- 최대 힙
- 완전이진트리
- 알고리즘
- 힙트리
- 자료구조
- SpringSecurity
- python
- JVM
- Kruskal
- 강화학습
- 이분탐색이란
- posix
- 연결리스트 종류
- Today
- Total
목록분류 전체보기 (113)
KKanging

이진트리 많아야 두 개의 자식 노드를 가짐 왼쪽 자식과 오른쪽 자식으로 구분 완전이진트리처럼 트리의 균형이 유지가 되지 않음 균형이 없는 트리이기 때문에 연결리스트로 표현하는 게 적합 root node로부터 이진트리를 표현한다. 연결리스트로 표현 돼서 배열처럼 트리의 원소를 찾기 힘들다. 그래서 이진트리는 순회 알고리즘을 이용해서 노드의 수나 정점을 찾는다. 이진트리의 순회 방법 전위 (VLR) 중위 (LVR) 후위 (LRV) 기준은 visit을 기준으로 전위 중위 후위를 나눈다 전위(Preorder traversal) root node부터 시작한다. Visit 하고 왼쪽(left)으로 가고(visit)한다. 왼쪽이 없으면 오른쪽으로 간다.(Right) 위 순서대로 방문한다. 중위(Inorder trav..

python에는 heap트리를 구현하는 표준 라이브러리 heapq라는 라이브러리가 있다. 만약 heap 트리를 아직 모른다면 아래 링크를 보는 것을 추천합니다. [자료구조] 힙트리의 정의와 구현 (Java) [자료구조] 힙트리의 정의 와 구현 (Java) 힙이란 완전이진 트리로 구성되었다. 트리의 구성이 균형을 이룬다 부모노드와 자식 노드 관계에 특징을 이룬다. 힙의 종류 최대 힙 트리 (Max heap) 완전이진트리로 구성 부모 노드의 키 값은 자 kkangmg.tistory.com heap트리 import import heapq heapq 특징 요소는 0부터 센다. 비교를 위해, 존재하지 않는 요소는 무한으로 간주. 최소 힙(Min heap)을 디폴트로 가진다는 점 즉, heap[0]이 리스트 중 제..

힙이란 완전이진 트리로 구성되었다. 트리의 구성이 균형을 이룬다 부모노드와 자식 노드 관계에 특징을 이룬다. 힙의 종류 최대 힙 트리 (Max heap) 완전이진트리로 구성 부모 노드의 키 값은 자식 노드의 키 값보다 크거나 같음 왼쪽 오른쪽 자식의 크기 구분 없음 최소 힙 트리(Min heap) 완전 이진트리로 구성된 트리 부모 노드의 키 값은 자식 노드의 키 값보다 작거나 같음 왼쪽 오른쪽 자식의 크기 구분 없음 힙의 응용 우선 순위 큐, 프린터 스풀러 등등 힙 정렬: 최대 힙 (내림 차순 정렬) , 최소 힙 ( 오름차순 정렬) 최대 힙 구조 이 글에서는 최대 힙의 예시와 구현만 하였습니다. 최대 힙의 예 배열 표 삽입 연산 그리고 heapify 연산을 한다 heapify 연산이란 ? 위 그림과 같이..

완전 이진트리란? 완전 이진트리 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지 완전 이진트리 표현 배열로 표현한다. 이유는 완전이진트리의 속성인 균형이 유지되기 때문 완전 이진트리 자료구조 0부터 시작해도 되지만 노드의 인덱싱의 조금 더 가시성이 좋기 때문에 1부터 시작해도 된다. 1부터 시작할 경우 배열 인덱스 i의 부모노드: i/2의 바닥함수(내림) 노드 배열 인덱스 i의 왼쪽 자식: 2i의 노드 배열 인덱스 i의 오른쪽 자식: 2i + 1의 노드 완전 이진트리의 레벨 i에서 노드의 수는 2^(i-1)개 완전이진트리의 높이가 h일 경우 최대 노드의 수는 2^h -1개 완전 이진트리에서 노드의 수 n일 경우 트리의 높이는 O(logn) 완전이진트리를 사용한 알고리즘의 수행시간은 트..

트리란 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 cycle을 가지지 않는 그래프 트리 관련 용어 노드(node) : 트리 자료구조에서 data의 단위 간선(edge): 트리나 그래프에서 정점이나 노드끼리 연결되어 있는 선 루트 노드(root node): 부모가 없는 최상위 노드 단말 노드 or 말단 노드(leaf node): 자식이 없는 노드 크기(size): 트리에 포함된 모든 노드의 개수 깊이(depth): 루트 노드로부터의 거리 높이(height): 깊이 중 최댓값 차수(degree): 각 노드의 (자식 방향) 간선 개수 이런 형태도 트리일까? 이 형태는 cycle이 발생하기 때문에 트리가 아니다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이유는 cycle이 ..

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말합니다. 이 이름은 Double-Ended Queue에서 나왔습니다. 스택과 큐의 일반적인 특성을 모두 가지고 있어서 스택처럼 LIFO(Last In First Out) 구조, 큐처럼 FIFO(First In First Out) 구조로 사용할 수 있습니다. 덱이란? 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말함 스택과 큐의 일반적인 특성을 모두 가지고 있음 덱이란 앞쪽 뒤쪽 모두 삽입 삭제가 많이 이루어지는 작업에 적합 인덱스 조회 후 삽입 삭제에는 불리함 덱의 구현 원형 배열 연결 리스트 이 글에선 원형 배열로만 구현하겠습니다. 덱의 자료구조 설계 add_front: 덱의 앞쪽에 요소를 추..

queue란 자료구조에 대해 알아보겠습니다. 큐(Queue)는 스택과 마찬가지로 컴퓨터 과학에서 핵심적인 개념입니다. 어떤 표를 사기 위해 줄서는 걸 생각해보면 이해하기 쉽습니다. 줄 서는 것과 같이 먼저 들어간 항목이 먼저 나오는 (First In First Out) 원칙을 따르는 자료구조입니다. 큐란? 데이터의 삽입과 삭제가 서로 다른 위치에서 일어나는 자료구조 FIFO: First-In-First-Out 큐의 응용 은행 대기, 식당 대기, 항공기 이착륙 다양한 분야의 시뮬레이션 등 큐 구현 방법 단순 배열 원형 배열 연결리스트 이 글에선 원형 배열 큐만 다룹니다. 배열 큐의 자료구조 설계 삽입(enqueue) , 삭제(dequeue) isFull(가득 찼는지 검사) isEmpty(비었는지 검사) 자..

stack이란 자료구조에 대해 알아보겠습니다. 스택(Stack)은 컴퓨터 과학에서 중요한 개념 중 하나입니다. 위에 테니스 공 통에 테니스 볼을 넣는 거와 같이 한쪽 끝에서 입력과 출력이 이루어지고 마지막에 들어간 공이 먼저 꺼낼 수 밖에 없는 것처럼(Last In First Out) 스택이란 자료구조도 동일하게 작동하는 자료구조 입니다. 스택이란? 삽입과 삭제 연산이 한쪽 끝에서 이루어지는 자료구조 LIFO (Last In First Out) 스택을 구현할 수 있는 방법? 배열→ 구현이 쉬우나 정적인 크기라 제한이 있음 리스트 ( 연결리스트 ) → 구현이 배열에 비해 어려우나 자료구조의 크기가 동적이다는 장점이 있음 이 글에서는 배열로 구현한 예만 보여드립니다. 연결리스트 구현이 그렇게 어려운 것 아니..

파이썬은 매우 다양한 자료형을 지원하며, 특히 리스트는 그 중에서도 매우 유연한 자료형입니다. 리스트는 여러 개의 값을 하나의 변수에 저장할 수 있는 자료구조로, 값을 추가, 삭제, 변경할 수 있습니다. 동적 배열과 리스트 파이썬의 리스트는 내부적으로 C언어 처럼 배열을 가지고 있습니다. 하지만 차이점이 있다면 동적 배열로 구현되어 있습니다. 동적 배열은 크기를 동적으로 조정할 수 있는 배열입니다. 이를 통해 리스트는 요소의 추가, 삭제, 탐색 등에 효율적인 작업을 수행할 수 있습니다. numbers = [1, 2, 3, 4, 5] 위 코드는 숫자 1부터 5까지의 값을 가진 리스트를 생성한 것입니다. 이때 리스트에 추가로 요소를 삽입하거나 기존 요소를 삭제하는 등의 작업을 수행하면, 파이썬은 자동으로 리..

연결리스트 종류 단일 연결리스트(Single linked list) 이중 연결리스트 (Doubly linked list) 원형 연결리스트 (Circular linked list) 원형 이중 연결리스트 (Doubly Circular linked list) 단일 연결리스트(Single linked list) 참고 사이트: 연결리스트란 연결리스트의 개념이 궁금하시면 연결리스트가 뭔지 보고 오시면 좋을거 같습니다. 이중(양방향) 연결리스트 (Doubly linked list) 이중 연결리스트는 각 노드가 두 개의 참조를 가지며, 하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킵니다. 이로 인해 리스트를 양방향으로 탐색할 수 있습니다. 이를 파이썬으로 구현하는 경우 Doubly_linked_list 클..