"Boldness has genius, power, and magic in it." - Johann Wolfgang von Goethe
728x90
728x90

APS 6

[Python] 트리(Tree)구조와 이진 탐색 트리 정리

학습 내용 자료구조 중 트리(Tree) 구조의 개념 이해 이진 트리와 이진 탐색트리 Python 링크드 리스트 생성에 이진 탐색 트리 적용하기 🌲 대표적인 자료 구조 트리(Tree) 트리구조는 성능도 좋고, 많이 사용하는 자료구조입니다. node라는 개념으로 1차원적인 리스트 라는 배열의 개념을 확장한 느낌이 드는 데요. node와 branch를 이용해서, 마치 나무가 뿌리를 내린듯한 구조로 탐색 알고리즘 구현을 위해 많이 사용됩니다. 트리(Tree) 관련 용어 정리 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노..

APS 2022.10.04

[Python] Hash Table의 충돌 개선을 위한 SHA-1, SHA-256

학습 내용 Hash Table의 충돌을 개선하기 위한 공간 확대 SHA-1, SHA-256 을 사용하여 충돌을 개선하기 Hash 자료구조의 시간복잡도 계산해보기 📘 해쉬 테이블의 빈번한 충돌을 지우기 위한 방법 해쉬 테이블은 잘 활용하면 속도도 매우 빠르고, 효율적인 자료구조를 구축할 수 있습니다. 하지만 해쉬 테이블 내의 충돌에 대비하지 않으면 매우 비효율적으로 변할 수 있습니다. 충돌을 줄이기 위해서는 일반적으로 공간을 늘리는 방법과 안정적인 해쉬값을 생성하는 방법이 있습니다. 해쉬 함수 재정의 및 저장공간 확대 해쉬 테이블 내 충돌이 발생하는 이유는 구축방식에 따라 다르겠지만, 같은 주소값을 가지는 값들이 서로 충돌하여 발생하는 문제가 큽니다. 따라서 일반적으로는 해쉬 테이블의 공간을 충분히 확보하..

APS 2022.10.04

[Python] Hash Table에 Linear Probing 기법 적용하기

학습내용 Hash Table의 단점 중 하나인 충돌 문제를 Linear Probing 기법으로 해결하기 제한된 Hash Table의 저장공간 활용하기 🧨 저장공간 충돌을 막아주는 Linear Probing 기법 해쉬 테이블 자료구조를 사용하다 보면, 같은 주소값을 가진 데이터들로 인해 충돌문제가 발생하곤 합니다. 이때 Chaining 기법을 활용해서 저장공간 외의 공간을 활용할 수 도 있는 데요. 상황에 따라 한정된 저장 공간이 주어진 상황속에서는 Linear Probing 기법을 적용할 수 있습니다. Linear Probing 기법은 '폐쇄 해싱' 또는 'Close Hashing' 기법 중 하나로, 충돌이 일어나면 해당 hash address의 다음 address부터 순회를..

APS 2022.09.27

이진트리(Binary Tree) - 전위순회, 중위순회, 후위순회

🌲 트리(Tree) 개념 트리는 비선형 구조로 원소들 간에 1:N 관계를 가지는 자료구조입니다. 원소들 간에 계층 관계를 가지며 상위 원소에서 하위원소로 내려가면서 확장되는 트리(나무) 모양의 구조입니다. 용어 루트(root) : 노드 중 최상위 노드 노드(node) : 트리의 원소 간선(edge) : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) : 트리의 시작 노드(부모가 없는 노드) 잎 노드(leaf node) : 단말 노드(자식이 없는 노드) 차수(degree) : 노드의 차수는 노드에 연결된 자식 노드의 수 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨 트리의 높이 : 트리..

APS 2021.04.15

파이썬 APS_탐색 알고리즘 DFS / BFS

🔎 DFS DFS(Depth-First Search)는 그래프의 깊은 부분부터 우선적으로 탐색하는 알고리즘 노드와 간선으로 이루어진 그래프 구조에서 시작점을 기준으로 인접 노드의 깊은 부분부터 탐색하는 알고리즘 입니다. DFS는 스택자료구조를 이용하여 인접 노드의 방문여부를 체크하고 모든 노드를 방문한 즉, 노드의 깊은부분에 도달하면 스택에서 상단 노드를 pop 하는 방식으로 목표 노드를 탐색합니다.메모리 효율적인 부분에서 그래프는 인접리스트 방식이 더 우월하지만, 특정한 두 노드의 연결정보를 얻기 위해서는 인접행렬방식이 더욱 유리합니다. 🔍 BFS BFS(Breadth First Search)는 너비우선탐색으로 가까운 노드부터 탐색하는 알고리즘 너비우선탐색인 BFS는 DFS와 다르게 큐(Queue)자료..

APS 2021.03.03

정렬(Sort) 알고리즘_버블 정렬, 카운팅 정렬

알고리즘 문제를 풀때 기본이 되는 개념은 정렬(Sort)입니다. 대부분 input값을 입력받고 output을 내야하는 문제상황속에서 내가 원하는 결과를 내기 위해서는 입력받은 자료를 문제를 풀기위한 구조로 재배열하는 작업이 필수적이기 때문입니다. 정렬에는 여러종류가 있지만 그 중에서 기초적인 개념 '버블 정렬', '카운팅 정렬'에 대한 내용입니다. 📌 정렬의 종류 버블 정렬(Bubble Sort) 카운팅 정렬(Counting Sort) 선택 정렬(Selection Srot) 퀵 정렬(Quick Sort) 삽입 정렬(Insertion Sort) 병합 정렬(Merge Srot) 시간복잡도 빅오 O() 시간복잡도를 확인하고 상황에 맞는 정렬을 사용하자! 많은 양의 데이터들을 다루다보면 그 데이터들을 연산하는 ..

APS 2021.02.18
728x90
728x90