개발조아

신장 트리중 가중치의 합이 최소인 신장트리 크루스칼 알고리즘 간선 선택 기반 알고리즘 동작 모든 간선을 가중치로 오름차순 정렬 정렬된 간선에서 사이클이 형성되지 않도록 간선을 선택 오름차순으로 되어 있으므로 작은 것부터 먼저 선택하게 됨 사이클이 형성되는 간선은 제외 선택한 정점을 MST 집합에 포함 간선의 개수가 n-1개가 될때까지 수행 Union-Find 알고리즘으로 사이클 형성 확인 프림 알고리즘 정점 선택 기반 알고리즘 동작 시작 정점을 MST 집합에 포함 MST 집합에 연결된 정점 중 아직 방문하지 않았고 가중치가 가장 작은 간선 선택 가장 낮은 가중치를 먼저 선택 선택한 간선으로 연결된 정점 MST 집합에 포함 간선의 개수가 n-1개가 될때까지 수행 우선순위 큐로 구현 다익스트라와의 차이 다익..

한 정점에서 다른 한 정점까지의 최단 경로 가중치가 없거나 1 인경우 BFS 가중치가 양수인 경우 다익스트라 가중치가 음수인 경우 벨만포드 모든 정점에서 다른 정점으로 최단 경로 위의 알고리즘으로도 풀이 가능 플로이드 와샬 다익스트라 알고리즘 가중치가 가장 적은 노드를 우선적으로 선택하여 탐색하는 방식 동작 1시작 노드와 연결된 정점과의 가중치 업데이트 및 시작 노드 방문 표시 2.방문한 노드에 연결된 정점들의 가중치가 작은 정점을 선택 3.해당 노드로 가는 가중치 업데이트 및 방문 표시 4.아직 선택되지 않은 노드가 남았다면 2,3 과정 반복 구현방법 우선순위 큐를 활용하여 구현 가능 최단 경로로 이동해야하므로 우선순위큐 최소힙으로 구성 항상 최소 가중치의 노드를 선택하여 탐색하도록 함 시간 복잡도 우..

깊이 우선 탐색(Depth First Search : DFS) 한 정점으로부터 연결된 한 정점으로만 탐색하여 끝까지 탐색하는 방법 한 정점에서 연결된 정점을 찾아 해당 정점으로 이동 만약 연결된 정점이 없다면 이전 정점으로 이동해 다른 정점 탐색 모든 정점에 대해서 탐색이 이루어진다 구현 방법 Stack 현재 정점에 연결된 다른 정점을 찾을 시 돌아갈 정점, 즉 현재 정점을 스택에 저장 현재 정점에서 연결할 정점이 없어면 스택에서 다시 정점을 빼서 수행 재귀로도 구현 가능 현재 정점에 연결된 다른 정점이 있다면 다시 재귀 호출 현재 정점에서 연결할 정점이 없다면 해당 재귀 탈출 시간 복잡도 O(V+E) 너비 우선 탐색(Breadth First Search : BFS) 한 정점에 연결된 모든 정점을 모두 ..

정점(Vertex)와 간선(Edge)의 집합 트리 또한 그래프의 일종이고 이때 트리는 사이클을 허용하지 않는 그래프이다 무방향 그래프 말 그대로 간선의 방향이 없는 그래프 (3,4)나 (4,3)이나 같은 간선 방향 그래프 간선에 방향이 있는 그래프 (3,4)와 (4,3)은 다른 간선 Degree 무방향 그래프 간선의 개수 방향 그래프 Indegree : 정점으로 들어오는 간선 outdgree : 정점에서 나가는 간선 그래프를 표현하는 방법 인접 행렬(Adjacency Matrix) 정점과 정점의 연결 관계를 행렬로 표현 연결 관계를 한번에 파악할 수 있다 간선의 개수와 무간하게 정점의개수^2의 공간이 필요 해당 정점에 연결된 간선의 정보 파악 위해선 O(정점의 개수)의 시간이 걸린다 인접 리스트(Adja..

완전 이진 트리의 일종 중복된 값을 허용 Max Heap 트리의 루트가 가장 큰값인 트리 Min Heap 트리의 루트가 가장 작은값인 트리 삽입 가장 끝 칸에 새로운 데이터 삽입 해당 위치부터 루트노드까지 올라가면서 종류에 맞게 값 변경 삭제 루트 노드를 제거하는 것 루트와 가장 끝칸의 노드의 값을 변경 힙의 사이즈 1 감소 루트 노드에서 다시 힙 구성 시간 복잡도 heapify 힙 구성 트리의 높이만큼 수행되므로 O(logn) build heapify O(nlogn) 원소를 하나씩 넣고 힙 구성 O(n) 모든 원소를 배열에 넣고 n/2번째 부터 힙 구성

이진트리의 일종 효율적인 탐색 가능 규칙 노드의 키는 유일해야한다 왼쪽 자식노드는 부모노드 보다 값이 작다 오른쪽 자식노드는 부모노드 보다 값이 크다 왼쪽, 오른쪽 자식 노드도 이진 탐색 트리 형태이다 탐색은 O(logn)의 시간복잡도를 갖는다 삽입 루트 노드에서 시작하여 단말 노드에 도달할 때까지 규칙에 맞게 진행하여 삽입 삭제 자식이 없을 시는 그냥 삭제 자식이 1개 있을 시 해당 자식을 올림 자식이 2개 있을 때 왼쪽자식 중 가장 큰값 또는 오른쪽 자식 중 가장 작은값을 올림

비선형 자료구조 계측적 관계를 표현한 자료구조 Node(노드) Edge(간선)으로 구성 특징 사이클이 존재하지 않는다 루트에서 한노드로 가는 경로는 유일하다 노드의 개수가 n이라면 간선은 n-1개 이다 트리 순회 전위순회(pre-order) 부모노드를 먼저 탐색 후 왼쪽, 오른쪽 자식 노드로 탐색 중위순회(in-order) 왼쪽노드를 먼저 탐색 후 부모, 오른쪽 자식 노드로 탐색 후위순회(post-order) 왼쪽노드, 오른쪽 노드 탐색 후 부모노드 탐색 레벨순회(level-order) 루트부터 계층별로 탐색 이진 트리(Binary Tree) 자식이 최대 두개인 트리 포화 이진 트리 모든 레벨이 꽉찬 트리 완전 이진 트리 왼쪽 부터 차례대로 채워진 이진트리

연속적인 메모리에 저장되지 않는 선형 자료구조 각각의 노드들이 데이터 필드와 인접한 노드에 참조하기 위한 데이터로 구성 배열 VS 연결리스트 배열과 연결리스트 선형으로 데이터를 저장하는 구조 배열 배열은 전체 길이가 고정되어 있고 사전에 길이를 알고 할당 해줘야함 탐색이 빠르다 요소를 삽입,삭제할 때 비용이 많이 듬 중간에 삽입하면 뒤로 나머지를 밀고 삽입 삭제 시 뒤에 있는 것을 모두 당겨야함 연결리스트 전체 길이를 알필요도 없고 사전에 만들어둘 필요가 없음 삽입, 삭제시 용이 삽입 시 해당 위치의 앞,뒤 노드와 연결만 시켜주면 됨 삭제 해당 위치의 앞뒤 노드를 연결 시켜주면 됨 탐색이 느리다 해당 위치에 바로 접근할 수 없어 head부터 순차적으로 접근해서 가야함 종류 노드끼리 방향을 어떻게 지정하느..