코딩 공부 일기

#include "stdafx.h"

#include "DijkstraAlgorithm.h"

int main()

{

DijkstraAlgorithm dijkstra(7);    //초기화, 최대 노드수는 7

        //경로 세팅

        dijkstra.Set(0, 1, 2);    //0 -> 1 : 비용 2

        dijkstra.Set(0, 3, 5);    //0 -> 3 : 비용 5

        dijkstra.Set(1, 2, 6);

        dijkstra.Set(1, 4, 10);

        dijkstra.Set(2, 6, 3);

        dijkstra.Set(3, 4, 4);

        dijkstra.Set(3, 5, 5);

        dijkstra.Set(4, 5, 1);

        dijkstra.Set(4, 6, 7);

        dijkstra.Set(5, 6, 2);

        //최단경로 검색(0->6)

        dijkstra.FindPath(0, 6);

    return 0;

} 

#pragma once

#define INF 99999999                                               //무제한

class DijkstraAlgorithm

{

private:

        const int m_NumberOfNodes;                                 //최대 노드의 수

        int **m_Table;                                             //노드간의 거리(혹은 비용) 테이블

public:

        DijkstraAlgorithm(int NumberOfNodes);

        ~DijkstraAlgorithm();

        void Set(int From, int To, int Cost);                       //경로 세팅

        void FindPath(int From, int To);                            //경로 찾기 시작

private:

        void CalPath(int *&Path,int From);                         //경로 계산

        void PrintTable(int *cost, bool *visit, int Length);       //테이블 출력

        void PrintShortestWay(int From, int To, int *prev);        //최단 경로 출력

};

#include "stdafx.h"

#include "DijkstraAlgorithm.h"

DijkstraAlgorithm::DijkstraAlgorithm(int NumberOfNodes): m_NumberOfNodes(NumberOfNodes)

{

        //비용 테이블 초기화

        m_Table = new int*[NumberOfNodes];

        for (int i = 0; i < NumberOfNodes; i++)

        {

               m_Table[i] = new int[NumberOfNodes];

               for (int j = 0; j < NumberOfNodes; j++)

               {

                       if(i == j)

                              m_Table[i][j] = 0;

                       else

                              m_Table[i][j] = INF;

               }

        }

}

DijkstraAlgorithm::~DijkstraAlgorithm()

{

        //비용 테이블 메모리 해제

        for (int i = 0; i < m_NumberOfNodes; i++)

        {

               delete[] m_Table[i];

               m_Table[i] = NULL;

        }

        delete[] m_Table;

        m_Table = NULL;

}

//경로 세팅

void DijkstraAlgorithm::Set(int From, int To, int Cost)

{

        if (From < m_NumberOfNodes && To < m_NumberOfNodes)

        {

               m_Table[From][To] = Cost;

        }      

}

//경로 찾기 시작

void DijkstraAlgorithm::FindPath(int From, int To)

{

        //경로 저장 배열 초기화

        int *path = new int[m_NumberOfNodes];

        //경로 계산

        CalPath(path, From);

        //최단 경로 출력

        PrintShortestWay(From, To, path);

        //배열 해제

        delete[] path;

        path = NULL;

}

//경로 계산

void DijkstraAlgorithm::CalPath(int *&Path, int From)

{

        int min, index;

        int *cost = new int[m_NumberOfNodes];            //비용

        bool *visit = new bool[m_NumberOfNodes];  //방문

        //배열 초기화

        for (int i = 0; i < m_NumberOfNodes; i++)

        {

               cost[i] = INF;

               visit[i] = false;

               Path[i] = -1;

        }

        //출발위치의 비용->0으로

        cost[From] = 0;

        //총 노드의 수 만큼 반복

        for (int i = 0; i < m_NumberOfNodes; i++)

        {

               min = INF + 1;

               index = -1;

               //검색할 노드 찾기

               for (int j = 0; j < m_NumberOfNodes; j++)

               {

                       //이미 체크한 노드면 패스

                       if (visit[j])

                              continue;

                       //현재 최소값보다 더 작으면 다음 노드로

                       if (min > cost[j])

                       {

                              min = cost[j];

                              index = j;

                       }

               }

               //노드들 비용 재계산

               for (int j = 0; j < m_NumberOfNodes; j++)

               {

                       //현재 비용보다, 지금 노드에서 출발하는 비용이 더싸면 갱신

                       if (cost[j] > cost[index] + m_Table[index][j])

                       {

                              //비용 갱신

                              cost[j] = cost[index] + m_Table[index][j];

                              //경로 갱신

                              Path[j] = index;

                       }

               }

               //현재 노드는 방문한 노드로 만듬

               visit[index] = true;

               //테이블 출력(진행사항 체크용)

               PrintTable(cost, visit, m_NumberOfNodes);

        }

        delete[] cost;

        delete[] visit;

        cost = NULL;

        visit = NULL;

}

//테이블 출력

void DijkstraAlgorithm::PrintTable(int *cost, bool *visit, int Length)

{

        //번호 출력

        printf("Num\t:\t");

        for (int i = 0; i < Length; i++)

               printf("%d\t",i);

        //비용 출력

        printf("\nCost\t:\t");

        for (int i = 0; i < Length; i++)

        {

               if (cost[i] != INF)

                       printf("%d\t", cost[i]);

               else

                       printf("X\t");

        }

        //방문 여부 출력

        printf("\nVisit\t:\t");

        for (int i = 0; i < Length; i++)

               printf("%d\t", visit[i]);

        printf("\n\n");

}

//최단 경로 출력

void DijkstraAlgorithm::PrintShortestWay(int From, int To, int *prev)

{

        //출력할 경로 저장

        int *path= new int[m_NumberOfNodes];

        //저장된 경로 마지막 위치

        int lastIndex = 0;

        int final = To;         //출발 위치

        int start = From;       //도착 위치

        From = prev[To];

        //최종 도착위치 부터 역순으로 경로 추적

        while (From != start && From != -1)

        {

               path[lastIndex++] = To; 

               To = From;                            

               From = prev[From];             

        }

        //경로가 없다면

        if (From == -1)

        {

               printf("경로가 없습니다\n");

        }

        //경로가 있다면

        else

        {

               //마지막에 입력안된 노드 입력

               path[lastIndex++] = To;

               //경로 출력

               printf("최적경로 : %d -> ", start);

               for (int i = lastIndex - 1; i > 0; i--)

               {

                       printf("%d -> ", path[i]);

               }

               printf("%d\n", final);

        }

        delete[] path;

        path = NULL;

}

//환전 알고리즘

//Coins(내림차순 정렬이 되어 있어야함) : 환전 가능한 동전 배열,

//NumberOfType : 동전의 갯수, Money : 환전할 금액

void Algorithm::CoinChange(int Coins[], int NumberOfType, int Money)

{      

        int *count = new int[NumberOfType];      //환전할 각 동전의 갯수

        int type = 0;                                         //동전의 종류

        printf("환전 금액 : %d 원\n", Money);

        //환전할 각 동전 0으로 초기화

        for (int i = 0; i < NumberOfType; i++)

               count[i] = 0;

        //마지막 동전을 체크할때까지 반복

        while (type < NumberOfType)

        {

               //현재 동전이 금액보다 더 크다면 : 금액이 더 작은 동전으로 변경

               if (Coins[type] > Money)

               {

                       type++;

               }

               //현재 동전이 금액보다 작다면 : 동전 갯수를 하나 올림 & 동전의 금액만큼 돈에서 차감

               else if (Coins[type] < Money)

               {

                       Money -= Coins[type];

                       count[type]++;

               }

               //현재 돈전 = 금액 이라면 : 동전 개수 하나 올림 & 반복 종료

               else

               {

                       Money = 0;

                       count[type]++;

                       break;

               }

        }

        //각 동전 갯수 출력

        for(int i = 0; i < NumberOfType; i++)

               if(count[i] != 0)

                       printf("%d동전 %d개\n", Coins[i], count[i]);

        //환전하지 못한 금액 출력

        if(Money != 0)

               printf("환산 불가능한 금액은 %d원\n", Money);

        //동전 배열 해제

        delete count;

        count = NULL;

}

//Num : 원판 번호 Src : 출발지, mid : 경유지 Dest : 목적지

void Algorithm::TowerOfHanoi(int Num, int Src, int mid, int Dest)

{

        //원판 번호가 1이라면(제일 작은 원판)

        if (Num == 1)

        {

               //원판 이동

               printf("원판 %d : %d -> %d\n", Num, Src, Dest);

        }

        else

        {

               //자신의 위에서 원판들 이동(자신보다 작은 원판)

               //출발지점 => 경유지점

               TowerOfHanoi(Num - 1, Src, Dest, mid);

               //원판 이동

               printf("원판 %d : %d -> %d\n", Num, Src, Dest);

               //경유지로 이동 시켰던 원판들 다시 자신의 위로 이동

               //경유지점 => 도착지점

               TowerOfHanoi(Num - 1, mid, Src, Dest);

        }      

}

int Algorithm::Fibonacci(int length)

{

        if (length < 1)

               return 0;

        if (length < 3)

               return 1;

        return Fibonacci(length - 2) + Fibonacci(length - 1);

}

int Algorithm::Fibonacci(int length)

{

        int prev = 1;

        int now = 0;

        int sum = 0;

        for (int i = 0; i < length; i++)

        {

               sum = prev + now;

               prev = now;

               now = sum;

        }

        return sum;

}

int Algorithm::LeastCommonMultiple(int num01, int num02)

{

//더 큰 수를 시작 점으로

        int num = num01 > num02 ? num01 : num02;

//최소 공배수를 찾을 때까지 반복

        while(true)

        {

//제일 먼저 두 수 모두로 나눠떨어지는 수가 최소 공배수

               if ((num % num01 == 0) && (num % num02 == 0))

               {

                       return num;

               }

               //찾을때까지 1씩 더함

               num++;

        }

}

int Algorithm::LeastCommonMultiple(int num01, int num02)

{

        int Divisor;                    //최대 공약수

        int Multiple = num01 * num02;   //두 수의 곱

        //최대 공약수 구함

        while (num02)

        {

               Divisor = num01 % num02;

               num01 = num02;

               num02 = Divisor;

        }

        Divisor = num01;

        return Multiple / Divisor;

}

//최대 공약수

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

        //방법01

        int max = 1;    //공약수 저장 변수

        int length = num01 < num02 ? num01 : num02;      //작은 숫자 만큼만 반복 수행

        for (int i = 1; i <= length; i++)

        {

               //두 수 모두 나누어떨어지면 max대체

               if ((num01 % i == 0) && (num02 % i == 0))

               {

                       max = i;

               }

        }

        return max;

}

}

 //유클리드 호제법_반복문

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

        int remainder;

        while (num02)

        {

               remainder = num01 % num02;

               num01 = num02;                

               num02 = remainder;

        }

        return num01;

//힙 정렬

//*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수)

void Sort::HeapSort(int * Array, const int Length)

{

        //힙 사이즈 조절 & 초기화

        m_Heap.Resize(Length);

        //힙에 데이터 입력

        for (int i = 0; i < Length; i++)

               m_Heap.Insert(Array[i]);

        //힙에서 데이터 다시 수령하여 입력

        //오름차순 정렬을 위해 최소 힙 사용(최대 힙을 사용하고, 데이터를 역순으로 넣어도 된다)

        for (int i = 0; i < Length; i++)

               Array[i] = m_Heap.Get();

}

//병합 정렬

//*Array : 정렬할 데이터 배열, Start : 데이터 시작위치, End : 데이터 마지막 위치

void Sort::MergeSort(int * Array, int Start, int End)

{

        //분할된 그룹의 크기가 1이하면 수행안함

        if (End <= Start)

               return;

        int mid = (Start + End) / 2;      //중간 데이터의 위치

        int length = End - Start + 1;     //분할된 그룹의 크기

        int *copyArray = new int[length]; //임시 저장공간

        int first = Start;    //첫번째 그룹의 시작 지점

        int second = mid + 1; //두번째 그룹의 시작 지점

        int copy = 0;         //임시 저장공간 인덱스

        //분할

        MergeSort(Array, Start, mid);    //첫번째 그룹

        MergeSort(Array, mid + 1, End);  //두번째 그룹

        //분할한 두 그룹을 다시 병합

        while (first <= mid && second <= End)

        {

               //임시 저장공간에, 데이터가 작은 순서대로 입력

               copyArray[copy++] =

                       Array[first] < Array[second] ? //첫번째 그룹의 데이터가 두번째 그룹의 데이터 보다 작은가?

                       Array[first++] :               //작다면 첫번째 그룹의 데이터 입력

                       Array[second++];               //아니라면 두번째 그룹의 데이터 입력

        }

        //입력이 되지 않고 남아 있는 데이터 처리

        //      어떤 그룹의 데이터가 남았는지 찾고

        int i = first <= mid ? first : second;

        //      순서대로 임시저장 공간에 입력

        for (; copy < length; copy++, i++)

               copyArray[copy] = Array[i];

        //데이터 목록에 임시저장한 데이터들 입력

        for (i = Start, copy = 0; i <= End; i++, copy++)

               Array[i] = copyArray[copy];

        //입시저장공간 메모리 해제

        delete[] copyArray;

        copyArray = NULL;

}

//기수 정렬

//*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수), MaxNum : 배열에서 가장 큰 수

void Sort::RadixSort(int * Array, const int Length, int MaxNum)

{

        int *store[10];          //각 자리수를 저장하는 공간

        int rear[10];            //각 저장공간에서 가장 늦게 입력된 데이터의 위치

        int radix;               //어떤 큐에 데이터를 입/출력 할건지 지정하는 변수

        int MaxMultiples = 1;    //최대 자릿수

        //저장 공간 초기화

        for (int i = 0; i < 10; i++)

        {

               store[i] = new int[Length];

               rear[i] = -1;

        }

        //최대 자릿수 계산

        while (MaxNum > 0)

        {

               MaxNum /= 10;

               MaxMultiples *= 10;

        }

        //정렬 시작

        for (int multiples = 10; multiples <= MaxMultiples; multiples *= 10)

        {             

               //비교하고자 하는 자릿수를 구하기 위해 나눠야 하는 수

               int div = multiples / 10;

               //기수 별로 데이터 분류

               for (int i = 0; i < Length; i++)

               {

                       //기수 계산

                       radix = Array[i] % multiples;

                       radix /= div;

                       //구한 기수의 저장소에 데이터 저장

                       //데이터를 저장 할 수록 그 기수의 rear가 한칸씩 뒤로 밀린다.

                       store[radix][++rear[radix]] = Array[i];

               }

               //데이터를 기수0 -> 기수9 순으로 순차적으로 입력

               int index = 0;

               for (radix = 0; radix < 10; radix++)

               {

                       //각 기수 순서대로 데이터 입력(각 기수 안에선 입력 받은 순으로 입력)

                       for(int  i = 0; i <= rear[radix]; i++)

                       {

                              Array[index++] = store[radix][i];

                       }

                       //입력이 완료된 기수의 rear는 -1로 초기화

                       rear[radix] = -1;

               }

        }

        //저장소의 메모리 해제

        for (int i = 0; i < 10; i++)

        {

               delete[] store[i];

               store[i] = NULL;

        }

}

//재귀 함수 이용

//*Array : 정렬할 데이터 배열, LeftRange : 가장 왼쪽의 위치, RightRange : 가장 오른쪽의 위치

void Sort::QuickSort(int *Array, int LeftRange, int RightRange)

{

        int copy; //자리 변경용 저장 변수

        int left = LeftRange; //검색할 데이터의 위치 : 왼쪽부터 시작, 기준보다 큰 데이터를 찾는다

        int right = RightRange; //검색할 데이터의 위치 : 오른쪽부터 시작, 기준보다 작은 데이터를 찾는다

        int pivot = Array[(left + right) / 2]; //기준

       //left가 right보다 작거나 같으면 반복 계속

        while (left <= right)

        {

               //pivot보다 큰 데이터를 찾을때까지 반복

               while (Array[left] < pivot)

                       left++;

               //pivot보다 작은 데이터를 찾을때까지 반복

               while (Array[right] > pivot)

                       right--;

               //left가 right보다 작거나 같으면 데이터 교환

               if (left <= right)

               {

                       copy = Array[left];

                       Array[left] = Array[right];

                       Array[right] = copy;

                       left++;

                       right--;

               }      

        }

        //입력된 범위 중 가장 왼쪽 위치(LeftRange)보다 right의 위치가 더 크면 정렬 실행

        if (LeftRange < right)

               QuickSort(Array, LeftRange, right);

        //입력된 범위 중 가장 오른쪽 위치(RightRange)보다 left의 위치가 더 작으면 정렬 실행

        if (left < RightRange)

               QuickSort(Array, left, RightRange);

}