Learning-log -CS/Data Structure & Algorithm25 자료구조 - 해시테이블 (Java, HashMap) 1. 개념해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소로 하여 데이터를 key와 함께 저장하는 자료구조key를 활용하여 value값 조회 가능매우 빠른 평균, 삽입, 삭제, 탐색연산이 제공되는 자료구조 구성- key hash function의 input고유한 값키 값 그대로 저장할 경우 다양한 키의 길이만큼 구성해야하므로 일정한 길이의 해시로 변경함- hash functionkey를 고정된 길이의 해시로 변경해주는 함수로 해시 함수를 거치는 과정을 "hashing"이라고 함서로 다른 key가 같은 hash 값을 같게 되는 경우를 해시 충돌이라고 하며, 이 충돌이 적을 수록 좋은 해시함수라고 할 수 있음- value저장소에 저장되는 값- hash table해시함수를 사용하여 해시값으로 매.. 2024. 5. 24. 자료구조 - 한방향 연결리스트, 양방향 연결리스트 1. 연결리스트1) 개념자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하나의 전체적인 자료구조를 이룸.링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않음자료의 크기를 동적으로 조절해 메모리의 효율적인 사용 가능.(추가 삭제 빠름)2) 노드연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위- 구성요소데이터 필드 : 원소의 값링크 필드 : 다음 노드의 주소 ( 마지막 노드는 링크 값을 null로 가짐)- 헤드 : 리스트의 처음 노드를 가리키는 레퍼런스 2. 한방향 연결리스트1) 연결구조노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가짐헤드가 가장 앞의 노드를 .. 2024. 5. 24. (알고리즘/Java) 벨만-포드 (Bellman-Ford) 알고리즘 1. 개념 그래프의 최단 경로를 구하는 알고리즘으로 벨만-포드 외에도 그래프의 다익스트라(Dijkstra)와 플로이드-와샬(Floyd-Wrasahll)이 있으며 이전 포스팅을 통해 다뤘었다. 벨만-포드 알고리즘은 다음과 같은 특성을 가진다. 그래프의 최단 경로를 구하는 알고리즘 하나의 정점에서 출발하는 최단거리를 구함 음수 가중치는 허용하되, 음수 사이클이 없어야 함 O(nm)의 시간복잡도 동적 계획법 사용 하나의 출발지를 지정해 최단거리를 구한다는 측면에서 다익스트라와 같지만 음수가중치를 허용한다는 점에서 다익스트라와 차이가 있다. 2. 알고리즘 단계 알고리즘 과정 벨만-포드 알고리즘의 과정에 대해 단계별로 살펴보자. 다익스트라와 마찬가지로 dist배열을 통해 최단거리를 기록할 것이다. N개의 노드가 .. 2024. 2. 25. 플로이드 워셜 알고리즘 1) 개념 - 모든 최단 경로를 구하는 알고리즘 - 다익스트라가 하나의 정점에서 모든 정점까지의 최단거리를 구한다면, 플로이드-워셜 알고리즘은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있다. 다익스트라에 대한 설명은 아래 링크를 통해 확인하자. 2023.07.05 - [Learning-log -CS/Data Structure & Algorithm] - (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교)\ (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의.. 2023. 7. 5. (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있음 탐욕기법을 사용한 알고리즘으로 MST 프림 알고리즘과 유사 2) 알고리즘 단계 D : 거리 계산을 위한 배열 U : 경로 배열 출발 노드(a)를 선택 후 a와 연결된 정점들에 대해 배열(D) 값을 가중치로 업데이트한다. >> 다른 정점들은 아직 도달할 수 없는 정점이므로 배열 값 무한대인 상태(배열 초기값을 무한대로 설정해두기)이다. D배열 중 거리가 가장 작으면서 U에 없는 정점(b) 선택한다. a에서 b를 경유해서 갈 수 있는 정점 후보를 보고 그 때 가중치 값을 D에 UPDATE(D[b] +a[b][c])하고 D에 .. 2023. 7. 5. (자료구조 & 알고리즘 정리) 최소 비용 신장 트리, Kruskal, Prim (2023.06.25) 1. 최소 비용 신장 트리 1) 신장트리(Spanning Tree) 란? - 그래프 내의 모든 정점을 포함하는 트리 - 최소 연결을 해서 간선의 수가 가장 적음 2) 최소 비용 신장 트리란? - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 3) 최소 비용 신장트리의 특징 - 각 간선의 가중치가 동일하지 않을 때, 단순히 가장 적은 간선을 사용한다고 최소 비용 신장 트리를 구할 수 있는 것이 아님 - 가중치를 고려하여 최소비용을 선택해야 함 - N개의 정점을 가지는 그래프에서는 반드시 N-1개의 간선만을 사용 - 사이클이 포함되어서는 안됨 으아리.,ㄴㅁ얼매ㅑ어리ㅏㅁㄴ 2. Kruskal 알고리즘 1) 탐욕적인 방법을 사용하여 간선을 하나씩 선택해서 MST를 찾는 알고리즘 2) 구현 방식 최초.. 2023. 6. 25. 이전 1 2 3 4 5 다음
