참된코딩

덱(Deque)

데이터를 앞으로도 뒤로도 넣을 수 있고,

앞으로도 뒤로도 뺄 수 있는 자료구조이다.

양반향 연결 리스트 기반으로 '덱' 구현.

 1->2->3->null 이렇게 연결되어있는 리스트가 있다고 하자. (이 때 Head : 1)

이 리스트의 내용을 반대로 뒤집을 것이다.

뒤집으면 3->2->1->null이 된다. (이 때 Head : 3)

※ 양방향으로 연결되어있지 않다.

방법은 생각해보면 간단하다.

현재 노드가 가리키는 포인터를 반대 방향의 노드를 향하게 하면 되는 일이다.

Head에 접근하여 순서대로 끝 노드까지 접근하자.

현재 끝 노드는 null를 가르키고 있다.

이 노드의 포인터를 반대 방향의 노드에 가르켜야 한다.

여기서 문제가 생긴다.

1. 각 노드의 포인터 방향을 모두 바꾼다고 했을 때 1은 null을 가르켜야 한다.

하지만 1은 Head이다. 방향이 바뀐다면 3이 Head가 될 필요가 있다.

그러면 포인터의 방향을 바꿔주는 작업을 하기전에 끝 노드에 접근하여 그 노드를 가르킬 노드를 임시로 생성해줄 필요가 있다.

그 부분이 15,16행이다.

15,16행은 끝 노드로 접근하는 과정이고 while이 끝나게 되면 pNode는

끝 노드를 가르킨채 반복문에서 빠져나오게 된다.

이때 18행에서 임시로 변수를 생성해주고 그 변수가 끝 노드를 가르키도록 하면 된다.

※ Head를 처음부터 바꾸지 않는다.

각각의 노드들의 포인터를 바꿔줘야 하는데,

한 번에 모든 노드들의 방향을 바꿀수 없기 때문이다.

노드 하나의 포인터를 바꿔주면 다시 처음부터 노드에 접근하여 포인터 방향이 바뀌지 않은 노드까지

이동 후 포인터 방향을 바꿔준다. 모든 포인터 방향이 바뀔때까지 이 작업을 반복한다.

모든 포인터의 방향이 바뀌었을 때 Head에 임시 변수를 대입하면 모든 작업은 끝나게 된다.

pNode를 3까지 접근시켜 3의 포인터를 null이 아니라 2를 가르키게 하자.

그러면 2와 3은 서로를 가르키게 된다.

그러면 다시 pNode를 2까지 접근 시키고 2의 포인터를 1을 가르키게 하자.

pNode를 1에 접근시켜 1의 포인터를 null을 가르키게 하자.

이제 Head를 3으로 옮기자 3의 위치는 임시변수인 Temp가 가지고 있다.

※ DataLen은 전역변수로 리스트에 데이터가 하나 추가될때마다 1씩 증가한다.

즉, 리스트에 데이터가 3개 존재한다면 DataLen은 3이된다.

▷ 기본개념

1. 데이터를 담을 테이블을 미리 크게 확보해 놓는다.

2. 입력받은 데이터를 해시하여 테이블 내의 주소를 계산한다.

3. 나온 주소에 데이터를 담는다.

※ 

- 해시 테이블은 궁극의 탐색 알고리즘이다.

- 해시 테이블의 성능은 공간을 팔아 얻어낸 것이다.

▷ 특징

해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.

▷ 용어정리

1. 충돌 (Collision)

- 서로 다른 입력 값에 대해 동일한 해시 값.

- 해시 테이블 내의 동일한 주소를 반환 하는것.

※ 

- 알고리즘을 정교하게 설계한다고 해도 모든 입력값에 대해 고유한 값을 만들지 못한다.

=> 해시 함수의 충돌은 피할 수 없다는 것이다.

2. 클러스터(Cluster)

- 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제.

▷ 해쉬 테이블의 검색 성능.

- 해쉬 테이블의 검색성능은 해쉬 함수의 성능과 해쉬 테이블의 크기에 좌우된다.

- 충돌이 많이 발생하면 성능은 O(n)에 가까워지므로 충돌을 최대한 억제시키는 것이 해쉬의 핵심 포인트다.

▷ 해시(Hash)

- 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다.

- 해시는 검색 방법이라기보다는 빠른 검색을 위해 자료를 관리하는 기법이라고 보면 된다.

실 생활에서도 해시 기법은 흔히 사용된다.

수첩에 주소록을 작성할 때 '가나다'순으로 페이지를 미리 분류하고 이름의 첫 글자를 기준으로

주소를 적는 방법이 바로 해싱이다.

1. 해시 테이블(Hash Table) : 자료가 저장되는 전체 저장소.

2. 버킷(Bucket) : 주소록의 예에서 보면 ㄱ, ㄴ, ㄷ, ㄹ의 각 페이지가 버킷이다.

3. 슬롯(Slot) : 페이지를 버킷(Bucket)이라고 한다면 페이지에 주소를 기록하는 칸을 슬롯이라고 보면 된다.

4. 해시 함수 : 새로운 자료가 입력될 때 어떤 버킷에 넣을지를 결정하는 연산.

Code

결과

▷ 큐(Quene)

- 큐(Queue)의 데이터 제거는 대기 줄의 가장 앞에서 수행되며, 

  데이터의 삽입은 대기 줄의 가장 뒤에서 수행되는 제한된 리스트 구조를 말한다.

- 가장 먼저 삽입된 데이터가(First In) 가장 먼저 제거되는(First Out) 선입선출(FIFO)형태의 자료구조를 가지고 있다.

- 제일 처음에 입력된 데이터를 front라고 하고,

- 가장 나중에 입력된 데이터를 rear라고 한다.

- 데이터의 삽입은 rear에서 이루어지고,

- 삭제는 front에서 이루어진다.

제공되는 큐를 이용하여 만들기.

직접구현.

양방향

결과

▷ 스택(Stack)

 - 스택은 데이터 입/출력이 한쪽으로만 접근할 수 있는 자료구조이다.

 - 가장 나중에 들어간 데이터가 제일 먼저나오게 되는 구조이다.

 - 선형구조 라고도 한다.

데이터의 입력이 A=> B=> C=> D 순서인 구조에서 자료를 꺼내거나 삭제하려면 다음과 같은 동작이 필요하다.

제공되는 스택을 쓸 경우.

push     : 데이터를 추가한다.

top       : 최상위 데이터를 반환한다.

pop      : 최상위 데이터를 삭제한다.

isEmpty : 현재 스택이 Null인지 아닌지 확인 후 true/false을 반환한다.

직접 구현할 경우 보통 사용법.

push     :  데이터를 추가한다.

Peek     :  최상위 데이터를 반환한다.

pop      :  최상위 데이터를 반환 후 데이터를 삭제 or 데이터를 삭제한다. ( 구현자 입맛대로. )

isEmpty : 현재 스택이 Null인지 아닌지 확인 후 true/false을 반환한다.

라이브러리 사용 스택.

직접 구현한 스택.

결과

▷ 단방향 연결 리스트(Linked List)

형태

▷구성방법

시작전.

 1). 데이터를 담을 구조체를 만든다.

 2). 헤드(Head)변수를 만든다.

0. 데이터 출력.

 1). 헤드를 가르킬 임시 노드 변수를 만든다.

 2). 노드가 null이 아닐경우 그 노드가 가지고 있는 데이터를 출력한다.

 3). 노드를 한칸 앞으로 이동해준다.

 4). 현재 노드가 null이 나올때까지 2~3번을 반복한다.

1. 데이터 추가

 1). 노드를 생성한다.

 2). 헤드의 포인터를 처음 생성된 노드에 가르킨다.

 3). 노드를 생성한다.

 4). 헤드를 가르킬 임시 노드 변수를 만든다.

 5). 현재 노드가 가르키는게 null이 나올때까지 노드 이동을 한다.

 6). 현재 노드가 가르키는게 null일경우 새롭게 추가한 노드를 가르킨다.

 7). 데이터를 추가 할 때 마다 4~6번을 반복한다.

2. 데이터 모두 삭제.

 1). 헤드를 담을 임시 노드 변수를 생성한다.

 2). 헤드 노드를 한 칸 앞으로 이동시킨다.

 3). 임시 노드 변수를 삭제한다.

 4). 헤드가 가르키는 노드가 null일때까지 1~3번을 반복한다.

3. 데이터 선택 삭제

 1). 자신이 삭제할 데이터를 담을 변수를 하나 만들어서 데이터를 입력받는다

 2). 첫 번째 노드(헤드)가 삭제할 데이터이면 새로운 노드 변수를 만들어 헤드를 담고

     헤드를 한 칸 전진한 뒤 만든 변수를 삭제.

 3). 첫 번째 노드(헤드)가 삭제할 데이터가 아니라면 헤드를 담을 변수와 헤드를 담을 변수의 전 노드를 가르킬 변수를

     만든다.

 4). 노드를 한 칸씩 전진 시키며 자신이 입력한 데이터와 같은지 비교한다. 

 5). 같다면 삭제 전용 변수의 포인터를 처음 만든 노드에 가르키고 두 번째 만든 노드는 처음 만든 노드가 가르키는 노드를 가르      킨다.

 6). 삭제 전용 노드 변수를 삭제한다.

4. 데이터 선택 추가.

  1). 삽입할 데이터를 입력받는다.

  2). 몇 번째에 삽입할건지 인덱스를 입력 받는다.

  3). 첫 번째 인덱스에 데이터를 삽입할 경우 새롭게 만든 노드를 헤드에 연결시킨 뒤

      헤드를 새롭게 만든 노드를 가르킨다.

  4). 첫 번째 인덱스에 데이터를 삽입하는게 아닐경우 입력받은 인덱스 - 1 만큼 노드를 이동한다.

      새롭게 만든 노드를 현재 노드의 다음 노드에 연결 시킨뒤 현재 노드의 포인터를 새롭게 만든 노드에 가르킨다.

0). 데이터 출력 (Data DisPlay)

1). 데이터 추가(DataAdd)

2). 데이터 모두 삭제(Data All Delete)

3). 데이터 선택 삭제(Data Select Delete)

예외처리 추가.

4). 데이터 선택 삽입(Data Select Insert)

▷ 연결 리스트(Linked List)

1. 단방향 연결 리스트.

- 한쪽 방향으로 연결된 리스트이다.

- 자료 생성시 노드가 생성되고 포인터는 생성된 포인터를 가르킨다.

2. 양방향 연결 리스트

- 양쪽 방향으로 연결된 리스트이다.

- 자료 생성시 노드가 생성되고 포인터는 생성된 포인터를 가르킨다.

그리고 새로 생성된 노드의 포인터는 전 노드를 가르킨다.

3. 환형 연결 리스트

- 양방향 연결 리스트와 비슷하지만 마지막 노드의 포인터가 가리키는 노드는 리스트의 처음 노드이다.

장점: 늘어선 노드의 중간지점 자료의 추가와 삭제가 O(1)의 시간내에 가능하다.

단점: 특정 위치의 데이터를 검색하는데에 O(n)의 시간이 걸린다는 단점이 있다.

▷ 퀵 정렬 (Quick Sort)

 정렬 알고리즘 중에 평균 실행 속도가 가장 빠르고 우수하므로 퀵 정렬(Quick sort)라는 명칭으로 불린다.

▷ 정렬방법.

1. 먼저 PIVOT 계수를 정한다. PIVOT 계수는 임의로 선정할 수 있으나, 중간 크기의 숫자를 PIVOT 계수로 선정하는 것이 가장 효율적이기 때문에 대부분 3개의 임의의 숫자를 랜덤으로 선택한 후 3개 중 가운데 값을 PIVOT 계수로 정한다.

2. PIVOT 값과 LEFT 값을 비교한다. 만약 LEFT 값이 PIVOT 값보다 크다면 PIVOT 값과 RIGHT 값을 비교한다.

RIGHT 값이 PIVOT 값보다 크다면, RIGHT 인덱스를 왼쪽으로 위치시킨 후 다시 PIVOT 값과 비교한다.

3. RIGHT 값이 PIVOT 값보다 작다면, LEFT 값과 RIGHT 값을 바꾼 후, LEFT 값을 오른쪽으로 한칸 전진시킨다.

4. LEFT 값과 RIGHT 값이 만날 때까지 2~3번 과정을 반복한다.

5. LEFT와 RIGHT가 만나면 해당 값과 PIVOT 값을 비교한다. PIVOT 값이 크면 오른 쪽 작으면 왼쪽에 위치 시킨다.

6. 3을 기준으로 블록을 크게 3보다 큰 값, 3보다 작은 값으로 나뉘게 된다. 3보다 작은 블록에 대해 다시 PIVOT 계수를 설정한다.

7. 기존에 한 방식대로 다시 LEFT와 RIGHT 값을 PIVOT과 비교한 후, 값을 교환한다.

8. 3보다 큰 블록에 대해서도 위와 같이 비교한다.

9. 최종 sorting이 완료된다.

Code.

결과

▷ 합병정렬(Merge sort)

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다.

▷ 정렬방법.

1. 데이터 집합을 반으로 나눈다.

2. 데이터 집합의 크기가 2이상일 경우 하나의 원소가 될때까지 1번을 반복한다.

3. 같은 집합에서 나뉘어진 원소끼리 정렬하면서 집합으로 만든다.

4. 모든 원소가 하나의 집합이 될때까지 3번을 반복한다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

※ 분할 - 파란색 블록은 기준점이다.

※ 정복

Code 

결과

▷ 쉘 정렬 (Shell sort)

쉘 정렬은 삽입 정렬이 어느 정도 정렬된 리스트에 대해서는 대단히 빠른것에 착안한 방법이다.

쉘 정렬은 삽입 정렬과는 다르게 전체의 값을 한 번에 정렬하지 않는다.

쉘 정렬은 일정한 기준에 따라 값을 분류한 후 부분 리스트들을 만들고 그 부분 리스트들에 대해서 삽입정렬을 실행한다.

그리고 각 정렬될 리스트들을 모아서 하나로 만든 후 삽입정렬을 실행한다.

삽입 정렬은 이미 정리되어 있는 데이터에 대해서는 연산을 하지 않기 때문에 부분을 미리 정렬하고 전체를 정렬할 경우

연산이 줄어들기 때문에 순수한 삽입 정렬보다는 효율이 좋다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

시작 : 7 2 4 1 8 3 5 9 6 10

1. 간격을 5로 잡고 각 간격에 있는 숫자들을 각각 모아 삽입정렬로 정렬한다.

※ 간격은 자신의 마음대로 정해도 된다.

한 번 정렬된 결과.

2. 정렬이 끝났으면 간격을 2로 나눈다.

※ 5를 나눴을 때 2.5 하지만 소수점 자리는 버린다.

3. 간격이 2로 바뀌었으므로 2간격으로 떨어진 숫자들을 모아 삽입정렬한다.

두 번째 정렬된 결과.

4. 정렬이 끝났으면 간격을 2로 나눈다.

5. 간격이 1로 바뀌었으므로 전체에 대한 삽입정렬을 실행한다.

6. 간격이 1보다 작아지면 반복을 중지한다.

7. 정렬 완료.

Code

결과.