본문 바로가기

분류 전체보기144

[자료구조]B 트리, B+ 트리, B* 트리 1. 각 트리에 대한 요약 내용 B 트리 (B-Tree): B 트리는 균형 트리의 일종으로, 데이터를 정렬된 상태로 저장합니다. 각 노드에는 여러 키와 해당 키에 대응하는 값을 가질 수 있습니다. 각 노드는 키에 대한 오름차순으로 정렬된 배열을 가지며, 노드의 크기가 일정한 범위 내에 유지됩니다. B 트리는 데이터베이스 인덱스와 파일 시스템에서 널리 사용됩니다. 검색, 삽입 및 삭제 작업에 대해 대부분의 경우 O(log n)의 시간 복잡도를 제공합니다. B+ 트리 (B+ Tree) B+ 트리는 B 트리의 변형으로, 리프 노드만이 데이터를 저장하고 내부 노드는 키만을 저장합니다. 리프 노드는 연결 리스트로 연결되어 있습니다. 리프 노드는 외부 블록이므로 색인과는 달리 키를 찾는 데 사용됩니다. 이는 키에 .. 2024. 3. 13.
[알고리즘] 장애물이 있을 때 최단거리 길 찾기 1. 문제 상황 설명 직사각형 형태의 필드에 시작위치에서 목표 위치로 가는길에 장애물이 있는경우 아래 예시 문제에서는 귀신이 따라와서 귀신보다 빨리 가야 한다. 즉 귀신보다 목표 위치가 가까워야 하며, 장애물까지 고려한경우 귀신보다 변위가 짧아야 한다. 처음에는 모든 경우를 계산하도록 재귀함수를 만들었으나 단순히 Queue를 이용하여 해결하였다. 시작점에서 상하좌우로 퍼져나간다. 퍼져나간 노드에서 다시 4방향으로 퍼져나간다. 한번 지나간 노드는 다시 지나가봤자 변위 손해이며 최단거리가 아니다. 2. 코드 작성 public class Main { public static void main(String[] args) throws IOException { //문제를 입력 받는다. BufferedReader b.. 2024. 2. 2.
[알고리즘] 플로이드 와샬(Floyd-Warshall) 1. 플로이드 와샬 알고리즘 그래프의 모든 노드에서 다른 모든 노드까지 최단거리를 구하는 알고리즘 O(V^3)의 시간복잡도를 가졌다. 코드를 보면 알겠지만 3중 포문이 돌아간다. 매커니즘 j노드에서 k노드를 바로 가는 것과 i를 거쳐서 가는 것 중 비교를 계속 진행한다. 2. 문제와 코드 프로그래머스 배달 문제 참고 class Solution{ public int solution(int N, int[][] road, int K) { int answer = 0; //거리 비용을 2차원 배열에 정리 int[][] costs = new int[N][N]; for (int i = 0; i < costs.length; i++) { Arrays.fill(costs[i], 500001); costs[i][i] = 0.. 2024. 1. 31.
[알고리즘] 다익스트라(Dikstra Algorithm) 1. 다익스트라 알고리즘 그래프의 한 노드에서 각 모든 노드까지 최단거리를 구하는 알고리즘 음의 가중치를 가지면 최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능 등이 발생. 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. 연결 그래프 : 모든 두 꼮짓점 사이에 경로가 존재하는 그래프 희소 그래프 : 밀집 그래피의 반대 밀집 그래프 : 간선의 수가 최대에 가까운 그래프 : 간선 개수 = 정점의 개수 ^2와 근사하다.. 2024. 1. 31.

티스토리툴바