'프로그래밍/자료구조, 알고리즘'에 해당되는 글 3건

  1. 2016.01.29 덱(deque)
  2. 2015.04.12 빨간 눈의 승려 문제.
  3. 2015.04.02 자료구조 / 알고리즘


deque에 대해서 검색해보았다.


원문 출처 : http://mayple.tistory.com/entry/CSTL-7%EC%9E%A5-deque


deck과는 다르다! deck과는!


7.1 deque 데이터 추상(data abstraction)

 
deque`double-ended queue'의 약자이고, `덱(deck)'이라고 발음한다. 전통적으로, 이 용어는 콜렉션의 앞과 뒤 어느 곳에서나 삽입과 삭제가 가능한 데이터 구조들을 지칭하는데 사용되었는데, deque 컨테이너 클래스는 이것뿐만 아니라 더 많은 것을 할 수 있다. 실제로, deque 데이터 구조의 능력은 vector 클래스와 list 클래스가 제공하는 것들을 모두 포함한다.
  • vector와 같이 deque은 인덱싱이 가능하다. 콜렉션 내에서의 위치를 키로 사용함으로써, 첨자로 값들을 접근할 수 있다. (물론 list 클래스에서는 제공하지 않는 기능이다.)
  • list와 같이 deque의 앞과 뒤에 값을 효율적으로 추가할 수 있다. (vector 클래스에서는 vector의 맨뒤에서 값을 추가하는데 있어 효율적이다.)
  • list와 vector 클래스에서와 같이, deque가 관리하는 시퀀스의 중간에서 값들을 삽입할 수 있다. 이러한 삽입 연산은 list에서도 효율적인 연산이지만, vector에서는 조금 더 비용이 드는 연산이다.
간단히 말해서, deque은 vector와 list를 필요로 하는 곳에서 모두 사용할 수 있다. vector와 list 대신에 deque를 사용하게 되면, 종종 프로그램의 성능이 더 나아진다. 어느 데이터 구조를 선택할지에 관해서는 4.2절을 참고하기 바란다. 

7.1.1 Include 화일

deque 데이터 타입을 사용하는 프로그램은 모두 deque 헤더 화일을 사용해야 한다.
    #include <deque>
 
 

7.2 deque 연산

deque는 vector와 같은 방식으로 선언하고, 클래스 내부에는 vector와 동일한 타입 정의를 가지고 있다.
begin()과 end() 멤버 함수는 양방향 반복자를 제공하는 리스트와는 달리, 임의접근 반복자를 리턴한다.
삽입(insert()push_front()push_back())은 deque의 원소를 가리키는 반복자나 레퍼런스들을 무효화시킬 수도 있다. 이는 vector 데이터 타입과 같이 list에서의 삽입보다 더 제한적이다.
deque내의 원소 타입에 소멸자가 정의되어 있다면, deque로부터 원소를 삭제할 때, 이 소멸자가 호출될 것이다.
deque 데이터 타입이 임의접근 반복자를 제공하기 때문에, vector에 적용되는 모든 generic 알고리듬은 deque에도 사용될 수 있다.
vector는 커다란 하나의 메모리 블럭에 원소들을 가지고 있는 반면, deque은 많은 수의 좀더 작은 블럭들을 사용한다. 메모리 블럭의 사이즈에 제한을 두고 있는 시스템에서 이는 매우 중요한 사항이며, 이러한 이유때문에 deque은 vector보다 더 많은 원소들을 포함할 수 있다.
값들을 삽입할 때는, 콜렉션내의 원소와 연결되어 있던 인덱스가 바뀌게 된다. 예를 들어, 3번 위치에 값을 삽입하면, 원래 3번 자리에 있던 값은 4번자리를 차지하게 되고, 4번 자리에 있던 값은 5번자리로 차례로 옮겨지게 된다. 
 
 
 

7.3 예제 프로그램 - Radix Sort

 
The radix sort algorithm is a good illustration of how lists and deques can be combined with other containers. In the case of radix sort, a vector of deques is manipulated, much like a hash table.
Radix sorting is a technique for ordering a list of positive integer values. The values are successively ordered on digit positions, from right to left. This is accomplished by copying the values into "buckets," where the index for the bucket is given by the position of the digit being sorted. Once all digit positions have been examined, the list must be sorted.
The following table shows the sequences of values found in each bucket during the four steps involved in sorting the list 624 852 426 987 269 146 415 301 730 78 593. During pass 1 the ones place digits are ordered. During pass 2 the tens place digits are ordered, retaining the relative positions of values set by the earlier pass. On pass 3 the hundreds place digits are ordered, again retaining the previous relative ordering. After three passes the result is an ordered list. 
 
bucketpass 1pass 2pass 3
073030178
1301415146
2852624, 426269
3593730301
4624146415, 426
5415852593
6426, 146269624
798778730
878987852
9269593987
The radix sorting algorithm is simple. A while loop is used to cycle through the various passes. The value of the variable divisor indicates which digit is currently being examined. A boolean flag is used to determine when execution should halt. Each time the while loop is executed a vector of deques is declared. By placing the declaration of this structure inside the while loop, it is reinitialized to empty each step. Each time the loop is executed, the values in the list are copied into the appropriate bucket by executing the function copyIntoBuckets() on each value. Once distributed into the buckets, the values are gathered back into the list by means of an accumulation.
    void radixSort(list<unsigned int> & values)
    {
       bool flag = true;
       int divisor = 1;
       
       while (flag) {
          vector< deque<unsigned int> > buckets(10);
          flag = false;
          for_each(values.begin(), values.end(), 
                copyIntoBuckets(...));
          accumulate(buckets.begin(), buckets.end(), 
                values.begin(), listCopy);
          divisor *= 10;
          }
    }
The use of the function accumulate() here is slightly unusual. The "scalar" value being constructed is the list itself. The initial value for the accumulation is the iterator denoting the beginning of the list. Each bucket is processed by the following binary function:
    list<unsigned int>::iterator 
          listCopy(list<unsigned int>::iterator c, 
             deque<unsigned int> & lst)
    {
       // copy list back into original list, returning end
       return copy(lst.begin(), lst.end(), c);
    }
The only difficulty remaining is defining the function copyIntoBuckets(). The problem here is that the function must take as its argument only the element being inserted, but it must also have access to the three valuesbuckets, divisor and flag. In languages that permit functions to be defined within other functions the solution would be to define copyIntoBuckets() as a local function within the while loop. But C++ has no such facilities. Instead, we must create a class definition, which can be initialized with references to the appropriate values. The parenthesis operator for this class is then used as the function for the for_each() invocation in the radix sort program.
    class copyIntoBuckets {
    public:
       copyIntoBuckets
          (int d, vector< deque<unsigned int> > & b, bool & f) 
             : divisor(d), buckets(b), flag(f) {}
    
       int divisor;
       vector<deque<unsigned int> > & buckets;
       bool & flag;
    
       void operator () (unsigned int v)
       {   int index = (v / divisor) % 10;
           // flag is set to true if any bucket 
           // other than zeroth is used
           if (index) flag = true; 
           buckets[index].push_back(v);
       }
    };


'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글

덱(deque)  (0) 2016.01.29
빨간 눈의 승려 문제.  (0) 2015.04.12
자료구조 / 알고리즘  (0) 2015.04.02
Posted by GENESIS8

댓글을 달아 주세요

지식인에 알고리즘으로 올라와 있길래, 프로그래밍 문제인 줄 알고 풀고 있었는데;; 답 만 올린 분 걸 채택해 갔다는 비사가..

// 옛날에 승려들만 사는 섬이 있었다. 그들 중에는 눈이 빨간 사람과 갈색인 사람이 섰여있다.

// 눈이 빨간 사람은 마법에 걸려있기 때문에 자기의 눈이 빨갛다는 사실을 스스로 깨닫게 되면

// 그날 밤 12시에 목숨을 잃게 된다. 이 섬에 사는 승려들은 서로의 눈 색깔에 대하여 언급하는 것이 절대 금지 되어 있다. 

// 그리고 거을과 같이 비춰볼 수 있는 도구가 없으므로 자신의 눈색을 확인 못한다. 

// 그러던 어느날 이섬에 난파되어 온 선원이 이 섬 규칙을 몰랐으므로 절대로 해서는 안될 말을 내뱉고 말았다.

// “ 모든 스님들을 만나지 못했지만, 당신들 중에서 적어도 1명은 눈이 빨갛군요” 

// 선원은 그 날로 이섬을 떠났지만 남아 있던 승려들은 눈 색깔에 대한 말이 나왔으므로 크게 동요하기 시작했다.

// 그날 밤부터 이 섬에는 무서운 일이 벌어지기 시작했다. 과연 어떤일이 일어났겠는가 ?

//



// 이 이야기의 논리적 추론 과정은 다음과 같습니다.

// 승려가 자신이 빨간 눈 인지를 확인하는 과정이 되지요.

// 승려들은 생각을 합니다. 전부를 보았는데, 빨간 눈이 없다?

// 그렇다는 것은 선원의 말이 거짓이 아니라면, 내가 바로 그 빨간 눈이다!

// 라고 알게 되어 그날 밤 죽게 됩니다.


// 단 여기서 단서를 달았는데, 적어도 1명은 빨갛군요. 이죠? 응용문제에서

// 2명 , 3명이 빨간 경우에 대응하게 합니다. 

// 이 경우에는 스님의 논리적 추론 과정이, 빨간 눈인 누군가를 발견하고 (2명인 경우)

// 쟤가 죽겠구나.. 생각하다가 하루가 지나고, 그가 안 죽은 것을 보고, 어 설마 다른 누가 빨간 눈인가?

// 라고 생각합니다. 그리고 그것이 자신임을 깨닫고, 상대 방도 그렇게 되어 두 명 모두가 이튿날에 죽게 됩니다.


// 3명일 경우에는 개인이 두 명이 빨갛구나 하고 생각합니다만. 실은 3명이죠. 

// 2명인 이들을 보면서, 처음에 그들이 안 죽는 것을 보고, 아 서로가 둘이라서 죽지 않았거니 하고 생각 한 후

// 이튿날 둘이 자신들이 빨갛다는 것을 깨닫고 죽겠구나 싶지만, 죽지 않는 것을 보게 됩니다.

// 거기서 자기 자신도 빨간 눈이다.. 라는 것을 알게 되버리죠.


// 결론적으로 빨간 눈인 사람이 n명일 때 n일 만큼이 걸리게 됩니다.



// 이 이야기에서 우리가 생각해야할 것은 일단 갈색 눈 / 빨간 눈 이라는 플래그의 존재 (변수)

// 승려가 최소 두 명 이상이라는 점. (혼자라면 얘기가 성립하지 않겠죠) (최소 객체 수)

// 날짜 개념이 있다는 점은 카운트의 존재. (변수)

// 사망 플래그. (라고 얘기하니 이상합니다만. 죽었다 라는 개념이 존재하죠)


// 사고의 추론 과정을 알고리즘으로 표현할 수 있어야합니다. 그들은 어떻게 생각할까요?

// 네 즉, 자신 이외의 사람이 빨간 눈인지를 체크하는 탐색. 그리고 그런 경우에 사망으로 이어지는 제어.


// 이상의 것들이 알고리즘을 통해서 문제를 풀기 위한 준비라고 할 수 있겠습니다.


// 승려라는 객체를 표현하기 위해서 언어의 제약은 안두셨으니, 가장 편리한 C++을 사용하여 대응합니다.


#include <iostream>

using namespace std;


// 승려 객체.

class monk

{

public:

// 승려의 생성시 값을 초기화할 생성자

monk()

{

liveFlag = true;

redEye = false;

primaryKey = counter++;

}

// 빨간 눈의 존재 여부를 체크하는 함수. 다른 승려들을 확인한다.

void redEyeChecking(monk* const checkMonk)

{

// 빨간 눈의 수. 

int redEyeCount = 0;

// 인원 수 만큼 체크한다.

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

{

// 빨간 눈을 체크하되 체크하는 것은 자기 자신은 아니어야한다.

if( checkMonk[i].redEye == true && checkMonk[i].primaryKey != this->primaryKey)

{

redEyeCount++;

}

}

// 만일 탐색하였는데도 불구하고 빨간 눈을 발견 하지 못하면, 자신이 빨간 것을 알게 된다.

// 빨간 눈을 발견하였더라도, 2일 째에 그가 살아있다면 자신이 빨간 것이라 생각하게 된다.

// 즉. n명에 대하여 n일의 날짜가 방패역할을 하지만, 날짜가 n값이 되면 깨닫게 되어 그 다음날이 오기전엔 죽습니다.

if(redEyeCount < day)

{

// 즉. 눈의 수 보다 day가 크다면 죽게 됩니다.

death();

}


//이것이 성립할 수 있는 이유는.

// '자신의 눈이 빨갛지 않다' 면, 빨간 대상보다 redCount가 1 높게 됩니다.

// 즉 '내가 빨간 눈이다'라고 인식하는 결론에 도달하기 전에 빨간 자들이 죽기 때문입니다.

// 왜냐하면 빨간 눈이 2명 있고, 갈색 눈이 3명 있을 때. 5명이 서로 중의 빨간 눈을 센다면

// 빨간 눈인 이들은 1명이 빨갛다고 보겠지만, 갈색 눈인 3명은 2명이 빨갛다고 인식하기

// 때문 입니다.

}


void death()

{

// 자신이 빨간 눈이라는 걸 알게되면 죽는다.

cout << primaryKey << "번 승려가 죽었습니다. " << endl;

cout << "그는 " << ((redEye == true)?"빨간":"갈색") << " 눈 입니다." << endl;

liveFlag = false; //사망

}

public:

// 몇 일이 지났는가?

static int day;

// 몇 명의 승려가 존재하는 가? 생성된 승려의 수를 카운팅 하는 변수.

static int counter;


// 해당 승려의 '고유성'을 보장하는 키. 이를 통해서 자신과 타인을 식별한다.

int primaryKey;

// 해당 승려의 빨간 눈 상태 플래그.

bool redEye;

// 해당 승려의 사망 여부를 확인하는 플래그.

bool liveFlag;

};


int monk::counter;

int monk::day;


// 승려의 수 

#define MONK_COUNT 10

void main()

{

monk monkClass[MONK_COUNT];

 

// 이 부분을 주석화 시키면. 전체가 죽는다. (빨간 눈이 없는 거짓 증언의 경우. 스스로가 빨간 눈이라고 오판)

// 빨간 눈의 인수 만큼 생존 일 수가 늘어나고, 죽는다.

monkClass[0].redEye = true;

monkClass[3].redEye = true;

monkClass[5].redEye = true;

monkClass[8].redEye = true;


while(1)

{

// 이곳에서 체크합니다

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

{

monkClass[i].redEyeChecking(monkClass);

}

int LiveCount = 0;

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

{

if(monkClass[i].liveFlag == true)

{

LiveCount++;

}

}


if(LiveCount < MONK_COUNT)

{

// 카운트가 전체 수 보다 적다면 빨간 눈(?)이 죽었다.

// 정상적인 상황에서 승려가 죽었다는 것은, 논리적 결론에 도달한 자들이 사망했다는 의미가 됩니다.

// 따라서 빨간 눈을 가진 자는 죽었다. 고 결론 짓습니다.

// 이는 갈색눈의 사람들일 수도 있습니다. (갈색만 있는 경우. 즉 증언이 거짓이라면. 갈색들이 죽게 됩니다.)

cout << "day : " << monk::day << endl;

cout << "이제 빨간 눈을 한 승려들이 아무도 없습니다." << endl;

exit(0);

}


// 하루가 지났다.

monk::day++;

}

}





'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글

덱(deque)  (0) 2016.01.29
빨간 눈의 승려 문제.  (0) 2015.04.12
자료구조 / 알고리즘  (0) 2015.04.02
Posted by GENESIS8

댓글을 달아 주세요

자료구조 (Data Structure)

데이터를 효율적으로 관리하기 위해서 만든 구조.

알고리즘 (Algorithm)

어떠한 문제를 해결하기 위해 명확히 정의된 유한한 규칙과 절차들의 집합.


추상적 자료 구조 (Abtract Data Struct)

효율적인 자료구조를 만들기 위해 기능을 추상화하고 기능에 대한 연산 복잡도를 그 위에 추가적으로 정의한 것. 사용자는 내부를 몰라도 됨 == 인터페이싱

추상적 자료형(Abstract Data Type)와 비슷하지만, 자료 구조를 생성하는 데 한정되어 있다. 자료구조를 사용해 연산에 대한 복잡도를 추가된 것.

일반 ADT >> 데이터 + 절차

>> 삽입, 삭제, 검색을 위해서는 연산 시간이 얼마나 걸릴지.

>> 연산 복잡도 = 시간 복잡도 + 공간 복잡도

알고리즘 :

주어진 문제를 해결하기 위해 명확하게 정의된 절차와 규칙들의 유한 집합이다.

-> 문제 해결 방법. 문제를 해결 하기 위한 단계적인 절차



ex) 동대문 시장에서 김씨를 찾아와라 최대한 빠르게.

-> 1. 찾는 것이 가장 중요. [아무리 빠르더라도 문제를 해결하지 못하면 무쓸모]

-> 2. 문제 해결 중에서 얼마나 더 빠르게 할 수 있는지,


-> 3. '유한'해야한다. 알고리즘은 검증할 수 있어야하는데, 무한한 절차와 규칙을 수행한다면 이것은 검증 될 수 없다.


최대 공약수와 최소 공배수도 알고리즘.

1을 제외한 수로 곱해서..



What , How 생각 모델.


What -> 무엇을

How -> 어떻게


What1 -> How1

What2(How1) -> How2

What3(How2) -> How3


How가 나오면, 해당 How는 새로운 What이 된다.


What : xx은행 옆에 있는 빵집을 찾아야한다

How : 찾기 쉬운 xx은행을 먼저 찾는다.


What : 찾기 쉬운 xx 은행을 찾아야한다

How :: xx 은행이 어디 있는지 사람들에게 물어본다.




What -> 문제 (목적)

How -> 알고리즘 (해결 방법)


알고리즘의 조건 5가지


1. 입력('없음'입력도 입력이다. void. 0개 이상의 입력이 필요하다)

2. 출력[입력과 출력이 없다면 그것은 프로시저(절차)]

3. 명확성[어떤 것을 하는지 좋고 나쁨이 확실해야함] 

4. 유한성[종결성](끝나지 않으면 검증 , 사용할 수 없다)

5. 효율성(물론 실행이 가능해야한다.)



오토마타(Automata) 이론



자료구조 : 










'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글

덱(deque)  (0) 2016.01.29
빨간 눈의 승려 문제.  (0) 2015.04.12
자료구조 / 알고리즘  (0) 2015.04.02
Posted by GENESIS8

댓글을 달아 주세요