뚜sh뚜sh

최소 신장 트리(Minimum Spanning Tree, MST) 가중치 그래프에서 가중치의 합이 최소가 되는 신장 트리를 말한다. 최소 신장 트리를 찾는 것은 네트워크 설계, 클러스터 분석, 지리 정보 시스템 등 다양한 분야에서 중요한 문제로 다루어진다. 최소 신장 트리를 찾는 데에 주로 사용하는 알고리즘 1. 크루스칼(Kruskal) 알고리즘 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 가중치가 가장 낮은 간선부터 순서대로 선택하면서 신장 트리를 구성한다. 선택한 간선이 사이클을 형성하는 경우, 그 간선은 제외한다. 이 과정을 모든 정점이 연결될 때까지 반복한다. 2. 프림(Prim) 알고리즘 시작 정점을 선택한다. 선택된 정점과 인접한 간선 중에서 가중치가 가장 낮은 간선을 선택하고, 해당..

신장 트리(Spanning Tree) 연결된 그래프에서 모든 정점을 포함하며, 사이클이 없는 부분 그래프이다. 신장 트리의 주요 특징 모든 정점 포함 : 신장 트리는 원래 그래프의 모든 정점을 포함한다. 사이클 없음 : 신장 트리는 사이클이 없어야 한다. 이는 신장 트리가 트리의 정의를 따르기 때문이다. 간선 수 : 그래프의 정점 수가 n일 때, 신장 트리는 정확히 n−1개의 간선을 가진다. 이는 모든 트리가 가지는 기본적인 성질이다. 유일성 : 신장 트리는 항상 유일하지는 않다. 하나의 그래프에는 여러 개의 신장 트리가 존재할 수 있다. 이러한 특성 때문에 신장 트리는 네트워크 설계, 알고리즘, 그리고 다양한 컴퓨터 과학 분야에서 중요하게 활용된다. 신장 트리를 찾는 알고리즘 1. 깊이 우선 탐색(DF..

그래프객체들의 집합과 이 객체들을 연결하는 선들의 집합으로 이루어진 수학적 구조이다. 그래프는 정점(Vertex) 또는 노드(Node)라고 불리는 객체들과, 이 정점들을 연결하는 간선(Edge) 또는 링크(Link)로 구성된다. 그래프는 복잡한 관계나 네트워크를 모델링하는 데 유용하다.   그래프의 기본 용어정점(Vertex) : 그래프의 기본 단위로, 위치를 나타낸다. 때로는 노드(Node)라고도 한다.간선(Edge) : 두 정점을 연결하는 선이다. 간선은 방향이 있거나 없을 수 있다.방향 그래프(Directed Graph) : 간선에 방향성이 있는 그래프. 간선이 (A, B)라면, A에서 B로의 연결을 나타낸다.무방향 그래프(Undirected Graph) : 간선에 방향성이 없는 그래프. 간선이 A..

스택과 큐는 배열에서 발전된 형태의 자료구조이다 스택과 큐의 핵심 이론 스택 - 스택은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조임 - 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있음 - 새 값이 스택에 들어가면 top이 새 값을 가리킴 - 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 되는 것임 - 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적임 !! - 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통함 스택 용어 - 위치 top : 삽입과 삭제가 일어나는 위치를 뜻함 - 연산 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터..

구간 합 - 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 - 코딩 테스트에서 사용 빈도가 높으니 알아두기 !! 구간 합의 핵심 이론 // 배열 A가 있을 때 합 배열 S는 아래와 같이 정의함 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됨 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소함 합 배열 S를 만드는 공식 // 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] 구간 합을 구하는 공식 S[j] - S[i-1] // i에서 j까지 구간 합 2차원 구간 합 배열 D..

배열 - 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 - 배열의 값은 인덱스를 통해 참조할 수 있음 - 선언한 자료형의 값만 저장할 수 있음 배열의 특징 인덱스를 사용하여 값에 바로 접근할 수 있음 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움, 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요함 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음 구조가 간단하여 코딩 테스트에서 많이 사용함 리스트 - 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 ※ 노드는 컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 부르는 말 리스트의 특징 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서..