본문 바로가기

전체 글68

[자료구조] ep7-1) 트리(Tree) ㅇ트리(Tree) ADT: 계층적으로 저장된 데이터 원소들을 모델링 - 계층적 구조맨 위의 원소를 제외하고, 각 트리 원소는 부모(parent) 원소와 0개 이상의 자식(children) 원소들을 가진다(전제: 트리는 비어있지 않다 - 알고리즘 단순화) 내부 노드(internal node): 적어도 한 개의 자식을 가진 노드(A, B, C, F)외부 노드, 리프(external node, leaf): 자식이 없는 노드(E, I, J, K, G, H, D)형제(siblings): 같은 부모를 가진 노드들(G, H)조상(ancestor): 부모(parent), 조부모(grandparent), 증조부모(grand-grandparent) 등자손(descendant): 자식(child), 손주(grandchild.. 2024. 6. 9.
[자료구조] ep6+) 두 개의 큐로 스택 설계 문제) 두 개의 큐로 스택을 설계하라프로그램 요구사항 S : S에 대해 isEmpty() 호출 (isEmpty)t : S에 대해 top() 호출 (top)p n1 n2 n3 ... : S에 대해 push(n1), push(n2), push(n3) ... 를 차례로 호출 (push)P : S에 대해 push(n)을 100만번 호출 - 여기서 n은 10~99 사이의 정수 난수 (pushMillion) o : S에 대해 pop() 호출 (pop) q : 수행 종료 (quit)  실행예에서 괄호 속의 수는 해당 명령 수행직후의 스택 S 사이즈를 나타낸다. cputime X.XXXXXXXX는 측정된 cputime in milliseconds이다. 이 실행시간은 각 부함수에 대한 호출과 반환 사이에 소요된 cput.. 2024. 6. 9.
[자료구조] ep6-3) 데크(Deque) ㅇ데크(Double-Ended Queue) ADT: 임의의 개체들을 저장하며, 스택과 큐의 합체 방식으로 작동한다삽입(add)과 삭제(delete)는 앞(front)과 뒤(rear)라 불리는 양쪽 끝 위치에서 수행쉽게 말해서, 양쪽 방향으로의 add/delete 가 둘 다 가능하다   역시 마찬가지로 데크는 배열과 리스트 2가지 방법으로 구현할 수 있다 1. 이중연결리스트에 기초한 데크 2. 배열에 기초한 데크똑같이 선형 배열은 비효율적이므로, 원형 배열을 사용한다       문제) 데크는 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조다. 헤더 노드와 트레일러 노드가 없는 이중연결리스트를 사용하여 아래에 정의된 데크 함수들을 구현하시오.◦ 초기 상태- 주의 : 명령 수행.. 2024. 6. 9.
[자료구조] ep6-2) 원형 큐(Circular Queue) ※ 리스트에 기초한 큐는 ep6) 큐를 보도록 하자https://claremont.tistory.com/entry/ep6-%ED%81%90Queue ep6) 큐(Queue)ㅇ큐 ADT: 임의의 개체들을 저장하며, 선입선출(First-In First-Out, FIFO) 순서를 따른다삽입(enqueue)은 큐의 뒤(rear), 삭제(dequeue)는 큐의 앞(front)이라 불리는 위치에서 수행  - 직접 응용: 대기열, 관료claremont.tistory.com    배열로 선형 큐를 구현하면 공간 낭비, 공간의 재사용 불가 등의 문제가 발생한다그래서 보통은 원형 큐를 사용한다ㅇ원형 큐(Circular Queue): 선형 큐의 문제점을 보완하기 위한 자료구조환형 큐라고도 한다 빈 큐를 만원 큐로부터 차별하.. 2024. 6. 8.
[자료구조] 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.

티스토리툴바