한화시스템 Beyond SW Camp/자료구조 알고리즘7 [알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra)다익스트라(Dijkstra) 알고리즘 : 그래프에서 출발 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나다익스트라 알고리즘은 도착 정점뿐만 아니라 다른 정점까지 최단 경로를 모두 찾는다.매번 최단 경로의 정점을 선택해 탐색을 반복한다. 동작 단계1. 출발 노드 설정출발 노드를 0으로로 설정하였다. 2. 최단 거리 테이블 초기화Known : 방문 여부Cost : 최단 거리 비용Path : 바로 이전 노드 (최단 경로 추적하기 위함)테이블 초기화 시 Cost (최단 거리 비용)은 출발 노드인 0은 0, 나머지 노드들은 INF (무한대)로 초기화 해준다.3. 최단 거리 테이블에서 방문을 하지 않은 노드들 중 가장 비용이 작은 노드를 방문해서 최단 거리 테이블 갱신 방문.. 2025. 1. 26. [알고리즘] DFS(깊이 우선 탐색), BFS(너비 우선 탐색) DFS (깊이 우선 탐색)다음 노드로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방식BFS (너비 우선 탐색)시작 노드에서부터 가까운 노드부터 먼저 탐색하는 방식스택을 이용한 DFS(깊이 우선 탐색) 구현// DFS boolean [] visited = new boolean[edges.length]; Stack stack = new Stack(); stack.push(0); // 탐색을 시작할 노드 스택에 추가 while (!stack.isEmpty()) { int vertex = stack.pop(); if (!visited[vertex]) { visited[vertex] = true; System.out.printl.. 2025. 1. 21. [자료구조] Trie 구현 Trie문자열을 저장하고, 빠르게 탐색하기 위한 트리 형태의 자료구조이다. 탐색 속도가 매우 빠르다 Trie 조건루트 노드는 항상 비어있다.루트 노드의 자식은 각 단어의 첫 글자이다.각 문자열의 마지막 글자는 색이 칠해진다. Trie 삽입 방법삽입할 문자열의 한 문자씩 루트의 자식부터 탐색을 하며 없으면 추가하고 있으면은 타고 들어가는 것을 반복한다.그리고 문자열의 마지막 문자가 되면 노드의 마지막 노드라는 것을 표시한다. APPLE, BEAR, BED, CAR, CARD, DADDY를 삽입해보았다.단어의 마지막 글자에는 색칠이 되어있고 BEAR와 BED의 BE까지는 동일하기 떄문에 타고 들어간 것을 볼 수 있다.CAR와 CARD도 CAR까지 동일하기에 타고 들어가서 마지막 글자만 각각 색칠되어있는 것을.. 2025. 1. 20. [자료구조] 레드-블랙 트리 (Red-Black Tree) 코드 구현 Red-Black 트리의 삽입 조건은 아래의 링크를 통해 확인하길 바란다.https://taeh00n.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACRed-Black-Tree [자료구조] 레드-블랙 트리(Red-Black Tree)레드 - 블랙 트리트리의 모양이 균형 잡히도록 각 노드들은 Red 혹은 Black의 색상을 가지고 모든 경우에서 O(lonN)의 시간 복잡도를 보장받는다.레드 - 블랙 트리 조건1. 루트 노드는 무조건 검은색taeh00n.tistory.comRBNodepublic class RBNode implements TreePrinter... 2025. 1. 20. [자료구조] AVL 트리 이론, 구현 AVL 트리AVL 트리는 이진 탐색 트리의 속성을 갖는다.왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1이다.높이 차이가 1보다 커지는 경우가 생기면 회전을 통해서 균형을 잡는다. 회전(Rotation)LL(Left - Left) case삽입 또는 삭제로 인해 Left - Left로 서브 트리가 불균형을 이루는 것을 LL 문제라 한다.4번 노드의 오른쪽 자식 노드를 6번 노드로 변경한다.4번 노드의 우측 자식인 것을 6번 노드의 왼쪽 자식노드로 변경한다. (4보다는 크고 6보다는 작기 때문)4번 노드를 부모 노드로 승격 시킨다.= 우회전 (Right Rotation) RR(Right - Right) case삽입 또는 삭제로 인해 Right- Right로 서브 트리가 불균형을 이루는 것을 RR .. 2025. 1. 20. [자료구조] 이진 탐색 트리(Binary Search Tree) 구현 이진 탐색 트리이진 탐색 트리는노드의 왼쪽 하위 트리엔 노드 값보다 작은 노드들만 있다.노드의 오른쪽 하위 트리엔 노드 값보다 큰 값들만 있다.=> 즉 데이터를 삽입할 때 거치는 노드보다 작으면 왼쪽, 크면 오른쪽으로 간다는 뜻이다.Nodepublic class Node implements TreePrinter.PrintableNode{ private int data; private Node leftNode; private Node rightNode;// 생성자. 노드 생성 시 오른쪽, 왼쪽 노드 비어있게. public Node(int data) { this.data = data; this.leftNode = null; this.rightNode.. 2025. 1. 19. 이전 1 2 다음
