삽입 정렬의 기본적인 연산은 데이터가 정렬되어 있을 때 이들 데이터 사이의 적당한 위치에 맞는 데이터를 삽입하는 것이다. 데이터를 삽입하고 난 뒤 그보다 오른쪽에 있던 데이터는 오른쪽으로 하나씩 자리를 옮겨줘야 한다. 삽입 정렬은 두 번째 데이터부터 정렬을 시작해 그 앞에 있는 데이터와 비교하고 삽입할 위치를 찾은 뒤 삽입할 위치의 공간 확보를 위해 데이터를 오른쪽으로 옮겨준 뒤 삽입하게 된다. 123456789for(i=2 ; in ; i++) {    w = a[i];    j=i-1;    while((wa[j])&&(j>=0)) {        a[j+1] = a[j];        j = j-1;    }    a[j+1] = w;}csw가 삽입할 데이터이다. (a[0]은 없고 배열은 a[1]부..

단순 정렬 알고리즘12345for(i=1 ; in ; i++) {    for(j=i+1; j=n ; j++) {        if( a[i] > a[j]) swap( a[i], a[j] );    }}Colored by Color Scriptercs i가 1부터 n-1까지 반복하고 j가 그 다음 데이터부터 n까지 반복하면서 a[i]이 a[j]보다 크면 서로의 값을 바꿔주어 가장 작은 값이 앞에 올 수 있도록 정렬하는 알고리즘이다.초기 상태가 [ 21  34  4  54  29  17 ]인 데이터 배열이 있을 때 위 알고리즘을 실행한다면[ 4  34  21  54  29  17 ][ 4  17  34  54  29  21 ]...[ 4  17  21  29  34  54 ]로 오름차순으로 잘 정렬된 것을..

AVL 트리 (Adelson-Velskii & Landis Tree) : 대표적인 균형 이진 탐색 트리각 노드에서 왼쪽 서브 트리의 높이(hL : height of left subtree)와 오른쪽 서브 트리의 높이(hR : height of right subtree)의 차이가 1 이하인 트리 특징- 왼쪽 서브 트리 - 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이 (hL - hR)를 노드의 균형 인수(BF, balance factor)라고 함- 각 노드의 균형 인수로 {-1, 0, +1} 값만 가지게 함으로써 균형을 유지함  루트 노드 50을 기준으로 왼쪽 서브 트리의 높이는 2, 오른쪽 서브 트리의 높이는 3이므로 BF = hL-hR = -1이 된다.위와 같은 방식으로 그림 속 노드..

Union-Find 알고리즘: 정점으로 구성된 집합을 관리하는 방법으로 집합의 합병과 요소가 어떤 부분집합에 속하는가를 판정하는 두 가지 연산.find 연산으로 특정 원소들을 집합 안에 있는지 없는지 판별하고, 없다면 두 원소들이 속한 트리들을 합병한다.Union = 2개의 원소로 이루어진 집합을 합치는 연산. = 합집합Find = 특정 원소가 속한 집합을 찾아주는 연산.총 세 가지 방법이 있다. 첫번째 방법 : 부모 노드 활용Find 연산123456789101112131415//자기 자신을 가지는 노드로 초기화.void initgroup() {  for(i=0;in;i++){    parent[i] = i;  }} //x가 속한 트리의 루트 값 반환.int find(int x) {  while( x !..

트리는 사이클이 없는 연결 그래프그래프에 대한 설명글은 👇🏻https://tildacoderecorder.tistory.com/107 [ 자료 구조 ] 그래프의 개념과 구조그래프 : 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 ( 트리는 1:N 관계 표현 ) 그래프 G = 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합. G = (V, E) 그래프의 종tildacoderecorder.tistory.com 신장 트리: n개의 정점으로 이루어진 무방향 그래프G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리깊이 우선 신장 트리 : 깊이 우선 탐색을 이용해 생성된 신장 트리너비 우선 신장 트리 : 너비 우선 탐색을 이용해 생성된 신장 트리 최소 비용 신장..

그래프: 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 ( 트리는 1:N 관계 표현 )그래프 G = 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합. G = (V, E) 그래프의 종류무방향 그래프: ( = 양방향 그래프) 두 정점을 연결하는 간선에 방향이 없는 그래프, 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현ex) 위 그림의 왼쪽 그래프가 G1, 오른쪽 그래프가 G2일 때. V(G2) = (A, B, C, D). E(G2) = {(A, B), (B, C), (B, D), (C, D)} 방향 그래프: 간선에 방향이 있는 그래프, 정점 Vi에서 정점 Vj를 연결하는 간선 즉, Vi -> Vj를 로 표현. Vi를 꼬리(tail), Vj를 머리(h..