밍의 기록들😉

[정렬] 합병 정렬 (Merge Sort) - 개념, 시간복잡도, 구현

합병 정렬 개념배열을 절반으로 나누어 각각을 정렬한 후, 합친다. 합병 정렬의 시간복잡도재귀적으로 구해야 한다.1. 왼쪽 합병정렬 = T(n/2)2. 오른쪽 합병정렬 = T(n/2)3. 합친다 = O(n) * T(n) = n개의 숫자를 합병정렬할 때의 시간복잡도* T(n) = 2 x T(n/2) + O(n) // 점화식 = 2(2T(n/4) + O(n/2)) + O(n) = 4T(n/4) + 2O(n) // 1번 대입 = 4(2T(n/8) + O(n/4)) + 2O(n) = 8T(n/8) + 3O(n) // 2번 대입 ...... // k번 대입 k+1 = log n = n x T(1) + log n x O(n) = n x O(1) + O(n log n) = O(n) + O(n log n) * 합병 정렬..
자료구조, 알고리즘/기본다지기 2018. 9. 10. 16:56
[정렬] 선택 정렬, 삽입 정렬, 버블 정렬의 구현

선택 정렬 구현 코드import java.util.Scanner; public class SortSelection { // 선택 정렬 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] data = new int [100]; for(int i=0; i
자료구조, 알고리즘/기본다지기 2018. 9. 10. 16:55
[트리] 트리의 순회

트리의 순회(Tree Traversal)트리의 모든 노드를 방문하는 순서트리 내에 어떠한 자료가 담겨있는지를 알기 위함그래프의 경우 DFS와 BFS가 있음트리에서도 위의 두 방법을 사용가능 하지만, 트리에서만 사용할 수 있는 방법이 3가지 있음1) 프리오더 = 전위 순회2) 인오더 = 중위 순회3) 포스트오더 = 후위 순회세 방법의 차이는 노드 방문을 언제 하냐의 차이임 전위 순회, 프리오더(Pre-order)Root - L - R노드 방문 - 왼쪽 서브 트리 순회 - 오른쪽 서브 트리 순회순서 : A-B-D-E-C-F-G그래프의 DFS의 순서와 같음노드 방문 왼쪽 서브 트리 순회 오른쪽 서브 트리 순회 중위 순회, 인오더(In-order)L - Root - R왼쪽 서브 트리 순회 - 노드 방문 - 오른..
자료구조, 알고리즘/기본다지기 2018. 9. 9. 21:54
Prev 1 ··· 4 5 6 7 8 9 10 ··· 16 Next