컴퓨터공학개론 CS[1] - 김용담 강사 (패스트캠퍼스, Upstage AI Lab 6기)

중학생 때부터 혼자 컴퓨터를 조립하던 오타쿠로써 컴퓨터공학수업은 기대됐다.

 

컴퓨터공학은 CSE(Computer Science and Engineering) 혹은 CS라고 하는 것 같다.

내용은 생각보다 어려웠지만 흥미로워 기억에 남는다.

 

---

CSE란?

계산, 자동화 및 정보를 연구하는 학문.

컴퓨터 과학은 알고리즘, 계산 이론, 정보 이론, 자동화 등 이론적 분야부터 하드웨어 및 소프트웨어 설계회 구현 등의 실용적인 분야까지 포괄한다.

 

• Baic Concepts of Programming Language
• Data Structure and Algorithms → 코딩 테스트!
• Computer Architecture → 컴퓨터의 하드웨어와 시스템 대한 과목.
• Operating System → Windows, macOS, Linux, …
• Computer Network → Ethernet, Wi-Fi
• Database System → 데이터를 관리하는 시스템에 대한 과목.
• Software Engineering → 개발 방법론

 

---

Computational Thinking

 

예시를 가지고 각 방법론을 이해해보자

1. Decomposition : 전체 문제를 작은 여러가지 문제로 나누는 과정.
2. Pattern Recognition : 주어진 문제의 반복적으로 나타나는 패턴을 찾는 과정. 
3. Abstraction : 문제에서 해결해야할 주요한 정보를 수치화(또는 계산 가능하게)하는 과정.
4. Algorithmic Thinking : 문제 해결 방식을 step-by-step으로 만드는 과정.

---

 

Introduction to Data Structures

데이터 스트럭처란?

• Data Structures는 데이터를 구성, 저장, 조작하는 방법을 의미함 → 데이터 관리의 효율성 중에서도 ‘구조’에 대한 내용
• 데이터의 특성에 맞춰 효율적 액세스 및 수정이 가능하도록 함.
• 대표적으로 Array(배열), List, Stack, Queue, Tree, Graph 가 포함됨. → 데이터를 효과적으로 표현하기 위해 만들어진 새로운 구조들. → 이런 구조들은 어떻게 만들어질까?

 

Abstract Data Type(ADT)

• Abstraction
  • 복잡한 데이터나 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것.
  • 실제 데이터의 형태를 그대로 다루는 것이 아니라 데이터가 가져야하는 명세(specification)를 기반으로 만듬.
  • 특성을 나타내는 변수, 필요한 연산 등이 포함됨.
  • 주어진 개념이 파이썬이 정의해 놓은 데이터타입과 부합하지 않는다면, 새로운 데이터 타입으로 정의할 수 있다.
• ADT는 프로그래밍을 함에 있어 데이터를 추상화하여 논리적인 구조를 정의한 것
• 데이터의 특성과 필요한 연산에 맞게 구조를 추상화 → 이렇게 필요한 데이터의 구조를 따로 정의해서 만들게 되면, 코드에서 데이터를 다루기 편해진다. e.g. Python Class, C Struct
• ADT를 사용하면 좋은 점을 아래와 같이 정리할 수 있다.
  1. 데이터에 대한 정보를 이해하고 저장하는 방식을 결정함으로써 최적의 알고리즘을 개발할 수 있음
  2. 프로그래밍을 효율적으로 구현할 수 있도록 도와줌

Time and space complexity

자료구조가 데이터를 효율적으로 처리할 수 있도록 도와준다는 것을 배웠는데 그렇다면 얼마나 효율적인지를 어떻게 평가할 수 있을까?

• Space Complexity
  • 고정 공간 요구량(Fixed space requirements): 자료구조가 사용하는 고정된 메모리 공간을 의미. 고정된 크기를 갖는 변수(int, double)가 여기에 포함되며 크기가 정해진 배열의 경우에도 고정 공간 요구량에 속한다. 
  • 가변 공간 요구량(Variable space requirements): 필요에 따라 동적으로 할당, 해제되는 메모리 공간을 의미. 특정 instance에 따라서 size가 달라지는 변수들이 여기에 속한다. 
  • Space Complexity는 고정공간 요구량과 가변공간 요구량을 더해 계산한다.
• Time Complexity
  • Time Complexity는 Compile Time과 Excution Time으로 나뉘는데, 우리는 Execution Time의 complexity만을 계산한다.
  • Excution Time이란, 코드만 딱 보고 계산할 수 있는 실행시간에 관련된 연산을 의미
  • Execution Time에서 for문과 같이 반복이 일어나는 부분에서 Time Complexity가 증가하게 된다.

 

---

 

Stacks and Queues

Stack

• Stack(스택)은 LIFO(Last-In First-Out) 구조를 가진 자료구조이다.
• 구조는 List와 비슷하나 기능적인 면에서 차이가 있다.
• Stack은 삽입과 삭제가 항상 제일 뒤(최근) 요소에서 이루어진다. 그리고 가장 최근에 삽입한 요소를 top이라고 지칭한다.
• 함수가 호출되면서 다시 복귀할 주소를 저장하거나, 지역변수, 매개변수 등을 임시로 저장하는데에 쓰인다. (검색 추천!)
• stack의 구현은 Array나 List 모두 가능하다.
  • 파이썬에서는 List를 통해 구현
• Basic operations (push, pop, is_full, is_empty)
  • Stack에 대한 기본적인 기능에는 push, pop, top, isFull(배열로 구현된 경우), isEmpty 가 있다.
  • push: stack의 가장 뒤에 요소를 삽입
  • pop: stack의 가장 뒤 요소를 제거 후 return.
  • top: stack의 가장 뒤 요소를 지칭하며 삭제 없이 접근하기 위해서 사용. 파이썬에서는 리스트 인덱스를 통해 접근

 

Queue

• Queue는 FIFO(First-In, First-Out) 구조를 가진 자료구조이다.
• 놀이공원이나 은행의 대기줄처럼 먼저 들어온 요소를 먼저 내보낸다.
• queue에서는 front와 rear로 가장 먼저 들어온 요소와 제일 마지막에 들어온 요소에 접근한다.
• Basic operations (enqueue, dequeue, is_full, is_empty)
  • Enqueue: queue에 원소를 삽입
  • Dequeue: queue에서 원소를 삭제

---

Linked List and Hash Table

인덱싱을 많이 한다 = array

인서트, 딜리트를 많이 한다 = linked list

 

Array

• 연속된 메모리 공간에 같은 타입의 데이터를 순차적으로 저장하는 자료구조
• 인덱스를 통해 빠르게 접근할 수 있음
• 크기가 고정되어 있기 때문에 배열을 생성할 때 크기를 지정해줘야함
  • 배열이 가득 차는 경우 새로운 데이터를 추가할 수 없거나 기존 데이터를 삭제해야 할 수 있음.
• Python에서는 numpy array에서 소개됨

 

Linked List

• array와 다르게 생성 후에 자유롭게 원소를 추가/삭제할 수 있는 자료구조이다.
• 가변적인 길이를 가지고 있기 때문에, 새로운 데이터 추가에 대한 제한이 거의 없다는 장점이 있다.
• 기본적으로는 하나의 요소에 그 다음 요소가 연결되어 있는 단순 연결리스트의 형태로 구현되고 경우에 따라 원형 연결 리스트, 이중 연결 리스트 등으로 나타내기도 한다.

Hash Table

• 데이터의 key를 hash function을 통해 hash value으로 변환하고, 이 값을 인덱스로 사용하여 데이터를 저장하거나 검색하는 효율적인 자료 구조이다.
• 평균적으로 $O(1)$의 시간 복잡도로 데이터에 접근할 수 있다.
• Python의 dict가 hash table로 구현되어 있다.
• Hash function을 통해 저장할 곳을 구분하므로, 어떤 함수를 쓰느냐에 따라 성능 차이가 난다.
• Hash table의 사용 목적은 정해진 메모리에 여러 원소를 효율적으로 저장하여 indexing 성능을 O(1)에 가깝게 만드는 것에 있다.

---

Trees and Graphs

Tree

• 데이터 속 항목을 계층적으로 구조화하는 자료구조이다.
• Tree와 관련된 용어 설명
  • Node : 트리 구조의 교점으로 Node는 데이터(value)를 가지고 있고, 자식노드를 가지고 있습니다.
  • Root Node: 트리구조에서 가장 위에 있는 노드. 즉 시작점이 되는 노드입니다.
  • edge(link): 트리를 구성하기 위해 노드와 노드를 연결하는 선 입니다.
  • level : 트리의 특정 깊이를 가지는 노드의 집합 입니다. Depth
  • degree: 각 노드가 지닌 하위 레벨의 가지의 수를 말하며 '차수'라고도 합니다. (child node의 개수)
  • Leaf node(Terminal Node): 하위에 다른 노드가 연결되어 있지 않은 노드
  • Internal Node : Leaf노드를 제외한 중간에 위치한 노드들을 말합니다.
  • Depth(=height) : 트리에 가장 큰 Level의 숫자
  • Parent Node : 나보다 상위 노드, 트리 구조에서는 하나 밖에 없음
  • Child Node : Parent Node에 직접적으로 연결되어 있는 하위 노트
  • Sibilings : 같은 Parent Node를 둔 같은 Level의 노드

Type of Trees

• Binary Tree
  • 자식 Node가 최대 둘 뿐인 Tree.
  • Decision Tree 중에 현재 많이 사용되는 **CART(Classification and Regression Tree)**도 대표적인 Binary Tree이다.
  • 비슷한 Tree로는 자식 node가 최대 세 개인 Ternary Tree가 있다.
  • Child Node의 개수가 0, 1, 2인 Tree = Binary tree
• Balanced Tree
  • 위의 Binary Tree의 경우 한쪽으로 편향된 구조를 가질 수 있다는 단점이 있다.
  • 이런 구조는 배열과 같은 선형구조이기 때문에 Leaf Node 탐색시 효율이 떨어짐.
  • 이를 보완하기 위해서 Balanced Tree 구조를 사용한다.
  • 그 예로는 B-tree, B+ tree 등이 있다. → 검색용 Tree들(index)은 다 검색 효율성을 위해 balanced tree로 정의한다.
  • 이러한 Balanced Tree는 어느 한쪽으로 데이터가 치우치지 않도록 균형을 지킬 수 있는 규칙을 가지고 있다는 특징이 있다.
• 이외에도 완전 이진 트리, Full Binary Tree, Complete binary Tree 등이 있다.

Graph

• 그래프는 관계를 모델링하기 위한 자료구조
• e.g. Social Network, Protein Structure , Chemical components, …
• 트리도 일종의 그래프 중 하나에 속함
• Graph 용어 설명 G = {V, E}
  • Vertex(=Node): Tree에서의 Node와 같은 개념
  • Edge(=Link): 정점과 정점을 있는 선
  • weight : edge의 가중치값
  • degree: Vertex에 연결되어 있는 Edge 수
    • out-degree: 방향이 있는 그래프에서 정점에서부터 출발하는 간선의 수
    • in-degree: 방향이 있는 그래프에서 정점으로 들어오는 간선의 수
  • Path: $V_i$에서 $V_j$까지 간선으로 연결된 정점을 순서대로 나열한 리스트 e.g. A → E = {A, B, D, E}
  • Path Length: 경로를 구성하는 간선의 수
  • Cycle: 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 e.g. A → A = {A, B, D, A}
• Graph 유형 설명
  • undirected graph: 두 정점을 연결하는 간선에 방향이 없는 그래프. 가장 기본적.
  • directed graph : 간선에 방향이 있어 정해진 방향으로만 이동할 수 있는 그래프
  • weighted graph : 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프
    e.g. 통과 가능한 금액, 강도 등으로 표현 가능

---

Basic Algorithm Design

Algorithms

• Algorithm은 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것.
• 알고리즘은 입력, 출력, 명확성, 유한성, 효율성의 조건을 만족해야한다.
• 자연어, pseudo-code(실제 코드처럼 문법적으로 완벽하지는 않지만, 로직 상 무슨 말인지 알 수 있는), 순서도, 프로그래밍언어 등으로 표현할 수 있음.
• 좋은 알고리즘이란? 효율성을 고려한 알고리즘
  • 공간복잡도와 시간복잡도를 고려해 알고리즘을 짜야 함. “efficiency”
• Recursion and iterative approaches
  • 알고리즘의 구현을 위해서 자주 사용하는 접근 방식 두가지가 iteration & recursion이다.
  • 재귀 방식은 함수내에서 파라미터를 바꿔 새로운 자기 자신을 호출하는 방식이다. → Fibonacci Number

• 재귀 방식을 이용하는 경우 반복 방식보다 코드가 간결하고 가독성이 좋아 문제를 쉽게 이해할 수 있다는 장점이 있다.
• 하지만 그 과정에서 계속적인 함수 호출은 스택에 함수 호출과 복귀 위치 등의 정보를 계속해서 추가하기 때문에 스택 오버플로우 문제가 발생할 수 있고, 시스템에 부담을 주기도 한다.
• 이미 우리가 익숙한 방식은 반복을 적용한 알고리즘인데, for문, while문과 같은 loop 반복문을 통해서 문제를 해결한다.
  • 이 경우 스택 오버플로우 문제가 없고, 시스템적 부담이 적다는 장점이 있지만 코드가 복잡해진다는 단점이 있다.
• 뒤에 search algorithm에서 서로 다른 방식을 이용해 구현된 탐색을 살펴보자.

Sorting algorithms

• 리스트에 대한 정렬 알고리즘을 살펴보자.
• 정렬 알고리즘은 주어진 데이터를 정해진 순서대로 재배열하는 알고리즘이다. (ascending, descending)
  → 데이터 간의 비교가 가능해야 함!
  → 비교를 하려면 기준이 있어야 함.
  → 기준을 정하려면 계산 방법이 있어야 함.

• Bubble Sort
  • Time Complexity : O(N^2)
  • 인접한 두 원소를 비교하면서 큰 값을 뒤로 보내며 정렬이 이루어짐. (오름차순 기준)
  • 가장 큰 값을 가장 마지막으로 보내는 것이 한번의 step으로 보고, 한번의 step이 끝나면 뒤에서부터 정렬되는 것을 볼 수 있음.
• Selection Sort(선택정렬)
  • 리스트에서 최솟값을 찾아 맨 앞의 요소와 위치를 바꾼다.
  • 이후 두번째 위치의 요소에서부터 마지막 위치의 요소까지 최솟값을 찾아 위치를 바꾼다.
  • 정렬을 진행하면서 앞에서부터 차례로 정렬이 되고, index 0는 1~n, index 1은 2~n까지를 반복하며 최솟값을 찾고 위치를 바꾸는 것을 반복하므로 시간 복잡도는 O(N^2)의 시간복잡도를 가진다.
  • 입력 배열이 이미 정렬되어 있건 말건 관계없이 동일한 연산량을 가지고 있기 때문에 최적화 여자가 적어서 다른 O(N^2) 정렬 알고리즘과 비교해봤을 때도 성능이 떨어지는 편임
• Insertion Sorting(삽입 정렬)
  • 리스트의 요소를 하나씩 가져와서 이미 정렬된 앞 부분과 비교하여 적절한 위치에 삽입함.
  • k번째 요소를 1부터 k-1까지 비교해 적절한 위치에 넣고, 원래 k번째 요소의 자리에는 해당 위치에 있던 요소를 넣는다.
  • 시간복잡도는 O(N^2)이며 작은 값들이 뒤쪽에 몰려있으면 최악의 경우라고 볼 수 있고, 사이즈가 작을 경우 매우 효율적이라 고성능 정렬 알고리즘들도 사이즈가 작을 경우 삽입 정렬보다 오래 걸릴 수 있다.
• (Advanced) Quick Sort(퀵 정렬)
  • 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬하는 정렬 알고리즘.
    • 분할정복이란? 복잡한 전체의 문제를 부분으로 나누어, 부분적인 문제를 해결하고 다시 합쳐 전체를 해결하는 방식을 의미.
  • 특정한 값을 기준으로 리스트를 두 개로 분할하고, 각각을 정렬한 뒤 다시 합치는 방식으로 동작.
  • 이 과정에서 분할된 리스트의 크기가 작아질수록 더 빠른 속도를 보이는 효율적인 알고리즘.
    1. 리스트 안에 있는 한 요소(피벗, pivot)을 선택
    2. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눔.
    3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬
    4. 분할된 리스트들을 하나의 리스트로 합침.일반적인 구현 알고리즘
       → 이를 재귀적으로 반복하면 정렬된 리스트를 얻을 수 있음.

Searching  algorithms

• Linear Search (순차 탐색, 전탐색)
  • full scan을 하고 찾는 것
  • 처음부터 끝까지 순서대로 모든 데이터를 탐색하는 방법.
  • 리스트, 배열 등 선형 구조에서 데이터를 검색할 때 사용됨
  • for문을 이용해서 앞에서부터 원하는 값을 찾기 때문에, O(n)의 시간복잡도를 가짐.
• Binary Search (이진 탐색)
  • 정렬된 데이터에서 특정 값을 찾을 때 사용하는 탐색 방법.→ 정렬하는데 O(NlogN) 시간을 지불하고 사용 가능!-Linear Search : O(N)
  • Binary Search : O(NlogN) + m*O(logN)
  • → 정렬이 되어있지 않은 데이터에서 m번 검색할 떄 비용은 :
  • → 만약, 정렬이 안되어있는 데이터셋에서 Binary Search를 하려면?
  • 정렬된 데이터셋(이진 트리, 배열)에서 중간값을 찾아서 검색 대상을 반으로 줄여가며 탐색을 진행. (search space가 줄어든다)
  • O(logN)의 시간복잡도를 가지며 이미 정렬이 되어 있는 데이터셋에서는 큰 효율성을 가진다.
• Tree Search
  • Tree를 이용해 데이터를 탐색하는 방식
  • 데이터를 Tree로 표현한 뒤에 Tree에서 원하는 원소를 탐색하는 방식
  • → from Root to Leaf (=certain node)
  • Tree를 만드는데 추가로 시간이 들지만($O(N^2)$), 그 이후에 탐색 시간이 $O(log_2N)$으로 줄어들게 되는 이득이 있다.
  • Update→ Rebuild(새로 다시 만듦)
  • → Insert and Adjust 삽입 및 재구조화 (incremental building)
• DFS(Depth-First Search) : Graph Search 방법 (from Vertex i to Vertex j)
• depth를 먼저보고 탐색하는 방식. tree level이 계속 증가하는 방향으로 탐색을 하다가, 더 이상 child node가 없을 때 다시 parent node로 올라와서 다른 child node들을 순차적으로 탐색함.
• BFS(Best-First Search) DFS와 다르게 같은 level의 다른 child node들을 먼저 탐색하는 방식. 같은 level의 모든 node를 탐색하면 가장 왼쪽 끝에 있는 다음 level의 노드부터 순차적으로 탐색함.