본문 바로가기

Computer Science62

[자료구조] 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.
[자료구조] ep3-1) 단일연결리스트(Single Linked List) ㅁ리스트 ADT: 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조응용 예: 스택, 큐, 집합 / 소규모 db(주소록 등) or 더 복잡한 데이터구조 재료 ※노드(node): 커다란 자료구조의 일부분 하나 하나를 의미e.g. 리스트의 노드, 트리의 노드  리스트는 배열과 쓰임새가 비슷해 보통 많이들 비교한다    ㅇ단일연결리스트: 노드 간의 링크가 하나     활용) 다항식을 표현하는 연결리스트한 개의 다항식(polynomial)을 한 개의 헤더 단일연결리스트로 표현하는 방식(연결리스트의 각 노드는 차수의 내림차순으로 유지하고, 계수가 0인 항의 노드는 유지하지 않음) 여기서 다항식의 덧셈을 구하는 프로그램을 만들자   (전체 코드)#include #include #pragma warning (.. 2024. 5. 3.
[운영체제] ep3) 스레드(thread) [컴퓨터 구조] ep5) 스레드 파트를 복습하자스레드: 실행의 단위- 하드웨어적 스레드: 하나의 코어가 동시에 처리하는 명령어 단위- 소프트웨어적 스레드: 하나의 프로그램에서 독립적으로 실행되는 단위 https://claremont.tistory.com/entry/%EC%BB%B4%ED%93%A8%ED%84%B0-%EA%B5%AC%EC%A1%B0-ep5-CPU-%EC%84%B1%EB%8A%A5-%ED%96%A5%EC%83%81-%EA%B8%B0%EB%B2%95 [컴퓨터 구조] ep5) CPU 성능 향상 기법세계 곳곳의 과학자들과 엔지니어들은 조금이라도 더 빠른 CPU를 만들기 위해 혈색이다 이번 장에서는 CPU 설계 기법과 명령어 처리 기법들에 대해 알아보겠다 ㅇ클럭 "컴퓨터 부품들은 클럭이라clarem.. 2024. 4. 8.
[운영체제] ep2) 프로세스(process) ㅁ프로세스(process): 실행 중인 프로그램 (실행/스케줄링의 단위 및 자료구조)보조기억장치에 저장된 프로그램을 메모리에 적재하고 실행하는 순간, 그 프로그램은 프로세스가 된다그리고 이 과정을 "프로세스를 생성한다"라 표현한다   + 프로세스를 직접 확인하는 방법- Windows: 작업 관리자 프로세스 탭 - UNIX체계: ps 명령어   포그라운드(foreground) 프로세스: 사용자가 볼 수 있는 앞 공간에서 실행되는 프로세스vs백그라운드(background) 프로세스: 사용자가 보지 못하는 뒷 공간에서 실행되는 프로세스이 백그라운드 프로세스 중에서 사용자와 상호작용하지 않고 혼자 묵묵히 일을 수행하는 프로세스들을 Windows에서는 서비스(service)라 하고 UNIX체계에서는 데몬(daem.. 2024. 4. 8.
[자료구조] ep2+) 하노이 탑 구현 하노이 탑이란? B 기둥을 이용해서 A 기둥에 놓인 크기가 다른 원판을 C 기둥으로 옮기는 문제이다. 이때 원판은 한 번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다.+ 이동횟수 공식은 (2^n - 1) 회이다 e.g. n = 1인 경우 1회의 이동, n = 2인 경우 3회의 이동, n = 3인 경우, 7회의 이동       문제)원반의 개수 N을 입력받아, 하노이 탑 문제의 수행과정을 출력하는 프로그램을 작성해라     의사코드)n: 이동해야 할 원반 수from: 출발 기둥aux: 보조 기둥to: 목표 기둥  모식도)  //A에 1~N 쌓여있음 A     B     C 1 2 . . N //N-1개를 A에서 C를 거쳐 B로 이동 A     B     C N     1     .. 2024. 4. 7.
[자료구조] ep2) 재귀(Recursion) ㅇ재귀(recursion): 종료조건을 만족하기 전까지 자기 자신을 계속해서 호출→ 종료조건을 잘 설정해야 한다진행 방향: 종료조건을 향하여 진행작동 원리: stack을 생각하자 (LIFO, 후입선출)   이 작동원리에 대한 마인드셋이 너무 너무 중요하다예를 들어 재귀함수는 3건의 요청이 들어온다 하면 한 함수가 3건의 요청을 처리하는 것이 아닌, 각각 3개의 함수가 1건의 요청을 처리하는 것이다 (재귀함수를 이해하기 위한 최고의 그림이자 예시이다, 세종대 컴공 교수님들 최고!)          참고 및 출처: 실전 C프로그래밍(나중채, 한동일 등), 데이터 구조 원리와 응용(국형준), C언어로 쉽게 풀어 쓴 자료구조(천인국) 2024. 4. 7.

티스토리툴바