IT 일반/자료구조(개념) - [인강] 코드잇, [대학원] 전공 수업 (16) 썸네일형 리스트형 [대학원-자료구조 7~] Hash Table : an example of dictionary Hash Table Hash Table의 역할:동적 집합(dynamic set)을 다루며 삽입(INSERT), 탐색(SEARCH), 삭제(DELETE) 연산을 지원하는 데이터 구조.컴파일러의 심볼 테이블(symbol table)과 같은 곳에서, 임의의 문자열을 키(key)로 사용해 효율적으로 요소를 관리.효율성:해시 테이블은 딕셔너리(dictionary)를 구현하기 위한 효과적인 데이터 구조로 사용됩니다.탐색 시간:최악의 경우: Θ(n) (모든 요소가 충돌하여 단일 체인으로 연결된 경우).일반적인 경우(합리적인 가정 하): 평균 탐색 시간은 O(1) (상수 시간).충돌 해결 방법:Chaining (체이닝): 같은 해시 값이 여러 번 발생할 때, 연결 리스트를 사용해 충돌을 해결.Open Addressin.. [대학원-자료구조 6] MST : Kruskal's Alg., Prim's Alg. 본 게시물의 전문은 chatgpt 기반의(언어모델 : gpt 4o) 답변임을 알려드립니다.1. Minimum Spanning Tree (MST)란?Spanning Tree (신장 트리):신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 뜻한다. 이 부분 그래프는 여러개가 존재할 수 있다. 주어진 그래프 G의 모든 정점을 포함하는 서브그래프입니다.이 서브그래프는 트리여야 하며, 즉 사이클이 없어야 합니다.예를 들어, 정점이 4개인 그래프의 모든 정점을 포함하면서 간선 수는 3개(=n-1)가 되어야 합니다.Minimum Spanning Tree (MST):최소 신장 트리 (MST, Minimum Spanning Tree) 란 가능한 여러 신장 트리 중에서 가중치의 합이 최소인 신장 트.. [대학원-자료구조 5] Disjoint Sets(서로소 집합) 자료구조 본 게시물의 전문은 chatgpt 기반의(언어모델 : gpt 4o) 답변임을 알려드립니다.Disjoint Set 자료구조는 연결 성분 탐색과 같은 그래프 알고리즘에서 효과적으로 사용됩니다. 각 노드가 속한 집합을 빠르게 찾고, 집합을 병합함으로써 효율적인 그래프 탐색이 가능합니다. 1. Disjoint Set (서로소 집합) 자료구조개념:Disjoint Set 자료구조는 서로 겹치지 않는 여러 집합들을 관리합니다.이 자료구조는 집합 간 교집합 없이 독립적인 집합의 모음을 유지합니다.기본 연산:make-set(x):새로운 집합을 생성하고, 원소 x를 그 집합의 멤버로 추가합니다.ex) {x} 형태로 집합 생성.find-set(x):원소 x가 속한 집합의 대표 원소(대표자)를 반환합니다.대표자는 해당 집합을.. [대학원-자료구조 4] Elementary Graph Algorithms : BFS, DFS 1. 그래프 자료구조 : 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위함- 선형적 관계 : 배열, 링크드 리스트- 계층적 관계 : 트리- 연결관계 : 그래프 그래프- 연결 데이터를 저장할 수 있는 자료 구조- 예시 : 다양한 연결 관계(ex. 도시들 관계, 웹페이지 하이퍼링크 등)를 나타내는 데 쓰이는 유연한 구조로, 알고리즘/프로그래밍에서 입력값으로 바로 활용하기에는 추상적임 그래프의 표현방식 두 가지- 그래프에서 두 노드 사이의 관계를 말할 때 adjacent(노드간에 엣지가 있음) 하다/안하다라고 얘기한다.① 인접 행렬(adjacency matrix)(directed graph에서의 adjacency matrix)- from에서 to로가는 관계일 때 to의 원소에 1, 나머지는 전부 0- ad.. [대학원-자료구조 3] 기타 정렬 알고리즘 - MergeSort, QuickSort 기타 정렬 알고리즘 - Merge-Sort, Quicksort : Recursive한 알고리즘(ChatGPT)두 알고리즘 모두- 비교 기반 정렬 알고리즘- Divide-and Conquer(분할 정복) 기법 활용- Recursive한 알고리즘1) MERGE-SORT(ChatGPT)- Merge Sort는 분할 정복(Divide-and-Conquer)을 활용하는 정렬 알고리즘으로, 이 MERGE 함수는 두 개의 정렬된 부분 배열을 병합하여 최종적으로 정렬된 하나의 배열로 만드는 핵심 역할을 함- Merge Sort는 재귀적으로 배열을 반으로 나누어 각각 정렬한 뒤, 그 정렬된 부분을 병합(merge)하는 과정에서 정렬을 완성- 이 MERGE 함수는 두 개의 정렬된 배열을 받아 하나의 정렬된 배열로 합치는 .. [대학원-자료구조 1~2] Tree와 Graph, Heap 자료구조 : 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위함- 선형적 관계 : 배열, 링크드 리스트- 계층적 관계 : 트리- 연결관계 : 그래프 ※ 코드잇 마저 수강한 후 보충하기, 과제 등 1페이지 보면서 보충하기1. Tree와 Graph1) GraphGraph- 연결할 객체를 나타내는 정점(Vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성- 연결 데이터를 저장할 수 있는 자료 구조- 예시 : 다양한 연결 관계① Undirected Graph (무향 그래프) G(V, E)에서- V = {노드들의 원소} : 정점의 집합- E : the set of unordered point of V ② Directed Graph (유향 그래프) G(V,E)에서- V = {노드들의 원소} : 정점의.. [코드잇-자료구조3 : 그래프의 구조와 탐색] 2. 그래프 탐색 본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 세번째 주제인 '그래프의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.- 강의 url : https://www.codeit.kr/topics/graphs 그래프의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇교통 앱에서 지하철역간 최단 거리를 알려주거나 SNS에서 사람들의 친구 관계를 볼 수 있는 것처럼, 우리 주변에는 다양한 연결 관계를 표현하는 데이터가 있습니다. 그래프는 연결 관계를 가지www.codeit.kr1. 그래프 탐색이란?그래프 탐색보통 자료구조에서 말하는 탐색 : 주어진 조건을 만족하는 데이터를 찾아내는 것그래프 탐색 : 하나의 노드를 시작점으로 해서 연결된 노드들을 모두 찾는 것을 의미- 그래프를 탐색할 때 시작점 .. [코드잇-자료구조3 : 그래프의 구조와 탐색] 1. 그래프 본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 세번째 주제인 '그래프의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.- 강의 url : https://www.codeit.kr/topics/graphs 그래프의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇교통 앱에서 지하철역간 최단 거리를 알려주거나 SNS에서 사람들의 친구 관계를 볼 수 있는 것처럼, 우리 주변에는 다양한 연결 관계를 표현하는 데이터가 있습니다. 그래프는 연결 관계를 가지www.codeit.kr1. 연결 관계 데이터와 그래프자료구조 : 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위함- 선형적 관계 : 배열, 링크드 리스트- 계층적 관계 : 트리- 연결관계 : 그래프 그래프- 연결 데이터를 저장할 수 있는 자.. [코드잇-자료구조2 : 트리의 구조와 탐색] 2. 힙 본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 두번째 주제인 '트리의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.- 강의 url : https://www.codeit.kr/topics/trees?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz 트리의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇트리는 계층적 데이터를 효과적으로 표현할 수 있는 자료 구조입니다. 데이터가 서로 연결되어 있는 모습이 나무에서 가지가 뻗어 나간 모습과 비슷하다고 해서 트리라는 이름이 붙었죠. 트리www.codeit.kr 1. 힙이란?아래의 두 가지 조건을 모두 만족하는 트리① 형태속성 : 힙은 완전 이진 트리이다. ② 힙 속성 : 모든 노드의 .. [코드잇-자료구조2 : 트리의 구조와 탐색] 1. 트리란? 본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 두번째 주제인 '트리의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.- 강의 url : https://www.codeit.kr/topics/trees?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz 트리의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇트리는 계층적 데이터를 효과적으로 표현할 수 있는 자료 구조입니다. 데이터가 서로 연결되어 있는 모습이 나무에서 가지가 뻗어 나간 모습과 비슷하다고 해서 트리라는 이름이 붙었죠. 트리www.codeit.kr1. 계층적 관계트리구조 : 계층적 관계를 저장하고 활용하기에 적합한 자료 구조- 배열, 링크드 리스트는 선형적 자료구조로 계층.. 이전 1 2 다음
