CS (9) 썸네일형 리스트형 [자료구조] 9. 큐(Queue) - 덱 ADT / 덱 구현 더보기 9.1. 덱의 ADT 9.2 배열 기반 덱 구현 1) 덱 구현 2) 덱 연산 구현 덱(deque)은 double-ended-queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입 및 삭제가 가능하다. 덱을 구현하는 방법도 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다. 9.1 덱의 ADT ◾ 객체 : n개의 element형 요소들의 순서 있는 모임 ◾ 연산 • create() : 덱을 생성 • initDeque(dq) : 덱을 초기화 • isEmpty(dq) : 덱이 공백 상태인지 검사 • isFull(dq) : 덱이 포화 상태인지 검사 • addFront(dq,e) : 덱의 전단에 요소를 추가 • addRear(dq,e) : 덱의 후단에 요소 추가 • dele.. [자료구조] 8. 큐(Queue) - 큐 ADT / 선형큐,원형큐 구현 더보기 큐란? / 큐의 특징 8.1 큐 ADT 8.2 큐의 구현 방법 8.3 선형큐 1) 선형큐 구현 2) 선형큐 연산 구현 8.4 원형큐 1) 원형큐 구현 2) 원형큐 연산 구현 스택과 마찬가지로 큐 또한 선형 자료구조이 일종이다. 스택이 후입선출(LIFO) 구조인 반면 큐는 선입선출(FIFO) 구조이다. 스택의 경우 삽입과 삭제가 같은 쪽에서 일어나지만, 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다. [큐의 특징] 선입선출, FIFO(First-In-First-Out) : 가장 먼저 들어온 데이터가 먼저 나가는 구조. 큐는 뒤에서 새로운 데이터가 추가되고, 앞에서 데이터가 하나씩 삭제되는 구조이다. 데이터 삽입이 일어나는 곳을 후단 (rear), 데이터 삭제가 일어나는 곳을 전단(front)라고 한다.. [자료구조] 7. 스택(Stack) 더보기 스택이란? / 스택의 특징 7.1 스택 ADT 7.2 스택의 구현 방법 7.3 배열 기반 스택 구현 1) 전역 변수로 구현 2) 스택 구조체 타입을 정의하여 구현 7.4 동적 배열 기반 스택 구현 7.5 연결 리스트 기반 스택 구현 1) 노드 / 연결된 스택 정의 2) 연결된 스택 연산 구현 스택은 선형 자료구조의 일종이다. 스택은 우리 주변의 사물 중 프링글스 과자 통에 비유할 수 있다. 프링글스 과자 통은 한쪽은 뚫려 있고 한쪽은 막혀 있다. 과자는 통의 뚫려 있는 부분에서 막혀 있는 부분으로 들어가 차곡차곡 쌓이게 된다. 먼저 들어간 과자일수록 통의 아랫부분에 위치하고 나중에 들어간 과자일수록 통의 윗부분에 위치할 것이다. 반대로 과자를 꺼내 먹을 때는 윗부분에 위치한 과자일수록 먼저 꺼내어.. [자료구조] 6. 리스트(List)3 - 원형 연결 리스트 / 이중 연결 리스트 더보기 원형 연결 리스트와 이중 연결 리스트란? 6.1 원형 연결 리스트 1) 원형 연결 리스트란? 2) 노드 정의link가 가리키도록 원형 연결 리스트를 조금 변형하면 원형 연결 리스트를 더 효율적으로 사용할 수 있다. 2) 노드 정의 단순 연결 리스트에서의 노드 정의와 동일하다. // 노드 정의 typedef int element; //노드에 저장할 요소의 자료형 typedef struct ListNode { // 노드 정의 element data; struct ListNode* link; }ListNode 3) 원형 연결 리스트 연산 구현 [원형 리스트의 처음에 삽입] 새롭게 삽입할 노드의 링크인 node->link가 기존의 첫 번째 노드를 가리키게 하고, 마지막 노드의 링크는 삽입한 노드를 가리키.. [자료구조] 5. 리스트(List)2 - 단순 연결 리스트 구현 더보기 단순 열결 리스트란? 5.1 단순 연결 리스트 구현 1) 노드의 정의 2) 단순 연결 리스트 생성 3) 노드의 생성 4) 노드의 연결 5.2 단순 연결 리스트 연산 구현 1) 삽입 연산 2) 삭제 연산 3) 방문 연산 4) 기타 연산 5) 연결 리스트 연산 예시 단순 연결 리스트 : 하나의 방향으로만 연결 되어 있는 연결 리스트. 단순 연결 리스트에서는 노드들이 하나의 링크 필드를 가지며 마지막 링크 필드의 값은 NULL이 된다. 5.1 단순 연결 리스트 구현 1) 노드의 정의 노드는 자기 참조 구조체를 이용하여 정의된다. * 자기 참조 구조체 : 자기 자신을 참조하는 포인터를 포함하는 구조체 // [노드의 정의] typedef int element; typedef struct ListNode {.. [자료구조] 4. 리스트(List)1 - 리스트ADT / 순차 리스트와 연결 리스트 / 순차 리스트 구현 더보기 리스트란?, 리스트의 특징 4.1 리스트의 ADT 4.2 리스트의 구현 방법 4.3 순차 리스트 구현 1) 순차 리스트의 정의 2) 순차 리스트 기초 연산 3) 항목 추가 연산 4) 항목 삭제 연산 4.4 연결 리스트 1) 연결 리스트의 구조 2) 연결 리스트의 종류 리스트에는 데이터들이 차례대로 나란히 저장되어 있다. [리스트의 특징] 리스트의 항목들은 순서 또는 위치를 가진다. 중복된 데이터의 저장을 막지 않는다. 4.1 리스트의 ADT [리스트의 ADT] ◾ 객체 : n개의 요소들로 구성된 순서 있는 모임. ◾ 연산 : 리스트를 초기화한다. 특정 위치에 요소를 추가한다. 맨 처음 위치에 요소를 추가한다. 맨 끝 위치에 요소를 추가한다. 특정 위치의 요소를 제거한다. 리스트의 모든 요소를 제거.. [자료구조] 3. 재귀의 활용 더보기 재귀함수란? 1) 팩토리얼 계산 2) 거듭제곱값 계산 3) 피보나치 수열 4) 이진 탐색 알고리즘 5) 하노이 타워 재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수. => 동일한 패턴의 작업을 반복해서 진행 * 재귀의 탈출 조건이 반드시 있어야 한다. 1) 팩토리얼 계산 [재귀함수 탈출 조건] : 0!을 구함 #include // 팩토리얼 함수 int Factorial(int n) { if (n == 0) return 1; else return n* Factorial(n - 1); } int main(void) { int n = 5; printf("%d! = %d", n, Factorial(n)); return 0; } 2) 거듭제곱값 계산 [재귀함수 탈출 조건] : 0제곱 값을 구함 #.. [자료구조] 2. 알고리즘 성능 분석 - 시간 복잡도 분석 / 빅오 표기법 더보기 알고리즘 성능 평가 지표 2.1 시간 복잡도 분석 방법 시간 복잡도 분석이란? 1) 시간 복잡도 함수 2) 알고리즘 효율성의 세 가지 경우 2.2 빅오 표기법 빅오란? 1) 빅오의 수학적 판별법 2) 간단하게 빅오를 구하는 방법 3) 대표적인 빅오 알고리즘의 성능은 '속도'와 '메모리의 사용량' 이렇게 두 가지 지표로 평가된다. 시간 복잡도 : 속도에 해당하는 알고리즘의 수행 시간 분석 결과. 공간 복잡도 : 메모리 사용량에 대한 분석 결과. 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행 속도에 초점을 둔다. 2.1 시간 복잡도 분석 방법 알고리즘을 이루고 있는 연산의 횟수를 세는 방법. 직접 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 .. 이전 1 2 다음
