밍의 기록들😉

퀵 정렬 개념원소(pivot(기둥/중심))를 하나 정하여, 해당 원소보다 작은 수들과 큰 수들로 나눈다. 1. pivot의 위치는 확정된 것2. pivot의 왼쪽과 오른쪽의 자리는 바뀌지 않는다. (= 왼쪽과 오른쪽을 따로 정렬해도 된다.) 퀵 정렬의 시간복잡도재귀적으로 구해야 한다.1. pivot을 정한다. = O(1)2. 작거나 같은 값과 큰 값을 분류한다. = O(n)3. 각각을 퀵정렬 한다. * T(n) = n개의 숫자를 퀵 정렬로 정렬하는데 걸리는 시간* T(n) = T(left) + T(right) + O(n) // 점화식 // left = pivot보다 작거나 같은 원소의 개수 // right = pivot보다 큰 원소의 개수 * pivot이 원소의 개수를 절반으로 나눈다고 가정하자* T(n..

합병 정렬 개념배열을 절반으로 나누어 각각을 정렬한 후, 합친다. 합병 정렬의 시간복잡도재귀적으로 구해야 한다.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) * 합병 정렬..

선택 정렬 구현 코드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

트리의 순회(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왼쪽 서브 트리 순회 - 노드 방문 - 오른..

트리의 표현 트리는 그래피이기 때문에, 그래프의 표현과 같은 방식으로 저장할 수 있음트리의 모든 노드는 부모를 하나 또는 0개만 가지기 때문에 부모만 저장하는 방식으로 저장 가능부모가 0개인 경우는 트리의 루트인데, 이 경우 부모를 -1이나 0으로 처리하는 방식을 사용함 트리의 부모만 저장하는 방식 이진 트리 이진 트리의 경우는 배열로 표현 가능부모의 노드가 x인 경우 자식의 노드는 2*x, 2*x+1로 나타냄 이진 트리의 경우는 배열로 표현 가능A[i][0]에 i의 왼쪽 자식, A[i][1]에 i의 오른쪽 자식을 저장 * 백준 알고리즘 참고

트리(Tree)자료구조의 일종사이클이 없는 그래프정점(Node, Vertex)간선(Edge) : 정점간의 관계를 나타냄정점의 개수 : V / 간선의 개수 : V-1 루트가 있는 트리 1번이 루트(root)임루트부터 아래로 방향을 정할 수 있음 루트 노드, 리프 노드, 단말 노드, 가지 노드 1번은 루트 노드(root node) 즉, 부모가 없는 최상위 노드4, 5, 6, 7번은 리프 노드(leaf node) 즉, 맨 마지막 끝 노드4, 5, 6, 7번은 단말 노드(terminal node)도 됨. 가지를 가지지 않는 노드. 즉 degree가 0인 노드1, 2, 3번은 가지 노드(branch node) 가지를 가지는 노드. 즉, degree가 0이 아닌 노드 부모와 자식 부모노드(Parent)와 자식노드(..

그래프의 탐색DFS : 깊이 우선 탐색BFS : 너비 우선 탐색 깊이 우선 탐색(DFS; Depth First Search)스택(=선행관계)을 이용하여 그래프를 탐색하는 방법나를 먼저 방문하고, 그 다음으로 인접한 노드를 차례로 방문(단, 방문했던 노드는 방문하지 않음)스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다. 인접 행렬을 이용한 구현 코드private static void dfs(int x) { check[x] = true; System.out.print(x); for(int i=1; i

그래프(Graph) 정점 6개, 간선 8개방향이 없는 그래프정점 : {1, 2, 3, 4, 5, 6}간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} 그래프의 구현 : 인접행렬정점의 개수를 V라고 했을 때V x V 크기의 2차원 배열을 이용정점의 연결관계를 0과 1로 표현A[i][j] = 1(연결이 되어있을 때), 0(연결이 되어있지 않을 때)양방향 그래프일 경우 A[i][j] = A[j][i] 구현 코드import java.util.Scanner; public class AdjacencyMatrix { public static void main(String[] args) { Scanner sc = new Scanner(Syste..

그래프(Graph)자료구조의 일종정점(Node, Vertex)간선(Edge) : 정점간의 관계를 나타냄G = (V,E)로 나타냄 경로(Path)정점 A에서 B로 가는 경로A-> C -> D -> E -> BA -> BA -> C -> BA -> C -> E -> B 사이클(Cycle)정점 A에서 다시 A로 돌아오는 경로A-> C -> B -> AA -> C -> E -> B -> AA -> C -> D -> E -> B -> A 단순 경로와 단순 사이클경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말함 방향 있는 그래프A -> C와 같이 간선에 방향이 있음A -> C는 있지만, C-> A는 없음 방향 없는 그..

큐(Queue)의 개념 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조 (선형 자료 구조) 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First In First Out) 방식으로 자료를 처리 큐(Queue)의 에러큐 오버플로우 : 큐의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없을 때 발생큐 언더플로우 : 큐에 제거할 자료가 없을 때 발생 큐(Queue)의 연산 시작과 끝을 표시하는 두 개의 포인터가 있는데, 프런트(F, Front)는 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터이며 삭제 작업을 할 때 사용한다. 리어(R, Rear)는 가장 마지막에 삽입된 자료가 위치한 기억공간을 가리키는 포인터이며 삽입..