이전 포스팅
알고리즘 분석 | 스택 | 후위 표기법(Postfix notation) | 역 폴란드 표기법 | - 3 - 1
알고리즘 -2 리뷰 알고리즘의 실제 실행 시간을 평가하는 것은 어려울 수 있습니다. 이는 입력 크기, CPU 주파수, 사용 가능한 RAM, 데이터 전송 속도 및 자원을 선점하는 프로그램 등의 여러 요인
jelong.tistory.com
큐 (Queues)
큐(Queue)는 현실 세계에서 사용하는 대기열과 같이 먼저 들어온 것이 먼저 처리되는 (FIFO) 데이터 구조입니다.
큐(Queue)에 객체는 언제든지 뒤쪽(rear)에 삽입될 수 있지만, 큐의 맨 앞쪽(front)에 있는 요소만이 제거될 수 있습니다. 큐의 예로는 인쇄 대기 작업 목록과 같은 것이 있습니다.
요소들은 뒤쪽에서 큐에 들어가며, 맨 앞쪽에서 제거됩니다. 즉, 새로운 요소는 큐의 뒤쪽으로 추가되며, 큐의 맨 앞 요소가 처리될 때마다 큐에서 제거됩니다. 이러한 방식으로 큐는 먼저 들어온 작업이 먼저 처리되도록 보장합니다
ADT 란
ADT란, 추상 데이터 타입(Abstract Data Type)의 약자입니다. 추상 데이터 타입은 데이터의 구현 방법을 명시하지 않고, 해당 데이터가 가져야 할 연산들을 정의한 것입니다.
즉, ADT는 데이터 타입이 가져야 할 기능(메소드)들의 명세서라고 볼 수 있습니다.
예를 들어, 리스트 ADT는 데이터를 저장하고 조회하며, 데이터를 추가하고 삭제할 수 있는 기능들을 포함할 수 있습니다
큐 메서드(Queue ADT)
큐(Queue) ADT는 다음과 같은 기본 메소드를 지원합니다:
- enqueue(Obj): 객체 Object를 큐의 뒤쪽(rear)에 삽입합니다.
- dequeue(): 큐의 맨 앞쪽(front)에서 객체를 제거하고 반환합니다. 큐가 비어있는 경우 오류가 발생합니다.
enqueue()와 dequeue() 이외에도 다음과 같은 메소드가 있습니다:
- size(): 큐 내의 객체 수를 반환합니다.
- isEmpty(): 큐가 비어있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
- isFull(): 큐가 가득 찼으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
- front(): 큐의 맨 앞쪽(front)에 있는 객체를 반환하지만 제거하지 않습니다. 큐가 비어있는 경우 오류가 발생합니다.
큐와 다중 프로그래밍
다중 프로그래밍(Multiprogramming)은 제한된 병렬성을 구현하는 기술입니다. 이 기술을 사용하면 여러 개의 작업 또는 스레드를 동시에 실행할 수 있습니다. 예를 들어, 컴퓨터 또는 프로그램은 여러 개의 스레드를 사용할 수 있으며, 그 중 하나는 마우스 클릭을 처리하고, 다른 하나는 화면에 애니메이션을 그리는 역할을 할 수 있습니다.
하지만, 여러 스레드를 사용하는 프로그램(또는 운영 체제)을 설계할 때, 하나의 스레드가 CPU를 독점하는 것을 방지해야 합니다. 이를 해결하는 방법 중 하나는 큐(Queue)를 사용하여 라운드 로빈 프로토콜(round robin protocol)로 CPU 시간을 스레드에 할당하는 것입니다. 여기서 우리는 스레드의 컬렉션을 보관하는 큐를 사용할 수 있습니다. 큐의 시작 부분에 있는 스레드는 제거되어 CPU 시간 일부를 할당받은 후, 다시 큐의 뒷부분에 삽입됩니다. 이렇게 하면 모든 스레드가 공평하게 CPU 시간을 할당받을 수 있습니다.
리스트 ADT(List ADT)
리스트는 데이터의 집합입니다. 이 데이터들은 각각 노드(node)라는 것에 저장됩니다. 각 노드는 데이터 필드와 다음 요소를 가리키는 포인터를 포함합니다. 데이터를 리스트에 삽입하려면 새로운 노드를 리스트에 삽입하고 포인터를 다시 할당하면 됩니다.
리스트 ADT는 데이터를 참조, 업데이트(삽입 및 삭제)하고 검색하는 방법을 지원합니다. 단일 연결 리스트 또는 이중 연결 리스트로 구현할 수 있습니다.
예를 들어, 단일 연결 리스트(singly-linked list)에서는 각 노드가 다음 노드를 가리키기 때문에 처음부터 순차적으로 데이터를 찾아가야합니다. 이중 연결 리스트(doubly-linked list)에서는 양쪽으로 순회할 수 있으므로 검색과 삭제 작업이 더욱 효율적입니다
단일 연결 리스트(singly-linked list)
Singly Linked List는 각 Node가 다음 Node를 가리키는 포인터만을 가지고 있습니다. 이렇게 되면, 리스트의 끝에 도달하면 다음 Node를 가리키는 포인터가 NULL 값을 가지기 때문에 더 이상의 데이터가 없음을 알 수 있습니다. 이러한 Singly Linked List는 데이터를 삽입하거나 삭제할 때, 해당 위치의 Node를 찾아야 하기 때문에 탐색 시간이 오래 걸릴 수 있습니다
이중 연결 리스트(doubly-linked list)
Doubly Linked List는 각 Node가 다음 Node와 이전 Node를 가리키는 포인터를 가지고 있습니다. 이렇게 되면, Singly Linked List와는 달리 앞 뒤로 모두 탐색할 수 있기 때문에 삽입, 삭제 시에도 이전 Node와 다음 Node를 모두 참조하므로 탐색 시간이 더욱 감소할 수 있습니다. 단, 포인터의 수가 2배 더 필요하므로 저장 공간이 더 많이 필요합니다.
참조 메서드(Referring methods)
리스트 ADT는 다음과 같은 참조 메소드를 지원합니다:
- first(): 첫 번째 요소의 위치를 반환합니다. 리스트 S가 비어 있으면 오류가 발생합니다.
- last(): 마지막 요소의 위치를 반환합니다. 리스트 S가 비어 있으면 오류가 발생합니다.
- isFirst(p): 요소 p가 리스트의 첫 번째 항목인 경우 true를 반환하고 그렇지 않은 경우 false를 반환합니다.
- isLast(p): 요소 p가 리스트의 마지막 요소인 경우 true를 반환하고 그렇지 않은 경우 false를 반환합니다.
- before(p): 위치 p 다음에있는 요소의 위치를 반환합니다. p가 첫 번째 요소인 경우 오류가 발생합니다.
- after(p): 위치 p 이전에있는 요소의 위치를 반환합니다. p가 마지막 요소인 경우 오류가 발생합니다.
업데이트 메서드(Update methods)
리스트 ADT는 다음과 같은 업데이트 메소드를 지원합니다:
- replaceElement(p,e): (p - 위치, e - 요소) 위치 p에 있는 요소를 e로 대체합니다.
- swapElements(p,q): (p,q - 위치) 위치 p와 q에 있는 요소를 서로 바꿉니다.
- insertFirst(e): (e - 요소) 리스트 맨 앞에 요소 e를 삽입합니다.
- insertLast(e): (e - 요소) 리스트 맨 뒤에 요소 e를 삽입합니다.
- insertBefore(p,e): (p - 위치, e - 요소) 위치 p 바로 앞에 요소 e를 삽입합니다.
- insertAfter(p,e): (p - 위치, e - 요소) 위치 p 바로 뒤에 요소 e를 삽입합니다.
- remove(p): (p - 위치) 위치 p에 있는 요소를 삭제합니다
예시 : insertAfter(1,e)
1 ㅡㅡ> 3 ㅡㅡ> 4
리스트가 다음과 같이 존재할때, 예시와 같은 함수를 호출한다면 어떻게 바뀔까?
정답 :
1 ㅡㅡ> e ㅡㅡ> 3 ㅡㅡ> 4