미누에요

퀵 정렬(Quick Sort)퀵 정렬은 평균적으로 가장 빠른 정렬 방법으로 알려져있다.분할 정복(Divide and Conquer) 방법을 사용하는 정렬이다. 퀵 정렬은 피봇(pivot)이라는 값을 기준으로 리스트를 나누어 정렬한다.피봇의 설정은 여러가지 방법이 있는데, 우리는 첫번째 값을 피봇으로 설정하는 비교적 간단한 방법을 사용하겠다. 연산 방법은 쉽게 말하자면피봇을 기준으로 왼쪽으로 이동하며 피봇보다 작은 값을 찾고 low에 저장한다, 오른쪽으로 이동하며 피봇보다 큰 값을 찾아 high에 저장한다.그리고 그 두 값의 위치를 바꾼다.반복한다.그리고 high가 low보다 앞에 있다면 종료한다. pivot과 high의 위치를 바꾼다. 글로는 설명이 어려울 거 같아 사진을 참조했다.개념이 이해가 어렵다면..

삽입 정렬(Insertion Sort)삽입 정렬은 1차원 배열 상에서 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬을 수행하는 방법이다.오름차순으로 정렬한다면, 위와 같은 오름차순으로 정렬된 리스트와 정렬되지 않은 리스트로 나누고정렬되지 않는 리스트에서 첫번째 원소를 정렬된 리스트의 각 값과 비교하여 알맞는 위치에 끼워넣는 방식이다.   위 방식을 구현하기 위해서는 정렬된 리스트와 정렬되지 않는 리스트의 인덱스값이 각각 필요하다.0부터 정렬된 리스트의 인덱스까지, 그리고 정렬되지 않은 리스트의 인덱스 부터 배열의 끝까지로 나누기 위함이다. 위 사항들을 고려해서 코드를 작성해보았다. 삽입 정렬  #include // 삽입 정렬 함수void insertionSort(int arr[], int n) { ..

Dijkstra 알고리즘 Dijkstra 알고리즘은 가중치 그래프에서, 한 정점에서 다른 정점으로 바로 가는 것보다 다른 정점을 거쳐서 가는 가중치 값이 더 효율적인 경우에 그 경로를 최단경로로 정하는 알고리즘이다.  식으로 표현하면 위와 같다.정점 v에서 정점 u까지 가는 최단 경로를 찾는 과정에서, v에서 u로 가는 기존에 알고있던 가중치값보다 어떤 k라는 정점을 거쳐서 가는 가중치가 작은 경우, 그 가중치값이 distance[u], 즉 v에서 u로 가는 최단거리로 업데이트되는 것이다. 예시 그래프로 자세히 보자.  위 그래프에서 시작 정점을 0이라고 해두고 시작하자.0에서 갈 수 있는 정점은 1, 2, 3이다. 이 세 정점에 대하여 간선의 가중치 값을 기록한다.그려둔 가중치 값 중 가장 작은 값을 ..

Kruskal 알고리즘굉장히 유명한 알고리즘이다.최소비용신장트리(MST, Minimum Spanning Tree)를 찾는 알고리즘이다. 예를 들어 위와 같은 가중치 그래프가 있다고 하자. Prim 알고리즘은 시작 정점이 필요했지만, Kruskal 알고리즘은 시작 정점이 필요하지 않다.Kruskal 알고리즘은 가장 작은 가중치를 갖는 간선을 찾아 여러 개의 작은 트리로 만들어두고, 붙이는 알고리즘이다. 쉽게 풀어서 차근차근 이야기해 보자. 우선, 가장 작은 가중치인 7이 연결된 두 정점을 선택하게된다.그리고 다음으로 작은 가중치인 10이 연결된 정점들을 묶는다. 그 다음으로 큰 12 를 묶는다.Kruskal 알고리즘은 연결되지 않는 게 많을 것이다. 이상해하지 말자. 곧 연결될테니다음으로 큰 13  13이..

최소비용 신장트리(MST, Minimum Spanning Tree)가중치 그래프에서, 간선들의 비용 합이 최소가 되는 신장트리최소비용 신장트리는 그래프가 아니라 트리 이기때문에 사이클이 구성되지 않아야한다.   우선, 최소비용 신장트리가 아니라 일반적인 신장 트리의 모습이 아래에 있다.  위 그림처럼 그래프에서 나올 수 있는 신장트리는 여러 개일 수 있다.  하지만, 일반적인 신장트리와 다르게 최소비용 신장트리는 간선에 가중치가 있기때문에, 그 값에 따라 최소한의 비용으로 나타낼 수 있는 트리여야 한다.   위 사진처럼 각 간선에 가중치가 있고, 그 가중치가 가장 작은 간선으로 이동하는 방식으로 얻은 트리가 최소비용 신장트리, MST이다.   최소비용 신장트리(MST)를 구하는 방법에는 크게 Prim 방..

그래프(Graph)정점(vertax)과 간선(edge)로 이루어진 자료구조이다. 방향성을 가지고 있느냐에 따라 방향 그래프와 무방향 그래프로 나누어진다.  위 그림에서 왼쪽이 무방향 그래프, 오른쪽이 방향 그래프를 나타낸다.  이러한 그래프는 보통 인접행렬, 인접 리스트의 두 가지로 표현한다.  인접 행렬각 정점(vertax)에 대해서 간선(edge)가 연결되어 있는 경우에 1을 작성하는 방법이다. 위 왼쪽 무방향 그래프의 인접 행렬은 아래와 같다.  해당 행과 열이 교차되는 곳에 1이 있다는 것은 두 정점이 간선으로 연결되어있다는 뜻이다.그리고 왼쪽 상단에서 오른쪽 하단으로 가는 축을 기준으로 대칭을 가지는 것을 확인할 수 있다.무방향 그래프는 방향성이 없기 때문에 1과 0이 관계가 있으면 0과 1도 ..

이진 탐색 트리(Binary Search Tree)한 노드를 기준으로 왼쪽 자식에 있는 트리는 해당 노드보다 작다한 노드를 기준으로 오른쪽 자식에 있는 트리는 해당 노드보다 크다 위 그림처럼, 모든 각 노드들에 대하여 왼쪽은 더 작은 값이, 오른쪽은 더 큰 값이 위치해야한다.  위와 같은 이진탐색트리를 코드로 구현해보겠다.구현할 기능은 아래와 같다.이진탐색트리에서 가장 작은 값이진탐색트리에서 가장 큰 값이진탐색트리에서 주어진 키 값 찾기이진탐색트리에서 새로운 키 삽입이진탐색트리에서 주어진 키 값 삭제  이진탐색트리에서 가장 작은 값해당 노드에서 왼쪽 트리가 더 작아야 하므로 왼쪽으로 쭉 내려가면 가장 작은 값이 나온다.int min_BST(Node *root) { Node *temp = root; ..

이진트리 이진트리는 완전 이진트리, 포화이진트리, 일반 이진트리    위를 바탕으로 기본적인 코드를 작성해보겠다.  기본 코드#include#includetypedef struct _tree{ struct _tree *left; int data; struct _tree *right;} Tree;void AddData(Tree **position, int value) { *position = (Tree *)malloc(sizeof(Tree)); (*position)->data = value; (*position)->left = NULL; (*position)->right = NULL;}void initData(Tree **head) { AddData(head, ..

완전 이진트리자식 노드가 왼쪽에서부터 채워져있는 형태의 트리  위 트리는 완전이진트리의 예시이다. 완전 이진트리는 배열으로 나타내기 편리하다.아래와 같이 왼쪽 위에서부터 순서대로 한층씩 내려오며 배열의 인덱스에 채워넣는다고 하자. 두 가지 방법으로 배열을 채울 수 있다. 1. 인덱스 0부터 차례로 채워넣기규칙성을 찾아보자.왼쪽 자식 인덱스 :  2*(부모 인덱스)+1오른쪽 자식 인덱스 : 2*(부모 인덱스)+2  실행 코드#include#define MAX_NODE 16void btree_array(int arr[], int idx){ // 왼쪽 자식 출력 int left_child = 2 * idx+1; if (left_child  위 코드는 인덱스가 3인 40의 왼쪽 자식과 오른쪽 자..

큐를 이용한 예제로는 전위식 계산이 있다. 전위식은 주로 많이 사용하지 않지만, 큐를 이용한 예제로 한번씩 나온다. 전위식연산자가 피연산자의 앞쪽에 위치한 식을 말한다.ex) -+x9+28x+4863  전위식을 계산하는 데 우리는 원형 배열 큐를 사용하겠다. 기본적인 원형 배열 큐의 코드들을 먼저 구현하겠다.#include#include#define MAX_SIZE 10char queue[MAX_SIZE];int front = 1, rear = 1;int isEmpty(){ if(front==rear) return 1; return 0;}int isFull(){ if(front==(rear+1)%MAX_SIZE) return 1; return 0;}void ..