IT Hyeon's study IT Hyeon's study

최소 신장 트리 (MST, Minimum Spanning Tree) 를 만들기 위한 대표적인 알고리즘 중 하나이다  특징 1. 그리디 알고리즘크루스칼 알고리즘은 그리디 알고리즘의 일종으로 매 순간 최적의 선택을 하면서 전체 최적해를 찾는다이 말은 즉, 간선의 가중치가 가장 작은 것부터 차례대로 선택하여 최소 신장 트리를 구성 2. 간선 중심!간선의 가중치에 기반하여 간선을 선택한다그래서 간선을 정렬한 후 가장 가중치가 작은 간선부터 선택하는 방식이다 3. 간선 수가 적을 때 효율적간선의 수가 정점의 수에 비해 적을때 크루스칼 알고리즘이 효율적으로 동작한다왜냐하면 전체 간선을 정렬한 후 선택하는 방식이기 때문이다  과정1. 초기 상태는 정점은 서로 연결되어 있지 않는 상태이다2. 간선을 하나씩 추가하면서 ..

정의1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을때 까지 탐색하는 알고리즘배열이나 리스트에 순차적으로 접근해야 할 때 두개의 포인트의 위치를 기록하면서 처리한다배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)의 시간복잡도로 단축 시킬 수 있다이분탐색 알고리즘과 유사한 방식이다 동작 방식왼쪽 left, 오른쪽 right 또는 start, end 이런 식으로 포인트의 변수 이름을 지정한다조건은 항상 두 포인터의 관계는 left  1. 초기화  두개의 포인터를 초기화 한다, 이 포인터들은 배열의 시작과 끝 또는 특정 위치에서 시작할 수 있다 2. 반복 처리 반복문을 사용하여 두 포인터가 특정 조건을 만족할 때까지 ..

이분 탐색  /  이진 탐색 - 데이터가 정렬돼 있는 상태에서 값을 찾아내는 알고리즘 이다- 데이터의 중앙값과 찾고 하는 값을 비교해서 데이터의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다- 데이터가 정렬되어 있어야만 사용할 수 있다 기능특징 시간 복잡도타깃 데이터 탐색중앙값 비교를 통한 대상 탐색 축소 방식O(logN)  탐색 과정1) 현재 데이터셋의 중앙값을 선택한다 2) 중앙값 > 타깃 데이터 일때 중앙값 기준으로 왼쪽 데이터셋을 선택한다3) 중앙값 4) 과정 1~3 을 반복하여 중앙값 == 타깃 데이터일때 탐색을 종료한다  Java로 하는 이분 탐색 구현  1. 반복문 구현public boolean searchBinary (int[] array, int n) { int left = 0; in..