본문 바로가기

Computer Science112

[자료구조] 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.
[자료구조] ep1+) 비트행렬로 배우는 시간복잡도의 중요성 그림과 같은 비트행렬 A가 있다고 하자, 1을 카운트하는 방법에는 다양한 방법들이 존재한다여기서 나는 2가지 방법을 얘기하려 한다 1. 가장 일반적인 방법으로 이중포문을 이용해 각 행마다 0이 나올 때까지 카운트를 하는 방법: O(n^2) 2. 제일 하단 좌측에서 시작해 우측 상단을 향해 지그재그 방식으로 올라오며 카운트를 하는 방법: O(n) 1번 방식은 시간복잡도가 O(n^2)이므로 n값이 커질수록 실행 시간은 제곱수로 증폭하게 된다반면에, 2번 방식은 시간복잡도가 O(n)이므로 n값이 커질 수록 실행 시간은 그저 선형적으로 증가하게 된다따라서 우리는 실행 시간의 측면에서 2번 방식이 압도적으로 더 좋은 것을 알 수가 있다그렇기에 우리는 상황에 맞는 자료구조와 알고리즘을 설계할 수 있는 능력을 길러야.. 2024. 4. 7.
[자료구조] ep1) 자료구조 기본 지식들 ㅇ다차원 배열- 3차원 배열 - 4차원 배열   ㅇ빅오(Big O) 표기법: 연산의 횟수를 대략적(점근적)으로 표기"최악의 case 실행시간을 고려한다" [예시](1) 7n-2: O(n)(2) 3n^3 + 20n^2 + 5: O(n^3)(3) 3log(n) + log(log(n)): O(log(n))(4-1) n까지의 반복문: O(n)(4-2) n까지의 이중반복문: O(n^2)(4-3) n까지의 삼중반복문: O(n^3)(5) 조건문에서의 실행시간은 최악의 case로 합산한다+ O(log*n)은 중첩 log(n)을 의미   함수 증가율의 상한을 표시!※ 빅오메가, 빅세타 표기법과 공간복잡도는 생략   ㅇ의사코드 or 수도코드(pseudo-code): 컴퓨터가 아닌 인간에게 읽히기 위해 알고리즘을 간략하게 .. 2024. 4. 7.
[컴퓨터 구조] 후기 컴퓨터 구조에 대한 복습 및 정리를 끝마치게 되었다회사 프리랜서일과 병행하느라 조금 디뎠지만, 그래도 이전에 한 번 깊숙이 배웠던 내용인지라 빠르게 진행할 수가 있었다세종대 전자정보통신공학과에는 스파르타라는 별명을 가지신  SoC 권위자 이성주교수님이 계신다 (지금은 반도체시스템공학과에 가신 걸로 알고 있습니다) 그 교수님의 컴퓨터구조론 강의평을 보면 컴퓨터 구조에 대해 아주 깊고 빠삭하게 배울 수 있지만 체감상 6~9학점에 스파르타식으로 너무 너무 힘들다는 강의평들이 여럿 적혀있다솔직히 보고 좀 겁이 났지만 컴퓨터 구조가 CS에 있어서 근간이 되는 중요한 과목이라 생각하여 수강신청 때 1순위로 신청을 하였다 솔직히 이제 와서 생각해 보면 수강하는 동안에는 많이 힘들었다 컴퓨터시스템구조론(William .. 2024. 3. 5.
[운영체제] ep1) 운영체제의 큰 그림 운영체제(Operating System): 실행할 프로그램에 자원을 할당하고, 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램(컴퓨터에서 가장 중요한 프로그램이다)여기서 자원이란 시스템 자원으로써 프로그램 실행에 마땅히 필요한 요소들을 말한다 e.g. CPU, 메모리, 보조기억장치, I/O, 패킷, 파일 등 운영체제를 잘 알려면 커널의 개념을 확실하게 알고 가야 한다ㅇ커널(kernel): 운영체제의 핵심 서비스를 담당하는 부분메모리에는 커널 영역과 사용자 영역으로 나뉘어져 있으며, OS는 커널 영역에 적재되어 자원 할당과 프로그램 실행에 도움을 준다 앞으로 운영체제를 지칭할 때는 특별한 언급이 없는 이상 커널을 지칭한다고 생각하면 된다    대부분의 운영체제 서비스는 커널에 있지만 커널에 포함되지 않.. 2024. 3. 3.

티스토리툴바