본문 바로가기

Computer Science59

[자료구조] 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.
[데이터베이스] ep1) DB 모델 ㅁ논리적 데이터 모델들1. 계층형 데이터 모델  2. 네트워크형 데이터 모델  3. 관계형 데이터 모델(RDB: Relational DataBase)- 우리는 이 RDB에 대해 앞으로 지겹도록 다룰 것이다   ㅁRDB 데이터 모델: 2차원 테이블(릴레이션) 형태로 데이터를 표현 ㅇ스키마(schema): db에 저장되는 데이터 구조와 제약조건을 정의한 것최상단 첫 행이라 생각하자 ㅇ튜플(tuple): db내의 주어진 목록과 관계있는 속성값의 모음한 행이라 생각하자 ㅇ속성: 개체 고유의 특성 (db를 구성하는 가장 작은 논리적 단위)한 열이라 생각하자 ㅇ인스턴스(instance): 튜플들의 집합행들의 집합이라 생각하자 ㅇ도메인(domain): 하나의 속성값 집합 ㅇ차수(Degree): 속성의 전체 개수 ㅇ카.. 2024. 5. 3.
[데이터베이스] ep0) 파일시스템 vs 데이터베이스 데이터베이스 등장 이전에는 보통 파일시스템을 이용하여 데이터를 관리하였다ㅇ파일시스템(File System): 컴퓨터에서 파일이나 자료를 쉽게 발견 및 접근할 수 있도록 보관 또는 조직하는 체제(운영체제에서 보통 한 챕터로 다룬다, 예전에는 학부 수업으로도 개설되어 있었다) 하지만 이런 파일시스템에는 문제가 두 가지 존재했다1. 데이터 종속성 2. 데이터 중복성  따라서 파일시스템의 단점들을 해결하고자 나온 것이 바로 데이터베이스(db)이다ㅇ데이터베이스(DB): 여러 사람에 의해 공유되어 사용될 목적으로 통합하여 관리되는 데이터의 집합데이터를 보다 효율적으로 처리하기 위하여 개발된 것으로 같은 데이터가 중복되는 문제를 없앨 수 있으며, 업무가 확대되어도 새로 파일을 준비할 필요가 없다는 장점이 있다ㅇDBM.. 2024. 5. 3.
[자료구조] 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.

티스토리툴바