C# LINQ 집계함수(Sum,MAX,MIN,Average,count,Aggregate 등)

닷넷,C#,.NET 2018. 6. 14. 22:19


C#의 LINQ를 사용하면 데이터를 가공하고 추출하는데 편리하고 빠른 장점이 있다. 기본적으로 SQL을 사용해봤다면 직관적으로 쉽게 이해할 수 있을 것이다. 코딩을 배워보지 않은 사람도 쉽게 이해할 수 있도록 만들어진 언어가 SQL 이기 때문에 쉽게 배워 사용할 수 있다. 그리고 병렬로 처리도 가능하기 때문에 일반적으로 코드를 작성해서 데이터를 추출하는 가공방식보다 많은 이점이 있다. 


LINQ에 기본적인 질의방식에 대해서는 아래링크를 참고하자


- C# LINQ 사용 방법 및 예제(from, select, where, orderby) : http://hijuworld.tistory.com/56


우선 기본적인 합(Sum), 최대값(Max), 최소값(Min), 평균값(Average), 데이터 갯수(Count) 에 대해서 알아보자.


아래 예제는 1부터 9까지의 데이터를 가지고 있는 numbers라는 변수가 존재하는데 Linq 함수를 이용하여 집계를 하는 것을 볼 수 있다. 해당 예제는 배열을 가지고 작성했지만 List와 같은 C#에서 제공해주는 다양한 제너릭 클래스들에서 사용이 가능하다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using System;
using System.Linq;
namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Console.WriteLine("sum : " + numbers.Sum());
            Console.WriteLine("max : " + numbers.Max());
            Console.WriteLine("min : " + numbers.Min());
            Console.WriteLine("average : "+ numbers.Average());
            Console.WriteLine("count : " + numbers.Count());
        }
    }
}
cs


네임스페이스인 using System.Linq 를 반드시 명시해줘야 한다.



Aggregate는 사용자가 직접 해당 데이터들을 어떻게 가공할지 명시 할 수 있다.


인자들의 합이나 최대값을 구하는 것이 아닌 가장 큰수와 가장 작은 수의 합이라던지 모든 수의 곱셈이라던지 등에 다양한 방식에 집계를 사용자가 직접 작성할 수 있는 장점이 있다. 잘만 사용하면 응용하여 사용할 수 있는 곳이 정말 많다.

람다식을 사용하여 함수의 내용을 쉽게 넘겨줄 수 있다. 


아래 예제는 모든 인자들의 곱을 계산하는 예제이다. 첫번째 인자와 두번째 인자를 곱해서 다시 첫번재 인자에 놓고 다시 그다음 번째 인자를 두번째 인자로 놓고 곱하는것을 반복한다. 


1
2
3
4
5
6
static void Main(string[] args)
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    var data = numbers.Aggregate((num1, num2) => num1 * num2);
    Console.WriteLine(data);
}
cs

출력결과 : 120



아래 예제는 위의 예제와 동일하지만 Aggregate 함수에 파라미터를 앞에 하나 추가하였다.


첫번째 인자 하나는 고정하는 기능을 한다.


100 * 1 * 2 * 3 * 4 * 5 의 결과가 출력되게 된다. 해당 기능은 대소 비교를 할때 가장 처음에 기준값을 정할 때에도 사용이 가능하다.


1
2
3
4
5
6
static void Main(string[] args)
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    var data = numbers.Aggregate(100, (num1, num2) => num1 * num2);
    Console.WriteLine(data);
}
cs


출력결과 : 12000



아래 예제는 첫번째 글자와 두번째 글자를 콤마를 사이에두고 연결한다.


1
2
3
4
5
6
static void Main(string[] args)
{
    String[] names = { "abc", "kim", "lee", "han", "park" };
    var data = names.Aggregate((str1,str2)=>str1+", "+str2);
    Console.WriteLine(data);
}
cs

출력 결과 : abc, kim, lee, han, park



이제는 좀더 응용해서 사용해보도록 하자.


아래는 학생들의 이름과 점수를 담고있는 객체들을 List로 가지고있는 데이터에서 학생들의 평균 점수를 구하는 예제이다. 클래스를 사용하여 학생의 이름과 점수를 저장할 수 있도록 하였다. 그리고 LINQ를 사용하여 데이터를 가공하는 것을 볼 수 있다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using System;
using System.Collections.Generic;
using System.Linq;
namespace test
{
    public class Student
    {
        public string name { get; set; }
        public int score { get; set; }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<Student> students = new List<Student>
            {
                new Student { name = "zzz", score = 88 },
                new Student { name = "kim", score = 50 },
                new Student { name = "han", score = 70 },
                new Student { name = "park", score = 45 },
                new Student { name = "peter", score = 84 },
                new Student { name = "lee", score = 98 }
            };
            var result = (from student in students
                        select student).Average(student => student.score);
            Console.WriteLine("전체학생의 평균 : " + result);
        }
    }
}
 
 
cs


결과 : 전체학생의 평균 : 72.5



아래는 좀더 응용한 것으로 학생들의 이름이 4글자 이상인 학생들만 추출하고 그 학생들의 점수의 합을 구하는 예제이다. from으로 학생 하나씩 선택하여 where로 이름이 4글자인 학생만 추출하고 select함수로 학생의 정보를 받는다. 그리고 Sum 함수로 이름이 4글자인 학생에 점수들을 모두 합한다. 복잡해보이지만 하나하나 차근차근 보면 쉽게 이해가 갈 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using System;
using System.Collections.Generic;
using System.Linq;
namespace test
{
    public class Student
    {
        public string name { get; set; }
        public int score { get; set; }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<Student> students = new List<Student>
            {
                new Student { name = "zzz", score = 88 },
                new Student { name = "kim", score = 50 },
                new Student { name = "han", score = 70 },
                new Student { name = "park", score = 45 },
                new Student { name = "peter", score = 84 },
                new Student { name = "lee", score = 98 }
            };
            var result = (from student in students
                          where student.name.Length >= 4
                          select student).Sum(student => student.score);
            Console.WriteLine("이름이 4글자 이상인 학생들의 점수 합 : " + result);
        }
    }
}
 
 
cs


출력 결과 : 이름이 4글자 이상인 학생들의 점수 합 : 129


아래 예제는 group by 키워드를 사용하여 50점이상 학생과 미만 학생으로 나눈후 해당 학생들의 숫자와 평균, 최대값을 구하는 코드이다. Group by는 특정 조건으로 데이터들을 그룹을 지어주는 기능을 한다. 예를들어 1~100까지의 수가 있어서 group by를 사용하여 50이상과 미만으로 나누어 각각의 평균을 구할 수 있다. 자주 사용되기 때문에 알아두면 좋다. 그룹으로 나눈 각각의 그룹은 into 키워드를 사용하여 g로 나타낸다. 그래서 g.key 사용하여 참인지 거짓인지를 가지고 어느 그룹의 데이터인지 알 수 있다. 그래서 각 그룹의 평균과 최대값 등을 알아 낼 수 있다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using System;
using System.Collections.Generic;
using System.Linq;
namespace test
{
    public class Student
    {
        public string name { get; set; }
        public int score { get; set; }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            List<Student> students = new List<Student>
            {
                new Student { name = "zzz", score = 88 },
                new Student { name = "kim", score = 20 },
                new Student { name = "han", score = 70 },
                new Student { name = "park", score = 45 },
                new Student { name = "peter", score = 84 },
                new Student { name = "lee", score = 98 }
            };
 
            var result = from student in students
                         group student by student.score >= 50 into g //50점을 기준으로 나눔
                         select new
                         {
                             key = g.Key==true ?"50점이상":"50점미만", //50점이상데이터인지
                             count = g.Count(), //해당 구간의 학생수
                             avr = g.Average(student => student.score), //해당 구간의 평균점수
                             max = g.Max(student => student.score) // 해당 구간에 최대값
                         };
            
            foreach (var data in result)
            {
                Console.WriteLine(data.key + " 학생 수 : " + data.count);
                Console.WriteLine(data.key + " 중 최대점수 : " + data.max);
                Console.WriteLine(data.key + " 학생들의 평균 : " + data.avr);
                Console.WriteLine("------------------------------------");
 
            }
        }
    }
}
cs

출력결과는 아래와 같다. 50이상의 학생과 미만의 학생의 최대값과 학생수 평균등을 출력한다.


저작자표시 비영리

'닷넷,C#,.NET' 카테고리의 다른 글

C# 파일 및 디렉터리 생성, 삭제, 복사, 존재여부 검사 등  (0) 2018.07.03
C# Parallel LINQ(PLINQ) 병렬 처리 LINQ 설명 및 시간 측정  (1) 2018.06.22
C# LINQ 사용 방법 및 예제 from, select, where, order by  (0) 2018.06.13
C# LOH(Large Object Heap)의 가지비 컬렉션 방식  (0) 2018.05.15
C#/.NET 확장 메서드 기능, String에 메서드 추가 하기  (0) 2018.05.14
Posted by 꿈만은공돌
,

C# LINQ 사용 방법 및 예제 from, select, where, order by

닷넷,C#,.NET 2018. 6. 13. 12:07


LINQ란 Language Integrated Query 라고해서 특정 데이터들에서 Query를 하여 데이터를 빠르고 편리하게 추출하는 방식이라 할 수 있다. 해당기능은 C# 3.0부터 추가가 되기 시작한 문법이다. 기본적으로 람다표현식을 사용하여 간결하고 가독성 좋게 작성 가능하다. Query를 하는데에는 SQL을 사용한다. SQL 이란 Structured Query Language의 약자이다. 


SQL에서 가장 많이 사용하는 문법은 다음 4가지 이다.


from : 어떤 데이터에서 찾을 것인가


where : 어떤 조건으로 찾을 것인가


order by : 어떤 항목을 기준으로 정렬할 것인가


select : 어떤 항목을 추출할 것인가


LINQ는 이러한 SQL의 문법을 가지고 다양한 쿼리를 통해 데이터를 가공하고 집계하는 등에 사용된다. 전통적인 방싱그로 for문과 if문을 가지고 특정 데이터들을 가공하고 집계내는 것도 가능하다. 하지만 LINQ를 이용하면 빠르고 정확하게 데이터를 찾는 것이 가능하다. 그리고 더욱 중요한 가독성이 좋다. 문장을 서술 하듯 질의를 하기 때문에 for와 if문을 사용하는 방식보다 가독성이 좋아 실수를 줄이고 유지보수가 쉽다.

또한 병렬로 처리도 가능하기 때문에 일반적으로 코드를 작성해서 데이터를 추출하는 가공방식보다 속도가 빠를 수 있다.


LINQ는 기본적으로 아래에서 소개한 예제만 보면 어느정도 이해가 갈 것이다. 더욱 복잡한 예제들도 많이 존재 하고 사용방법도 복잡한 것들도 많지만 우선 아래 예제들을 보고 LINQ가 무엇인지 이해하자.


아래 예제는 1부터 9까지의 수중에 3의 배수를 찾는 예제이다. from 문으로 nums에 저장된 1부터 9까지의 숫자중 하나씩 추출하며 where 로 3의 배수인지를 검사한다. 검사결과가 참인 데이터인 num을 select 문으로 추출한다. 그 결과를 변수 numQuery에 저장한다. foreach문으로 결과를 출력한다. LINQ를 사용한 데이터 가공에 가장 기본적인 형태의 예제이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using System;
using System.Linq;
namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[9] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            var numQuery = from num in nums
                           where (num%3) == 0
                           select num;
            foreach(int num in numQuery) //결과 출력            
                Console.Write(num +" ");            
        }
    }
}
cs

출력결과 : 3 6 9



아래 예제는 길이가 3글자인 문자열을 찾는 것이다. where에서 string.length ==3 으로 문자길이가 3인 것을 찾는다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using System;
using System.Linq;
namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            String[] names = new String[]{ "abc", "kim","peter", "Tistory", "Z"};
            var nameQuery = from name in names
                                  where name.Length == 3
                                   select name;
            foreach(string name in nameQuery) // 결과 출력
                Console.WriteLine(name);
        }
    }
}
 
cs

출력 결과

abc 

kim



아래 예제는 60점이상 학생만 이름순으로 출력하는 것이다. student 클래스를 선언하여 이름과 점수를 저장하도록 한다. List객체를 만들어서 학생들의 정보를 저장한다. 그래서 해당 객체에 점수가 60점이상인 학생들을 where 문으로 검사하여 추출하고 orderby를 사용하여 이름순으로 정렬 시킨다. 그리고 select 에서 학생의 이름만을 추출한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using System;
using System.Collections.Generic;
using System.Linq;
namespace test
{
    public class Student
    {
        public string name { get; set; }
        public int score { get; set; }
    } 
 
    class Program
    {
        static void Main(string[] args)
        {
            List<Student> students = new List<Student>
            {
                new Student { name = "zzz", score = 88},
                new Student { name = "kim", score = 50},
                new Student { name = "han", score = 76 },
                new Student { name = "park", score = 45 },
                new Student { name = "peter", score = 84 },
                new Student { name = "lee", score = 98 }
            };
            var smart = from student in students
                        where student.score >= 60 // 60점이상만
                        orderby student.name ascending//이름순으로 정렬
                        select student.name; //이름만 추출
 
            foreach(string studentName in smart)     //결과 출력        
                Console.WriteLine(studentName);
        }
    }
}
cs

출력 결과

han

lee

peter

zzz


orderby는 orderby 정렬기준 ascending 이런식으로 사용을 한다.

기본으로 오름차순(ascending)이며 내림차순으로 하고 싶다면 descending 을 써주면 된다. 디폴트는 오름차순인 ascending이기 때문에 반드시 명시할 필요는 없다.


이외에도 LINQ를 이용하면 합(Sum), 최대값(Max), 최소값(Min), 평균값(Average), 데이터 갯수(Count)들을 쉽게 계산할 수 있다. 아래 링크를 참고하도록 하자.

C# LINQ 집계함수(Sum,MAX,MIN,Average,count,Aggregate 등) : http://hijuworld.tistory.com/57

저작자표시 비영리

'닷넷,C#,.NET' 카테고리의 다른 글

C# Parallel LINQ(PLINQ) 병렬 처리 LINQ 설명 및 시간 측정  (1) 2018.06.22
C# LINQ 집계함수(Sum,MAX,MIN,Average,count,Aggregate 등)  (0) 2018.06.14
C# LOH(Large Object Heap)의 가지비 컬렉션 방식  (0) 2018.05.15
C#/.NET 확장 메서드 기능, String에 메서드 추가 하기  (0) 2018.05.14
C# 상속금지 키워드 sealed 키워드  (0) 2018.05.13
Posted by 꿈만은공돌
,

C++ 이중 연결 리스트(double linked list) 설명 및 예제

알고리즘 2018. 6. 7. 22:58


일반적인 링크드 리스트는 Node가 다른 Node를 하나만 가리키고 있지만 이중 연결리스트는 앞 뒤로 하나씩 연결을 가지고 있습니다. 

그래서 탐색을 할때 해당 노드에서 앞에 노드나 뒤에 노드로 쉽게 왔다갔다 할 수 있는 장점이 있습니다. 특정 노드를 탐색하다가 뒤로 마음대로 갈 수 있다는 의미이다. 프로그램을 작성하기전에 이러한 상황이 꼭 필요하고 자주 발생할 것 같다면 이중 연결 리스트를 고려해 보아야 합니다. 

  

아래 Node를 보면 next와 prev 라는 2개의 Node 포인터를 볼 수 있습니다. 하나는 자신의 앞에 있는 노드(next)를 가르키며 다른하나는 자신의 뒤에 있는 노드(prev)를 가르키는 역할을 합니다.

생성자를 통해 기본적으로 포인터에 NULL을 대입 합니다. 그리고 파라미터를 받는 생성자는 파마리터로 받은 ptr을 가지고 해당 노드 다음에 자신을 놓도록 합니다. 포인터를 사용하기 때문에 복잡해 보일 수 있다. 종이에 하나하나 그려가며 코드를 보면 이해가 쉽게 갈 것입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Node { 
    int data;
    Node* next, * prev; 
    Node() {
        next = prev = NULL;
        data = 0;
    }
    Node(int i, Node* ptr)//ptr 뒤에 추가
    {
        data = i;
        prev = ptr;
        next = ptr->next;
        next->prev = prev->next = this; 
    }  
};
cs

 


그리고 이중 연결리스트의 또 다른 장점으로는 노드 자신을 삭제하는게 쉽습니다. 그 이유는 자신의 앞에노드와 뒤에 노드의 정보를 가지고 있기 때문에 포인터를 가지고 자신을 제외한 앞뒤 포인터를 서로 연결 시켜줄 수 있어서 입니다.

아래 예시는 자기 자신의 노드를 삭제하는 함수 입니다. 함수의 첫번째 줄은 자신의 뒤에 노드에 다음을 가르키는 포인터에 자기 자신의 다음 노드의 주소값을 넘겨줍니다. 그러면 뒤에 노드가 자신의 다음 노드를 가르키게 하는 것입니다. 두번째 줄에는 자신의 다음노드의 이전을 가르키고 있는 포인터에 자신이 가르키고 있는 뒷노드의 주소값을 넘겨주는 것입니다. 그리고 마지막으로 delete로 자기자신을 삭제해서 할당받은 메모리를 해제합니다. 간결한 코드이지만 처음이해하는데는 많은 어려움이 있을 수 있습니다.


1
2
3
4
5
void selvDelete() {
     prev->next = next;
     next->prev = prev;
     delete this;
}
cs


일반적으로 간단하게 데이터를 추가하고 탐색하는 경우에는 일반 연결 리스트를 구현하면 됩니다.

연결리스트를 활용하여 구현한 Stack 예제 : http://hijuworld.tistory.com/54


하지만 데이터를 탐색할 때 뒤로 갔다 앞으로 갔다하는 경우가 많고 데이터 삭제가 빈번한 경우라면 이중 연결 리스트로 구현하는 것이 좋습니다.


아래 예제는 이중연결리스트를 구현한 예제입니다.


C++을 기본으로 작성하였으며 데이터를 삽입이나 삭제 할때 가장 앞이나 가장 뒤에서 모두 가능하게 하였습니다.

필요한 기능의 함수가 있다면 DLinkedList 구조체에 추가하여 구현하면 됩니다. 

해당 예제를 가지고 데이터를 앞뒤로 삽입하고 삭제하기 때문에 왠만한 기능을 다 할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
 
 
struct Node {
    int data;
    Node* next, * prev;
    Node() {
        next = prev = NULL;
        data = 0;
    }
    Node(int i, Node* ptr)//ptr 뒤에 추가한다.
    {
        data = i;
        prev = ptr;
        next = ptr->next;
        next->prev = prev->next = this; 
    }    
    void selvDelete() {
        prev->next = next;
        next->prev = prev;
        delete this;
    }
};
 
struct DLinkedList {
    Node *head;
    Node *tail;
    int count;
    DLinkedList() { //생성자
        count = 0;
        head = new Node(); //더미를 선언해서 가지고 있게한다.
        tail = new Node(); //더미를 선언해서 가지고 있게한다.
        head->next = tail; //서로연결한다.
        tail->prev = head;
    }
    ~DLinkedList() {
        while (head->next != tail)
            head->next->selvDelete();
        delete head;
        delete tail;
    }
    void firstInsert(int i) { //head 다음에 추가한다.
        new Node(i, head);
    }
    void endInsert(int i) { //tail 앞에 추가한다.
        new Node(i, tail->prev);
    }
    void firstDelete() { //head 다음 노드 삭제한다.
        if (head->next == tail)    return;
        head->next->selvDelete();
    }
    void endDelete() { //tail 앞에 제거한다.
        if (tail->prev == head) return;
        tail->prev->selvDelete();
    }
    void printAll() {
        Node* tmp = head;
        while (tmp->next != tail) {
            printf("%d\n", tmp->next->data);
            tmp = tmp->next;
        }
    }
};
 
int main() {
    DLinkedList *list = new DLinkedList();
    list->firstInsert(1); //1을 삽입한다.(가장앞)
    list->firstInsert(3); //3을 삽입한다.(1앞에)
    list->firstInsert(5); //5을 삽입한다.(3앞에)
    list->firstDelete(); //5를 삭제한다
    list->endInsert(100); //100을 삽입한다.(가장뒤에)
    list->endInsert(200); //200을 삽입한다.(100뒤에)
    list->endInsert(300); //300을 삽입한다.(200뒤에)
    list->endDelete(); //300을 삭제한다.
    list->printAll();
    delete list;
}
cs

 이중 연결리스트를 여러번 직접 종이에 그려가며 작성해 보아야 손에 익어서 언제든 작성 할 수 있습니다. 처음부터 코드를 완벽하게 작성하고 실행을 해야합니다. 대충 작성하고 디버깅을 해야지 하고 생각한다면 쉽게 에러를 찾을 수 없습니다. 포인터를 가지고 계속 왔다갔다 하기 때문에 디버깅에 많은 어려움이 있습니다. 연결 리스트 뿐만 아니라 데이터를 포인터로 연결하는 트리나 링큐 등도 디버깅하는데 많은 어려움이 있습니다. 처음부터 주의깊게 프로그래밍하는 것이 좋습니다. 


저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 2진 탐색(Binary Search) 예제 코드  (0) 2018.05.24
C/C++ 병합정렬(Merge Sort) 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
Posted by 꿈만은공돌
,

C++ 스택(Stack), 연결 리스트(LinkedList) 코드

알고리즘 2018. 6. 7. 21:23

C++을 이용하여 LinkedList를 사용하여 Stack을 구현해보도록 하겠습니다.


 스택(Stack)을 설명하자면 다음과 같습니다. 가장 처음 데이터를 1을 넣으면 [1]이 됩니다. 거기에 2를 넣으면 [2, 1] 이 됩니다. 2->1을 가르키고 있는 것이죠. 그리고 4를 넣으면 [4,2,1]이 됩니다. 4->2->1 입니다. 여기에 10을 넣으면 [10, 4, 2, 1] 데이터가 됩니다. 이제 데이터를 꺼내면 10부터 나오게 됩니다. 마지막 넣은 데이터가 가장 처음 나오게 됩니다. 

 Last In First out 으로 줄여서  LIFO 라고 합니다. 

 10을 꺼내게 되면 [4, 2, 1]이 됩니다. 다시 데이터를 꺼내면 4가 나오게 됩니다. [2,1]이 됩니다. 그리고 하나더 꺼내면 2가 나오고 마지막으로 1이 나오게 됩니다.

 비유를 하자면 바닥에 이불을 하나씩 쌓는것을 생각하면 됩니다. 빨간이불을 먼저 쌓고 그다음에 검정이불을 쌓고 마지막으로 하얀이불을 쌓으면 다음에 꺼낼 때 하얀이불이 가장위에 있기때문에 하얀이불부터 꺼낼 수 있습니다.


Stack은이렇듯  LIFO 으로 마지막에 들어온 데이터가 가장 처음에 나오는 방식 입니다.


 연결리스트를 구현할때 Node들을 만들어서 서로 연결해야 합니다. Node는 기본적으로 데이터를 보관할 변수하나와 다른 노드를 가르킬 포인터 변수를 가집니다. 아래 예제에서는 data변수가 데이터를 저장할 변수가 됩니다. 그리고 next가 다른 노드를 가르킬 포인터가 됩니다. 

 그리고 추가로 생성자를 추가시켰습니다. 구조체에도 c++에서는 생성자나 함수등을 포함시킬 수 있습니다. class와의 차이는 모든 변수와 함수가 기본적으로 public입니다. 첫번째 생성자는 기본생성자로 초기화만 시킵니다. 다음생성자는 데이터와 다음 노드를 받습니다. 파라미터로 들어온 ptr 다음 노드로 자신을 가리키게 합니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Node {
    int data;
    Node* next;
    Node() {
        next = NULL;
        data = 0;
    }
 
    Node(int i, Node* ptr) //ptr 뒤에 추가
    {
        data = i;
        next = ptr->next;
        ptr->next = this; 
    }    
};
cs


연결 리스트(LinkedList)를 가지고 구현한 스택(stack) 코드입니다. 기본적으로 .cpp로 C++ 컴파일을 해야한다.

Stack에 생성자를 보면 new Node로 더미노드를 만들어서 head에 넣는 것을 볼 수 있습니다. 이는 pop과 push등을 할때 더미노드가 있어야 코드가 더 간결해집니다.

소멸자도 반드기 구현해줘야 합니다. 그래야 사용하지 않는 메모리를 heap에서 계속 점유하고 있기 때문에 프로그램이 계속 돌다가 메모리가 부족한 현상이 발생 할 수도 있습니다.

push 함수는 head 다음에 새로운 노드를 추가시킵니다. pop은 head 다음 노드를 꺼내는 역할을 합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
 
struct Node {
    int data;
    Node* next;
    Node() {
        next = NULL;
        data = 0;
    }
 
    Node(int i, Node* ptr) //ptr 뒤에 추가
    {
        data = i;
        next = ptr->next;
        ptr->next = this; 
    }    
};
 
struct Stack {
    Node *head;
    int count;
    Stack() { //생성자
        head = new Node(); //더미노드
        count = 0;
    }
 
    ~Stack() { //소멸자
        while (count!=0) {
            pop();
        }
        delete head;
    }
 
    void pop() { //데이터 제거
        Node *tmp = head;
        head = head->next; 
        delete tmp; 
        count--;
    }
 
    void push(int i) { //데이터 삽입
        new Node(i, head);
        count++;
    }
 
    void printAll() { //모두 출력
        Node *cur = head;
        while (cur->next) {
            cur = cur->next;
            printf("%d\n", cur->data);
        }
    }
};
 
int main() {
    Stack *stack = new Stack();
    stack->push(1);
    stack->push(3);
    stack->push(5);
    stack->push(7);
    stack->printAll();
    delete stack;
}
cs

이제까지 단일 연결리스트에 대해서 알아 보았습니다. 

단일 연결리스트 vs 이중 연결 리스트


단일 연결 리스트는 Node가 다른 Node를 하나만 가리키고 있지만 이중 연결리스트는 앞 뒤로 하나씩 연결을 가지고 있습니다. 


그런데 이중연결리스트는 탐색을 할때 해당 노드에서 앞에 노드나 뒤에 노드로 쉽게 왔다갔다 할 수 있는 장점이 있습니다. 특정 노드를 탐색하다가 뒤로 마음대로 갈 수 있다는 의미이다. 프로그램을 작성하기전에 이러한 상황이 꼭 필요하고 자주 발생할 것 같다면 이중 연결 리스트를 고려해 보아야 합니다. 


이중 연결리스트 : http://hijuworld.tistory.com/55




저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 이중 연결 리스트(double linked list) 설명 및 예제  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 2진 탐색(Binary Search) 예제 코드  (0) 2018.05.24
C/C++ 병합정렬(Merge Sort) 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
Posted by 꿈만은공돌
,

C언어/C++ 콘솔 화면 초기화 방법, 예시

C, C++ 2018. 6. 4. 21:26

 본포스팅은 C언어와 C++에서 콘솔화면 초기화 하는 예제를 소개하고 설명합니다. 콘솔 화면에 써진 것들을 모두 지우는 기능을 합니다. 


 콘솔화면을 지워야 하는 경우  windows.h 에 있는 system 함수를 사용하면 됩니다. system("cls")로 호출하면 콘솔화면이 지워지게 됩니다.


 int system(const char *cmd); 해당 함수에 원형입니다. cmd에 적은 명령을 수행하도록 하는 함수 입니다. 윈도우 키를 입력하고 cmd를 입력하여 콘솔창을 실행해서 cls를 입력하면 화면이 지워지는 것을 볼 수 있습니다. 따라서 해동함 수는 윈도우 콘솔에서 제공하는 명령들을 실행합니다.


 C언어와 C++ 모두에서 사용 가능하다. 콘솔에 코드를 작성하다보면 요긴하게 사용 할일이 많이 있다. 예를들어 해당 기능으로 간단한 게임등을 구현 가능합니다. 화면을 계속 지우고 그리면서 애니메이션 처럼 캐릭터가 움직이거나 특정 모양의 객체가 움직이는 것등을 포현할 수 있습니다. 물론 콘솔이라는 환경적 제약 때문에 조잡해 보일순 있지만 공부한 프로그래밍 언어를 가지고 간단한 게임을 구현하면서 더욱 흥미를 높일 수 있습니다. 예를들어 테트리스나 벽돌깨기등의 게임을 제작해보는 것도 방법입니다.


 간단한 사용예제입니다. 처음에 화면에 지우기 1초전 이라는 구문을 출력하고 1초간 딜레이를 줍니다. 그리고 System("cls")로 콘솔화면을 초기화 합니다. 그러면 이전에 출력했던 지우기 1초전 이라는 문자가 지워지는 것을 볼 수 있습니다. 그리고 다시 1초간 프로그램이 정지 했다가 화면에 지우기 완료 라는 문자가 출력되는 것을 볼 수 있습니다. 해당 예제에 사용된 sleep함수는 ms 단위로 프로그램을 일시 정지 시키는 기능을 합니다. 예를들어 1000을 적으면 1초가 되고 60,000은 1분을 의미합니다. 알아두면 유용하게 사용 가능합니다.


1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <windows.h>
 
int main() 
{    
    printf("지우기 1초전\n");
    Sleep(1000); //1초 딜레이
    system("cls"); //콘솔화면 지우기
    Sleep(1000);
    printf("지우기 완료\n");
}
cs




두번째 예제 입니다. 

 while을 사용하여 무한반복하면서 사용자로부터 값을 입력받습니다. scanf로 값을 입력받아서 입력받은 데이터가 1이면 초기화를 시키고 2이면 프로그램을 종료시킵니다. if문으로 입력받은 값이 1인지 2인지를 검사합니다. 1이면 system("cls") 함수 호출로 화면을 초기화 시킵니다. 2이면 break 문을 사용하여 while문을 나가게 합니다. 그래서 해당 프로그램이 종료하게 됩니다. 간단하지만 응용하면 다양한 프로그램을 작성할 수 있습니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <windows.h>
 
void main()
{
    int a;
    while(1) {
        printf("숫자입력(1:초기화, 2: 종료) : ");
        scanf("%d", &a);
        if(a==1) {
            system("cls");
        } else if(a==2) {
            break;
        }
    }    
}
 
cs

 콘솔을 지우는 것 이외에도 다양한 system 함수에 기능이 존재합니다. 예를들어 System함수안에 "calc"를 입력하면 계산기가 실행되는 것을 볼 수 있다. notepad 를 입력하면 메모장이 실행됩니다. 해당 명령어들은 하나의 프로그램이며 해당 프로그램들은 windows 폴더안에 있습니다. 알아두면 유용한 것 들이 많으니 나중에 정리해서 포스팅하도록 하겠습니다.


저작자표시 비영리

'C, C++' 카테고리의 다른 글

C/C++ 동적 메모리할당 malloc, calloc, realloc 함수 비교 및 예제  (0) 2018.06.18
C/C++ malloc, free를 사용한 메모리 할당 및 해제(1차원, 2차원 배열)  (0) 2018.06.17
C언어/C++ 딜레이 함수 Sleep(), 설명, 사용예시  (0) 2018.06.04
C,C++ 콘솔화면에 원하는 좌표로 커서 이동하기  (0) 2018.06.02
C, C++ 에서 동적 메모리의 할당(malloc, new)과 해제(free,delete) 원리  (0) 2018.04.30
Posted by 꿈만은공돌
,

C언어/C++ 딜레이 함수 Sleep(), 설명, 사용예시

C, C++ 2018. 6. 4. 21:20

c언어/ C++ 에서 딜레이 함수 사용하기


프로그램을 진행하다보면 프로그램을 멈추어야할 떄가 존재합니다.


api를 사용하지 않고 아래와 같이 for문을 중첩사용하여 시간을 끄는 방식이 존재합니다.


int a=0;

for(int i=0; i < 10000; i++){ //1중첩 for문

for(int j=0; j < 10000; j++){ //2중첩 for문

a++; //무의미한 연산

}

}


하지만 위와 같은 방식은 원하는 시간만큼 정확하게 딜레이 시키기가 불가능 합니다.


그래서 C와 C++에서는 Sleep 함수를 사용합니다.


windows에 api 를이용하는 방식입니다.


#include <windows.h> 로 헤더파일을 추가해야합니다.


그리고 Sleep( ) 함수를 사용 합니다.


파라미터로 int 데이터를 사용하는데 ms단위입니다.


예를들어 Sleep(1000); 는 1000ms로 1초를 의미합니다.


프로그램을 사용하다보면 유용하게 쓸일이 많이 있습니다.


아래 예제를 참고바랍니다.



- 사용예제1 -


1
2
3
4
5
6
7
8
#include <stdio.h>
#include <windows.h>
 
int main() {    
    printf("시작\n");
    Sleep(1000); //1초정지
    printf("끝\n");
}
cs



- 사용예제2 -


1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <windows.h>
void main()
{
     int i=0;
     for(i=0; i<100; i++){
        printf("%d\n",i);
        Sleep(200);   //200ms 일시정지
     }
}
 
cs


- 사용예제3 -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <windows.h>
 
void main() {    
    printf("1초 정지\n");
    Sleep(1000);
    printf("2초 정지\n");
    Sleep(2000);
    printf("3초 정지\n");
    Sleep(3000);
    printf("4초 정지\n");
    Sleep(4000);
    printf("5초 정지\n");
    Sleep(5000);
    printf("끝\n");
}
cs


저작자표시 비영리

'C, C++' 카테고리의 다른 글

C/C++ malloc, free를 사용한 메모리 할당 및 해제(1차원, 2차원 배열)  (0) 2018.06.17
C언어/C++ 콘솔 화면 초기화 방법, 예시  (0) 2018.06.04
C,C++ 콘솔화면에 원하는 좌표로 커서 이동하기  (0) 2018.06.02
C, C++ 에서 동적 메모리의 할당(malloc, new)과 해제(free,delete) 원리  (0) 2018.04.30
포인터 배열 VS 배열 포인터 차이 및 예제  (0) 2018.04.30
Posted by 꿈만은공돌
,

C,C++ 콘솔화면에 원하는 좌표로 커서 이동하기

C, C++ 2018. 6. 2. 22:25


C, C++에서 콘솔화면에 커서를 원하는 위치로 이동하여 해당위치에 문자를 출력하는 방법이 존재한다.


아래 gotoxy함수를 참고하자.

windows.h 헤더에 포함되어 있는 api 를 이용하면 된다.

그러면 원하는 위치로 커서를 이동시킬 수 있다.

아래 gotoxy 함수를 소스에 추가해서 사용하면 편리하다.


1
2
3
4
5
6
7
8
9
#include <windows.h>
 
void gotoxy(int x, int y)
{
      COORD Cur;
      Cur.X = x;
      Cur.Y = y;
      SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),Cur);
}

cs




아래는 해당 함수를 가지고 키보드의 방향키를 입력 받아 해당 방향키대로 A 문자를 콘솔 화면에서 이동시키는 코드이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <conio.h>
#include <windows.h>
 
#define UP 0x48
#define LEFT 0x4B
#define RIGHT 0x4D
#define DOWN 0x50
#define SPACE 0x20
 
class CCharacter {
    int m_x, m_y;
    char m_ch;
    int m_key;
public:
    CCharacter(char ch) : m_x(0), m_y(0) //생성자(x,y좌표값을 모두 0으로 초기화 시킨다.)
    {
        m_ch = ch;
    }
    void gotoxy() {//커서이동함수
        COORD Cur;
        Cur.X = m_x;
        Cur.Y = m_y;
        SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Cur);
    }
    bool KeyProcess() {
        if (kbhit()) // 키입력을 체크
        {
            m_key = getch();
            switch (m_key) {
            case UP: m_y--; break;
            case DOWN: m_y++; break;
            case LEFT: m_x--; break;
            case RIGHT: m_x++; break;
            case SPACE: break;
            }
            return true;
        }
        return false;
    }
    void Draw() {
        system("cls"); // 화면을 지운다.
        gotoxy();//커서를 이동시킨다.
        printf("%c", m_ch); //문자출력
        
    }
};
void main() {
    CCharacter ch('A');
    while (1) {
        boolean b = ch.KeyProcess();
        if(b) 
            ch.Draw();
    }
}
cs


아래 화면처럼 A 문자를 키보드 방향키로 마음대로 움직이게 할 수 있다.



방향키를 입력받을때마다 화면을 지우고 커서가 있는 좌표에 문자를 출력하는 방식이다.

화면을 초기화하는 것은 아래 링크를 참고하자.


C언어/C++ 콘솔 화면 초기화 방법, 예시 : http://hijuworld.tistory.com/53



저작자표시 비영리

'C, C++' 카테고리의 다른 글

C언어/C++ 콘솔 화면 초기화 방법, 예시  (0) 2018.06.04
C언어/C++ 딜레이 함수 Sleep(), 설명, 사용예시  (0) 2018.06.04
C, C++ 에서 동적 메모리의 할당(malloc, new)과 해제(free,delete) 원리  (0) 2018.04.30
포인터 배열 VS 배열 포인터 차이 및 예제  (0) 2018.04.30
[c/c++] memset()을 이용한 배열에 값을 모두 0또는 -1로 초기화  (0) 2018.04.08
Posted by 꿈만은공돌
,

구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)

알고리즘 2018. 6. 2. 22:16


알고리즘 문제를 풀다보면 특정 구간에 합이나 최대값, 최소값 등 정보를 얻어야 할 때가 있다.


데이터의 숫자가 얼마 안되면 배열에 값을 넣어두고 특정 구간을 차례로 탐색하며 값을 연산하여 구하면된다.


아래 예를 보자.8개의 숫자 중 특정 구간의 합을 구하는 문제이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
 
int data[8] = { 1,22,4,8,11,23,6,14 }; //데이터
 
int segSum(int start, int end) { //start부터 end까지의 합
    int sum = 0;
    for (int i = start-1; i < end; i++) {
        sum += data[i];        
    }
    return sum;
}
 
int main() {
    //부분합 구하기
    printf("%d\n", segSum(1, 8));
    printf("%d\n", segSum(8, 8));
    printf("%d\n", segSum(1, 3));
    printf("%d\n", segSum(3, 5));
}
 
cs


데이터의 갯수가  적고 조회하는 횟수도 적다면 위와같은 코드는 문제가 될 것 이 없다.

하지만 데이터의 갯수가 100,000 개이고 부분합읠 조회하는 횟수가 100,000 이라고 하면 최악의 경우 

for문의 반복 횟수가 100,000 * 100,000 이란 어마어마한 숫자가 된다. 


그래서 이를 해결하기 위해 세그먼트 트리(Segment Tree)라는 바이너리 트리를 이용한다.


leaf 노드(가장 끝단에 있는 노드들)에 데이터를 저장하고 부모노드는 자식노드의 합 또는 최대값, 최소값 등을 저장한다.



위의 데이터를 세그먼트 트리로 만들면 아래와 같다.

각 노드에는 leaf노드들의 시작과 끝 번호를 가지고 있어서 해당 구간의 데이터를 요청하면 lead노드까지 탐색해보지 않고 값을 반환 하기 때문에 탐색시간이 빨라진다.


아래 코드는 위의 배열을 탐색하는 코드를 세그먼트 트리를 이용하여 구현한 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<stdio.h>
 
int data[8] = { 1,22,4,8,11,23,6,14};
int index = 0;
 
struct SegTree {
    SegTree *left;    //왼쪽 노드
    SegTree *right; //오른쪽 노드
    int s, e, m;    //시작, 끝, 중간
    int sum;        //자식들의 합
    SegTree() {        //빈생성자
        s = e = m = sum = 0;
        left = right = NULL;
    }
    SegTree(int start, int end) { //생성자
        s = start;
        e = end;
        m = (s + e) / 2; //중간값 계산
        if (start == end) { //leaf노드
            sum = data[index++]; //데이터 저장
            return; //leaf노드라 더이상 쪼갤필요없어서 종료
        }
        //쪽개기
        left = new SegTree(s, m); //왼쪽 노드
        right = new SegTree(m + 1, e); //오른쪽 노드
        sum = left->sum + right->sum; //자식들의 합
    }
    int serch(int start, int end) {        //start부터 end까지의 합 계산
        if (start > e || s > end)    return 0;    //범위 초과
        if (start <= s && e <= end) return sum; //범위 안에 있음
        return right->serch(start, end) + left->serch(start, end);
    }    
};
 
int main() {
    SegTree *tree = new SegTree(1, 8); //세그먼트 트리 생성
    printf("%d\n", tree->serch(8, 8));
    printf("%d\n", tree->serch(1, 3));
    printf("%d\n", tree->serch(1, 8));
    printf("%d\n", tree->serch(3, 5));
}
 
cs


3에서 5의 합을 구하는 것을 아래 그림을 참고하도록 하자.

구하려는 3~5의 구간을 가지고 노드가 가지고 있는 s와 e 값을 가지고 비교하며 값을 구한다.



저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 이중 연결 리스트(double linked list) 설명 및 예제  (0) 2018.06.07
C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
C/C++ 2진 탐색(Binary Search) 예제 코드  (0) 2018.05.24
C/C++ 병합정렬(Merge Sort) 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
Posted by 꿈만은공돌
,

C/C++ 2진 탐색(Binary Search) 예제 코드

알고리즘 2018. 5. 24. 22:04

이진탐색(2진탐색)은 정렬된 데이터에서 원하는 데이터를 빠르게 찾는 방식이다.


예를들어 1부터 100까지 숫자가 있다면 75를 찾아 보자.


일반적인 방식은 1부터 하나하나 데이터를 비교해가며 찾아야 한다.


O(N)에 복잡도를 가진다.


하지만 2진탐색을 사용하면 가장 중간데이터인 50부터 찾아서 비교해보고 50보다 찾아야 할 데이터인 75보다 작다.


그래서 50보다 큰수이기 때문에 50과 가장끝 데이터인 100중 가장 중간 데이터인 75를 비교해본다.


이렇게 중간데이터를 가지고 대소비교를 해가면서 데이터를 찾으면 


O(logN) 의 복잡도를 가진다.


훨씬 빠른 데이터 탐색을 할 수 있다.


코드 구현역시 간단한 편이다.




아래는 이진탐색 예제 코드이다.


아래와 같이 반복문을 가지고 시작과 끝부분의 데이터를 바꿔가며 찾는 방식이 있으며 재귀함수로도 구현이 가능 하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
 
//size 크기의 data배열안에서 d를 찾기
//값이없으면 -1반환
//값이 있으면 data배열의 index 반환
int binarySearch(int data[], int size, int d)
{
    int s = 0; //시작
    int e = size - 1; //끝
    int m;
    while (s <= e) {
        m = (s + e) / 2;
        if (data[m] == d) return m;
        else if (data[m] > d) e = m - 1;
        else s = m + 1;
    }
    return -1;
}
 
int main() {
    int data[] = { 1,3,6,8,11,23,111,114,213 };
    int dataSize = sizeof(data) / sizeof(int);
    int ans = binarySearch(data, dataSize, 114);
    printf("%d\n", ans);
}
 
cs

저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 병합정렬(Merge Sort) 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
1부터 n까지 합계 함수(for와 재귀)  (0) 2018.03.30
Posted by 꿈만은공돌
,

C/C++ 병합정렬(Merge Sort) 코드

알고리즘 2018. 5. 24. 21:44


병합정렬 위키 링크 


병합정렬은 O(NlogN) 에 시간복잡도를 가진다.

1,000 개의 데이터를 정렬 한다면 1,000 X log1,000 = 1,000 X 10 = 10,000 이다.

만약 1,000,000개의 데이터를 정렬 한다면 1,000,000 X log1,000,000 = 1,000,000 X 20 = 20,000,000 이다.

2천만으로 1ms정도 안에 처리가 가능한 수준이다.


버블 정렬이나 선택정렬 등은 O(N^2) 의 시간 복잡도를 가진다. 

1,000개의 데이터를 정렬 한다면 1,000 X 1,000 = 1,000,000 이 된다.

1,000,000개의 데이터를 정렬 한다면 1,000,000 X 1,000,000 = 1,000,000,000,000 이다.

1조나 되기때문에 1ms에 처리가 불가능 하다.

 

데이터에 숫자가 많으면 버블 정렬에 비해 속도가 엄청 빠르다.

하지만 임시 메모리를 두고 데이터를 복사해야하기 때문에 메모리 사용이 버블 정렬에 비해 크다.


데이터의 갯수가 1,000 개 수준이라면 버블 정렬을 이용해도 되지만 그 이상 만개가 된다면 병합정렬이나 퀵정렬을 고려해보아야 한다.




퀵정렬에 비해 병합정렬은 코드가 간단해서 구현하기가 쉬운편이고 퀵정렬에 비해 속도가 안정적이다.


병합정렬은 데이터를 반씩 쪼개서 반씩 정렬을 하는 방식이다.


4 1 2 3 을 오름차순 정렬 한다고 하면


4 과 1를 정렬하면 1 4 가 되고 

2와 3을 정렬 하면 2 3 이된다.

1 4 와  2 3을 정렬 하는데

각각 앞에서 부터 정렬을 시작한다.

1과 2를 비교하여 1이 작기 때문에 1을 넣고 그다음 4와 2를 비교하여 2가 작기 떄문에 1 2 로 저장하고

4와 3을 비교하여 3이 작기 때문에 1 2 3 이되고 마지막 4를 추가하여 1 2 3 4 가 된다.


모든 경우를 비교하지 않기때문에 속도가 빠르다.


기본적으로 병합정렬은 재귀함수로 구현한다.


반으로 쪼개서 다시 재귀함수로 호출하고


호출한 결과를 가지고 정렬을 한다.


이걸 계속 반복하는 방식이다.


- 바로 쓸 수 있는 병합 정렬(Merge Sort) 코드 오름차순 정렬 -


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mergeSort(int data[], int s, int e) {
    int tmp[10000];
    int i = s;
    int k = s;
    int m = (s + e)/2;
    int j = m + 1;
    if (s >= e) return; //쪼갤수 없음, 되돌아가기
    mergeSort(data, s, m); //분할
    mergeSort(data, m+1, e); //분할
    while ((i <= m) && (j <= e)) { //병합
        if (data[i] < data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while (i <= m) tmp[k++] = data[i++]; //나머지 병합
    while (j <= e)  tmp[k++] = data[j++]; //나머지 병합
    for (i = s; i <= e; i++) data[i] = tmp[i]; //복사
}
cs


- 실제 사용 예제 -


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
void mergeSort(int data[], int s, int e) {
    int tmp[10000];
    int i = s;
    int k = s;
    int m = (s + e) / 2;
    int j = m + 1;
    if (s >= e) return; //쪼갤수 없음, 되돌아가기
    mergeSort(data, s, m); //분할
    mergeSort(data, m + 1, e); //분할
    while ((i <= m) && (j <= e)) { //병합
        if (data[i] < data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while (i <= m) tmp[k++] = data[i++]; //나머지 병합
    while (j <= e)  tmp[k++] = data[j++]; //나머지 병합
    for (i = s; i <= e; i++) data[i] = tmp[i]; //복사
}
 
int main() {
    int data[] = { 1,5,2,4,3,7,-1,10,6 };
    mergeSort(data, 0, sizeof(data) / sizeof(int)-1);
    for (int i = 0; i < sizeof(data) / sizeof(int); i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}
cs



저작자표시 비영리

'알고리즘' 카테고리의 다른 글

C++ 스택(Stack), 연결 리스트(LinkedList) 코드  (0) 2018.06.07
구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용)  (0) 2018.06.02
C/C++ 2진 탐색(Binary Search) 예제 코드  (0) 2018.05.24
분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘  (0) 2018.04.02
1부터 n까지 합계 함수(for와 재귀)  (0) 2018.03.30
Posted by 꿈만은공돌
,

티스토리툴바