본문 바로가기

Computer Science/자료구조24

[자료구조] ep6-1) 큐(Queue) ㅇ큐 ADT: 임의의 개체들을 저장하며, 선입선출(First-In First-Out, FIFO) 순서를 따른다삽입(enqueue)은 큐의 뒤(rear), 삭제(dequeue)는 큐의 앞(front)이라 불리는 위치에서 수행  - 직접 응용: 대기열, 관료적 체제, 공유자원에 대한 접근(e.g. 프린터), 멀티프로그래밍- 간접 응용: 알고리즘 구현, 자료구조 구현     큐도 마찬가지로 배열과 리스트 2가지 방법으로 구현할 수 있다연결리스트로에 기초한 큐는 배열로의 구현에 비해 동적 메모리 할당으로 크기에 유연하며, 메모리가 효율적이다※ 배열에 기초한 큐는 ep6-2) 원형 큐를 보도록 하자https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%E.. 2024. 6. 8.
[자료구조] ep5+++) 시간복잡도를 고려한 스택 설계 프로그램 요구사항1)  스택을 배열 또는 연결리스트 가운데 어느 것으로 구현해도 좋다.2)  주함수(즉, main 함수)는 아래에 보인 사용자의 명령 코드를 입력받을 때마다 해당 부함수를 호출하여 명령을 수행한다.p e : 스택에 원소 e를 삽입 (push)P : 스택에 100만개 원소를 삽입 (pushMillion)o : 스택으로부터 원소를 삭제 (pop)O : 스택으로부터 100100만 개 원소를 삭제 (popMillion) f : 스택 원소 중 최솟값 출력 (findMin)q : 수행 종료 (quit)3)  p, o, f 명령이 입력되면 별도로 작성된 push, pop, findMin 부함수를 각각 호출하여 수행한다. 4)  P 명령이 입력되면 주함수는 부함수 pushMillion을 호출한다. pu.. 2024. 6. 8.
[자료구조] ep5++) 수식표기법(스택을 이용한 후위수식) ㅁ수식표기법: 이항연산을 표현하는 방법으로, 연산자와 피연산자의 위치를 어떻게 적는지에 따라 3가지로 나뉜다  1. 중위수식(infix expression): 연산자를 피연산자 사이에 배치- 우리가 일반적으로 사용하는 수식- 암묵적 우선순위(precedence)- 우선순위는 괄호에 의해 무시예시: (A+B)xC-(DxE) 2. 후위수식(postfix expression): 연산자를 피연산자 뒤에 배치 (컴파일러가 사용하는 방식)- 역폴란드식(reverse Polish) 표기- 우선순위 x- 괄호 x- 스택을 사용예시: AB+CxDEx- 3. 전위수식(prefix expression): 연산자를 피연산자 앞에 배치- 폴란드식(Polish) 표기예시: -x+ABCxDE     문제1) 스택을 이용하여 입력 .. 2024. 6. 8.
[자료구조] ep5+) 심볼 균형(스택을 이용한 괄호 쌍의 대칭성 검사) 문제) 스택 응용으로, 키보드로부터 입력된 한 라인의 수식 문장 내 괄호 쌍의 대칭성을 검사하는 프로그램을 작성하세요. 괄호 쌍은 { }, [ ] , ( ), 세 종류가 있다.※ 주의: 한 개의 수식 문장은 1000개를 넘지 않는 문자로 이루어진다. 수식 문장은 공백문자를 포함할 수 있다. 검사 결과 대칭이 아니면 'Wrong_N'을, 대칭이면 'OK_N'을 출력한다. 여기서 N은 문장 내 괄호의 개수다.     (전체코드)#include char g_stack[1001] = {0};int g_top = -1; // 스택의 인덱스값int g_cnt = 0; // 괄호 총 개수int isBalanced(char* str);void push(char bracket);char pop();char peek();.. 2024. 6. 8.
[자료구조] ep5) 스택(Stack) ㅇ스택 ADT: 임의의 개체를 저장하며, 후입선출(Last-In First-Out, LIFO) 순서를 따른다삽입(push)과 삭제(pop)는 스택의 top(스택 포인터)이라 불리는 위치에서 수행  - 직접 응용: 웹페이지들의 기록, ctrl+z, Window OS에서 겹쳐진 윈도우들, C++이나 JVM에서 메서드의 연쇄적인 호출, 재귀의 구현 등- 간접 응용: 알고리즘 구현, 자료구조 구현   우리는 스택을 배열과 리스트 2가지 방법으로 구현할 수 있다   ※ 삽입과 삭제가 특정위치에서만 수행되므로, 헤더노드는 불필요        문제) 배열을 이용해 스택을 구현하시오원소 : 영문자 다음 연산을 지원해야 함.- push(stack, ‘c’) : stack의 top에 원소를 추가한다. stack이 이미 꽉.. 2024. 6. 7.
[자료구조] ep4+) 집합 ADT 활용문제들 문제1) 두 개의 집합 A와 B를 입력받아, A가 B의 부분집합인지를 검사하는 프로그램을 작성하라1) 집합은 오름차순 양의 정수로 저장 및 출력되어야 한다.2) 공집합은 공집합을 포함한 모든 집합의 부분집합이다.​3) 입력: 프로그램은 두 개의 집합 A, B를 차례로 표준입력받는다. 한 개의 집합을 나타내는 두 개의 입력 라인은 다음과 같이 구성된다. 첫 번째 라인: 정수 n (집합 크기, 즉 집합 원소의 개수) 두 번째 라인: 집합의 원소들 (오름차순 양의 정수 수열). 공집합은 첫 번째 라인은 0, 두 번째 라인은 존재하지 않는다.4) 출력: A ⊂ B이면 0을 출력하고, 그렇지 않으면 B에 속하지 않은 A의 가장 작은 원소를 표준 출력한다.5) 모든 집합은 헤더 노드가 없는 단일연결리스트(singl.. 2024. 5. 3.
[자료구조] ep4) 집합(Set) ㅇ집합 ADT: 유일한 개체들을 담은 용기 - 하나의 집합 ADT에는 중복되는 개체가 없다 (우리가 흔히 아는 집합형태)- 직접 응용: 키워드 검색엔진, 집합론에 관련된 다양한 계산- 간접 응용: 알고리즘을 위한 보조 자료구조, 다른 자료구조를 구성하는 요소 집합은 배열로 구현이 가능하지만 연결리스트로도 구현이 가능하다(각 노드는 하나의 집합원소를 표현) 집합 ADT의 주요 메소드 3가지ㅇunion(A, B): A, B집합의 합집합을 반환  ㅇintersect(A, B): A, B집합의 교집합을 반환  ㅇsubtract(A, B): A, B집합의 차집합(A - B)을 반환​​     참고 및 출처: 데이터 구조 원리와 응용(국형준), C언어로 쉽게 풀어 쓴 자료구조(천인국) 2024. 5. 3.
[자료구조] ep3-3) 다중연결리스트(Multi Linked List) 리스트의 확장: 공유 개념두 개의 배열을 이용하여 원소 및 그룹 리스트를 각각 구현한다 ㅇ다중연결리스트: 양방향 및 다중 방향 검색이 가능한 연결리스트     활용) 인터넷 쿠폰 사이트 '쿠몬'• 쿠폰의 총 가입자 수는 NG 명이며, 제공되는 쿠폰의 종류는 NE 종이다. 초기 데이터구조는 가입자의 배열 Groups(크기 NG)와 쿠폰의 배열 Elements(크기 NE)로 구성된다. 어떤 가입자 g가 어떤 쿠폰 e를 구매하면 삽입 알고리즘을 통해 다중연결리스트 내에 (e, g) 노드가 생성된다.• 쿠폰의 보유는 가입자 당 종별 최대 1 매로 제한한다.• NG = 5, NE = 4를 사용하고 가입자명은 [A,B,C,D,E]를 쿠폰 명은 [1,2,3,4]를 사용하시오.• 주함수에서 반복적으로 사용자의 명령코드.. 2024. 5. 3.
[자료구조] ep3-2) 이중연결리스트(Double Linked List) ㅇ이중연결리스트: 노드 간의 링크가 두 개     활용) 영문자 리스트 ADT순위는 1부터 시작한다고 가정하며 순위 정보가 유효하지 않으면 화면에 에러 메시지 "invalid position"을 출력하고, 해당 연산을 무시한다   두 가지 방법이 있다첫 번째 방법: 전역변수 사용 x- 헤더노드, 트레일러노드, 리스트의 크기에 대한 전역변수 사용 x (전체코드)#include #include typedef struct NODE { char e; // element struct NODE* prev; struct NODE* next;} NODE;void add(NODE* head, int r, char e);void delete(NODE* head, int r);void get(NODE* head, int r.. 2024. 5. 3.

티스토리툴바