[알고리즘] 최단 경로 찾기

최단 경로를 찾는 데 자주 사용되는 알고리즘은 여러 가지가 있다. 1. One-To-One 한 지점에서 다른 특정 지점까지의 최단경로 구하기2. One-To-All 한 지점에서 다른 모든 지점까지의 최단경로 구하기3. All-To-All 모든 지점에서 모든 지점까지의 최단경로 구하기 문제의 조건마다 사용되는 알고리즘이 다르기때문에 적절히 선택해서 사용해야 한다.그러려면 어떤 알고리즘이 있는지 알아야 할 것! 1. 다익스트라(Dijkstra) 알고리즘 목적 단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것원하는 목적지가 나오면 종료할 수도 있음 그래프 유형 가중치가 있는 방향성 또는 무방향성 그래프 - 음수 가중치 허용 X 시간복잡도 O((V+E)⋅log⁡V) 구현방식1. 시작 노드의 거리를 0..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 20.
• textsms

[자료구조] Avl Tree

🌳 AVL 트리(Adelson-Velsky and Landis Tree)란?AVL 트리는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로,트리의 균형을 유지하여 탐색, 삽입, 삭제 연산을 O(log n) 시간 복잡도로 보장하는 자기 균형 이진 탐색 트리다.   특징균형 인수(Balance Factor, BF)어떤 노드의 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이가능한 값: -1, 0, 1BF = 2 또는 -2가 되면 불균형 → 회전(Rotation) 필요자동 균형 유지삽입/삭제 시 불균형 발생 → 회전 연산으로 균형 유지탐색, 삽입, 삭제 모두 O(log n) 여기서 주목할 점은 균형을 유지하기위해 하는 회전 연산이다. 근데 왜 균형을 유지해야할까? 얘도 어차피 이진트리 아닌가..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 17.
• textsms

[자료구조] 이진트리

🌳 이진 트리(Binary Tree)란?이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 계층적 자료구조.자식 노드는 보통 왼쪽과 오른쪽으로 구분된다. 트리의 기본용어 노드(Node): 데이터를 저장하는 기본 단위루트(Root): 트리의 최상위 노드자식(Child): 특정 노드의 하위 노드부모(Parent): 자식 노드의 상위 노드리프(Leaf): 자식이 없는 노드서브트리(Subtree): 특정 노드와 그 하위 트리  이진트리의 특징 자식 노드의 수: 최대 2개 (0~2)재귀적 구조: 트리의 하위 구조도 트리 형태균형도(Balance): 노드의 배치가 성능에 영향을 미침 이진 트리의 종류포화 이진 트리(Full Binary Tree)모든 노드가 0개 또는 2개의 자식을 가짐리프 노드는 동일한 깊..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 17.
• textsms

[자료구조] B+ tree

B+Tree란? 데이터베이스 index에 자주 사용되는 자료구조 B-Tree 계열의 Balanced Tree 종류 중 하나   MySQL의 InnoDB 스토리지 엔진은 주로 B+ Tree를 사용한다. B+ Tree B-Tree에서 파생된 개념이다. B+Tree는 데이터베이스 인덱스와 파일 시스템 사용에 더 적합할 수 있도록 만들어졌다.  B-Tree와 차별화되는 특징은 아래와 같다. B+Tree의 리프 노드는 서로 연결 리스트로 서로 연결되어, 형제 노드끼리도 옮겨가며 조회할 수 있다. 연결된 리프 노드의 리스트를 따라가면서 범위 쿼리를 할 수 있어서, 범위 검색 성능이 좋다. internal 노드에는 키만 저장되며, 이 키를 사용해서 자식 노드의 메모리 상 위치를 판단한다.. internal 노드에는 ..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 17.
• textsms

[자료구조] LinkedList

LinkedList란?? 변수와 다음 노드를 가리키는 정보를 가진 노드들의 집합 Java에서는 LinkedList와 ArrayList를 기본제공한다. 기본제공 메서드  List list = new ArrayList();  // String타입 리스트 기본 생성자  get(int index) index위치의 값을 반환contains(Object e)해당 Object가 list에 있는지 boolean타입으로 반환size()list의 사이즈를 int로 반환add(String e)list에 String 추가add(int index, String element)list의 index위치에 String 추가remove(int index)해당 index 위치의 값을 삭제clear()list 초기화   직접 구현해보기 ..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 16.
• textsms

[자료구조] 스택(Stack)

스택(Stack)의 특징LIFO 구조후입선출(Last In, First Out) 방식으로 동작한다.나중에 삽입된 데이터가 가장 먼저 제거된다.단일 접근점데이터의 삽입과 제거는 한쪽 끝에서만 이루어집니다(보통 top 또는 head라 부릅니다).주요 용어push: 데이터를 스택의 맨 위에 삽입.pop: 스택의 맨 위 데이터를 제거.peek: 스택의 맨 위 데이터를 제거하지 않고 확인.isEmpty: 스택이 비어 있는지 확인. 스택의 장점간단한 구현자바에서는 단순히 메서드만 사용하면 금방 구현이 가능하다.재귀 문제 해결에 유용함수 호출 기록을 저장하고 복원하는 데 사용된다.DFS(깊이 우선 탐색) 같은 알고리즘에 필수적이다.일시적인 데이터 저장데이터를 임시 저장하고 나중에 처리하는 데 적합하다.ex) 괄호 검..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 16.
• textsms