스택6 [자료구조] 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. [자료구조] 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. [자료구조] ep2) 재귀(Recursion) ㅇ재귀(recursion): 종료조건을 만족하기 전까지 자기 자신을 계속해서 호출→ 종료조건을 잘 설정해야 한다진행 방향: 종료조건을 향하여 진행작동 원리: stack을 생각하자 (LIFO, 후입선출) 이 작동원리에 대한 마인드셋이 너무 너무 중요하다예를 들어 재귀함수는 3건의 요청이 들어온다 하면 한 함수가 3건의 요청을 처리하는 것이 아닌, 각각 3개의 함수가 1건의 요청을 처리하는 것이다 (재귀함수를 이해하기 위한 최고의 그림이자 예시이다, 세종대 컴공 교수님들 최고!) 참고 및 출처: 실전 C프로그래밍(나중채교수님, 한동일교수님), 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국) 2024. 4. 7. 이전 1 다음
