GUI(Graphical User Interface)

• 유저가 직접 정보를 볼 수 있는 화면
• 유저와 상호작용 하는 방식. 개발을 모르더라도 사용 가능하도록 함. ex) button, text fields, menus, windows

Java Swing

• GUI를 위해 미리 정의해놓은 class들의 모음
• Platform Independent : 특정 OS에 국한되지 않음
• Rich and Customizable Component : 대부분의 component와 기능 제공 + 개발자가 커스텀 가능

Key Concept of Swing

• Component-Based Model
  • 다양한 Component 조합해서 화면 구성
  • container ⊃ butten, text field
• Event-Driven Model
  • Event 를 통해 유저와 상호작용 함 ex) button 클릭 / text 입력
  • Component 가 이벤트를 생성하면 event listener 가 들음.
• Hierarchical Organization
  • Component 들은 위계 질서를 가지고 정렬되어 있음
  • 복잡하게 구성된 유저 인터페이스 생성 가능.

2. Components & Containers

Containers

• Component를 가지고 구성하는 도화지.

• GUI 레이아웃을 구성할 때 필수적

  Top level

  • JFrame : main 창. 이 아래 panel(⊃ component) 배치
  • JDialog : 팝업창. 경고, 알림용
  • JApplet : 보안 이슈로 잘 사용하지 않음

  Intermidiate level → 공간 구분 시 사용

  • JPanel : component끼리 모아두는 곳
    • layout manager 통해 요소 정렬

• Container 내부에 또 다른 Container 넣을 수 있음.

Basic Components

• GUI 를 만들 때 기본 클래스
• 모든 Component는 java.swing.JComponent 클래스를 상속 받음
  • 기본 값 : size, position, color
  • 기본 행동 : responsing user input
• 한계
  • Lack of Sophistication : 복잡한 구조를 만들기엔 부족함.
  • Limited Customization : 실시간 업데이트가 안됨. 한 번 만든 후에는 변화 불가

종류

• JButton : 클릭될 수 있는 버튼
• JLabel : 텍스트나 이미지를 보여줌 (이후 수정 불가)
• JTextField : 한 줄짜리 유저가 입력 가능한 입력 공간
• JPasswordField : 입력한 값이 보이지 않는 입력 공간

3. Advanced Components

JTree

• 계층적인 데이터 구조를 나타낼 때 사용
• node는 확장하거나 나눠질 수 있음

import javax.swing.JFrame;
import javax.swing.*;
import javax.swing.tree.DefaultMutableTreeNode;

public class BasicJTreeExample extends JFrame {
    public BasicJTreeExample() {
        setTitle("Basic JTree Example");
        setSize(300, 300);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create a root node
        DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");

        // Ad first level child nodes
        DefaultMutableTreeNode child1 = new DefaultMutableTreeNode("Child 1");
        DefaultMutableTreeNode child2 = new DefaultMutableTreeNode("Child 2");

        // Add second level child nodes to child 1
        DefaultMutableTreeNode grandChild1 = new DefaultMutableTreeNode("grandChild 1");
        DefaultMutableTreeNode grandChild2 = new DefaultMutableTreeNode("grandChild 2");

        child1.add(grandChild1);
        child1.add(grandChild2);

        // Construct the tree structure
        root.add(child1);
        root.add(child2);

        // Create a JTree
        JTree tree = new JTree(root);

        // Add the tree to the frame
        JScrollPane TreeView = new JScrollPane(tree);
        add(TreeView);

        setVisible(true);
    }

    public static void main(String[] args) {
        new BasicJTreeExample();
    }
}

• JScrollPane 에서만 사용 가능
  • 기본 Panel은 사이즈가 고정. 그렇지만 Tree는 얼마나 길지 모르므로 ScrollPane 사용.
  • JTree ⊂ JScrollPane ⊂ JPanel 가능

JTable

• 표 형식의 데이터 구조를 나타낼 때 사용
• 열 정렬, cell 수정, custom cell rendering 지원

  import javax.swing.*;
  import javax.swing.table.DefaultTableModel;
  

public class BasicJTableExample extends JFrame { public BasicJTableExample() { setTitle("Basic JTable Example"); setSize(400, 300); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    // Define column names for the table
    String[] columnNames = {"ID", "Name", "Age", "Occupation"};

    // Define data for the table (2D array)
    Object[][] data = {
            {1, "Alice", 30, "Engineer"},
            {2, "Bob", 25, "Designer"},
            {3, "Charlie", 35, "Teacher"},
            {4, "Dave", 28, "Developer"}
    };

    // Create table model with the specified data and column names
    DefaultTableModel model = new DefaultTableModel(data, columnNames);

    // Create JTable with the model
    JTable table = new JTable(model);

    // Add the table to a scroll pane
    JScrollPane scrollPane = new JScrollPane(table);
    add(scrollPane);

    setVisible(true);
}

public static void main(String[] args) {
    new BasicJTableExample();
}

}

![](https://velog.velcdn.com/images/yeonbo_ra/post/e47b0ef5-02f5-4d8a-9f61-dcad335934ee/image.png)
- `JTree`와 마찬가지로 `JScrollPane`에서만 사용 가능

### JTappedPane
- 여러 탭의 인터페이스를 가능하게 함. 여러 패널 & 섹션이 한 화면에 나올 수 있음
- `JTappedPane` 안에 `Panel` 넣기
```java
import javax.swing.*;

public class BasicJTabbedPaneExample extends JFrame {
    public BasicJTabbedPaneExample() {
        setTitle("Basic JTabbedPane Example");
        setSize(400, 300);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create JTabbedPane
        JTabbedPane tabbedPane = new JTabbedPane();

        // Create panels for each tab
        JPanel panel1 = new JPanel();
        panel1.add(new JLabel("This is the first tab."));

        JPanel panel2 = new JPanel();
        panel2.add(new JLabel("This is the second tab."));

        JPanel panel3 = new JPanel();
        panel3.add(new JLabel("This is the third tab."));

        // Add panels to JTabbedPane with titles
        tabbedPane.addTab("Tab 1", panel1);
        tabbedPane.addTab("Tab 2", panel2);
        tabbedPane.addTab("Tab 3", panel3);

        // Add the tabbed pane to the frame
        add(tabbedPane);

        setVisible(true);
    }

    public static void main(String[] args) {
        new BasicJTabbedPaneExample();
    }
}

JSplitPane

• 컨테이너를 두 개의 크기 재지정 가능한 패널로 나눔. 유저가 드래그해 사이즈 조절 가능
• JTappedPane 안에 어떻게 나눌건지 넣고, 각각 위치할 Panel 넣기

  import javax.swing.*;
  

public class BasicJSplitPaneExample extends JFrame { public BasicJSplitPaneExample() { setTitle("Basic JSplitPane Example"); setSize(400, 300); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    // Create two panels to split
    JPanel leftPanel = new JPanel();
    leftPanel.add(new JLabel("This is the left panel."));

    JPanel rightPanel = new JPanel();
    rightPanel.add(new JLabel("This is the right panel."));

    // Create JSplitPane with the two panels
    JSplitPane splitPane = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT, leftPanel, rightPanel);
    splitPane.setDividerLocation(150); // Initial divider position

    // Add the split pane to the frame
    add(splitPane);

    setVisible(true);
}

public static void main(String[] args) {
    new BasicJSplitPaneExample();
}

}

![](https://velog.velcdn.com/images/yeonbo_ra/post/19053b1c-a68f-4473-ac25-dd08bc4e70a4/image.png)

#### Extra
- `JSlider` : 유저가 슬라이더로 값을 조절할 수 있게 함 (ex. 볼륨 조절)
  - `slider = new JSlider(최소, 최대, 초기값);`
- `JSpinner` : 유저가 여러 값 중 선택할 수 있도록 함
  - `spinner = new JSpinner(new SpinnerNumberModel(초기값, 최소, 최대, 증가량));`
- `JProgressBar` : 작업률을 보여줌
  - `progressBar = new JProgressBar(초기값, 최대);`

![](https://velog.velcdn.com/images/yeonbo_ra/post/2e16e024-5706-4b09-80f5-d40a6386645e/image.png)

## 4. Layout Manager
- 기본적인 레이아웃들
- component들을 알아서 크기 조절 & 배치해줌

- `FlowLayout` 
  - component를 한 줄에 배치, 줄이 모두 차면 다음 줄로 넘김(반응형,
  - 간단한 왼 → 오른쪽 레이아웃
  ![](https://velog.velcdn.com/images/yeonbo_ra/post/d0cb1bcc-bd41-4c88-981b-6ef3aac6b784/image.png)

- `BorderLayout` 
  - component 들을 나눠진 다섯 영역으로 나눔
  - North, South, East, West, Center
``` java
JFrame frame = new JFrame("BorderLayout");
frame.setLayout(new BorderLayout());

frame.add(new JButton("North"), BorderLayout.NORTH);
frame.add(new JButton("South"), BorderLayout.SOUTH);
frame.add(new JButton("West"), BorderLayout.WEST);
frame.add(new JButton("East"), BorderLayout.EAST);
frame.add(new JButton("Center"), BorderLayout.CENTER);

frame.setSize(400, 300);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);

• GridLayout

  • 특정한 행과 열로 나뉜 그리드에 Component 배치
  • 각 칸마다의 크기가 같음

    frame.setLayout(new GridLayout(2, 2)); // 2 * 2 행렬

    

  5. Event Handling

  Event Handling

  • GUI component 들로 유저 상호작용을 관리하는 과정
    • 클릭, 키입력, 마우스 움직임 등

      Event Listener

    • component 에서 발생시킨 특정한 타입의 event를 듣는 interface
    • ActionListener : 버튼 클릭 같은 액선 이벤트를 들음
    • MouseListener : 마우스 클릭이나 움직임 같은 마우스 이벤트를 들음
    • KeyListener : 키 입력이나 떼기 같은 키보드 이벤트를 들음

  Process of Event Handling

  • Event Source : 이벤트를 만드는 Component

  • Event Listener

    • 특정한 이벤트를 듣는 인터페이스
    • Event Source와 붙어있음

  • Event Object : 이벤트의 타입, 소스에 대한 캡슐화 된 정보

  • Event Source가 이벤트를 생성하면 Event Listener 가 그것을 듣고 Event Object를 생성함.

1. Property of Algorithms

알고리즘 : 계산을 하거나, 문제를 풀기 위한 정확한 명령의 유한한 서열

• 프로그램은 알고리즘을 구현한다.

Properties

• Input : 특정한 집합으로부터의 입력값
• Output : 입력한 값에 대한 출력값
• Definiteness : 알고리즘의 단계는 명확히 정의되어야 함
• Correctness : 어떠한 입력값에 대해서도 항상 정답을 구해야 함
• Finiteness : 유한한 횟수의 단계를 거쳐 답을 도출해야 함
• Effectiveness : 정확하고 유한한 시간 내에 수행해야 함
• Generality : 조건을 만족하는 모든 입력에 대해 적용 가능해야 함
• Efficiency : 최소한의 시간 & 공간을 사용 해야 함

Pseudocode

• 의사 코드, 알고리즘을 표현하는 방법

procedure 이름(인자: 타입)

ex) procedure maximum(L: list of integers)

변수 := 표현

• 의사 코드에선 정형화 되지 않은 표현도 허용된다. v := 3x + 7 x := the largest integer in the list L swap x and y → 실제 프로그래밍 언어에선 사용 불가

begin statements end

if condition then statement → 프로그래밍 언어의 if

while condition statement → 프로그래밍 언어의 while

for var := initial to final statement → 프로그래밍 언어의 for

{comment} → 주석, 설명을 덧붙이기 위해 사용

• example

  procedure max($a_1, a_2, ...,a_n$ : intergers)     max := $a_1$      {largest element so far}     for i := 2 to n      {go thru rest of elems}         if max < $a_i$ then max := $a_i$      {found bigger?}     {이 지점에서 max는 list의 원소 중 가장 큰 정수와 같다}     return max {max is the largest element}

• example

  procedure sum($a_1, a_2, ...,a_n$ : intergers)      s := 0      {sum of elems so far}      for i := 1 to n      {go thru all elems}          s := s + a_i      {add current item}      {이 지점에서 s는 모든 list 안의 값의 합}     return s

2. Algorithms for Searching and Sorting

Search Algorithm

Linear Search

• 선형 탐색 : 차례대로 x를 다음 원소와 비교하며 일치하는지 확인하는 알고리즘

  procedure linear search(x : integer, $a_1, a_2, ..., a_n$: distinct integers)     i := 1     while (i ≤ n and x ≠ $a_i$)         i := i+1     if i ≤ n then location := i     else location := i     return location      {location is the subscript of the term that equal x, or is 0 if x is not found}

→ 시간 복잡도 : O(n)

Binary Search

• 이진 탐색 : 리스트 중간 원소 조사, 두 구간으로 나눠 어느 쪽에 있는지 판단하고 범위를 줄이는 알고리즘

  procedure binary search(x : integer, $a_1, a_2, ..., a_n$ : increasing integers)     i := 1     {i is left endpoint of search interval}     j := n     {j is right endpoint of search interval}     while i < j         m := $\lfloor(i+j)/2\rfloor$         if $x > a_m$ then i := m + 1         else j := m     if x = $a_i$ then location := i     else location := 0     return location     {location is the subscript of the term $a_i$ equal to x, or 0 if x is not found

→ 시간 복잡도 : O(log n)

Sort Algorithm

Bubble Sort

• 버블 정렬 : 인접한 원소를 차례대로 비교, 순서가 잘못되어 있으면 서로 교환해 정렬하는 알고리즘

  procedure bubble sort($a_1, ..., a_n$ : real numbers with n ≥ 2)     for i := 1 to n-1         for j := 1 to n-i

                **if** $a_j > a_{j+1}$ **then** interchange $a_j$ and $a_{j+1}$

  {$a_1, ..., a_n$ is in increasing order}

→ 시간 복잡도 : O(n²

Insertion Sort

• 삽입 정렬 : - 두 번째 원소 부터 시작, 첫 원소와 비교해 앞/뒤 정해, 점점 뒤로가고, 앞쪽에서 정렬이 되는 알고리즘

  procedure insertion sort($a_1, a_2,...,a_n$: real numbers with n ≥ 2)     for j := 2 to n         i := 1         while $a_j > a_i$

                i := i + 1

          m := $a_j$         for k := 0 to j - i - 1

                $a_{j-k} := a_{j-k-1}$

          $a_i$ := m {$a_1, ..., a_n$ is in increasing order}

→ 시간 복잡도 : O(n²

3. Greedy Algorithms

욕심쟁이 알고리즘(greedy algorithm) : 각 단계마다 가장 좋은 선택을 하는 알고리즘

• 계산원 알고리즘 : 동전으로 거스름돈을 주는 방법을 계산하는 알고리즘

  procedure change($c_1, c_2, ..., c_n$: values of denominations of coins, where $c_1 > c_2 > ... >c_r$, n : a positive integer     for i := 1 to r         $d_i$ := 0 {$d_i$ counts the coins of denomination $c_i$ used}         while n ≥ $c_i$

                $d_i$ := $d_i$ + 1 {andd a coin of denomination $c_i$ 
                n := n - $c_i$ 

  {$d_i$ is the number of coins of denomination $c_i$ in the change for i = 1, 2, …, r}

• greedy 알고리즘이 모든 알고리즘에 대한 답인 것은 아니다.

4. Halting Problem

• Halting Problem : 주어진 프로그램과 그 입력값에 대해 프고르갬이 유한한 시간 안에 종료될지, 아니면 무한 루프에 빠져 종료되지 않을지 판별하는 알고리즘은 존재하지 않는다.

1. 입력으로 프로그램 P와 그 프로그램의 입력값 I를 받는 절차 H(P, I)가 있다고 가정.
2. H는 프로그램 P가 입력 I로 실행되었을 때, P가 멈출지 멈추지 않을지 판정하는 절차.

→ 해결할 수 없다는 것 증명

1. 가정 : 만약 H(P, I)라는 절차가 존재한다고 가정

2. 만약 프로그램이 멈추면 "halt", 멈추지 않으면 "loops forever" 출력

3. 프로그램 K(P) 정의

   • 만약 H(P, P) 가 "loops forever" 출력할 시 K(P)는 멈춤.
   • 만약 H(P, P) 가 "halt" 출력할 시 K(P)는 무한 루프.

4. K(K)를 호출한다면

   • K(K)가 "loops forever" 라면 K(K)는 멈춘다 → 모순
   • K(K)가 "halt" 라면 K(K)는 무한 루프에 빠진다 → 모순

• 따라서, Halting 문제를 해결할 수 있는 일반적인 알고리즘은 존재하지 않는다.

##

1. Basic of Function

함수(function) : A, B가 집합일 때, A로부터 B로의 함수 f는 A의 원소 각각에 B의 원소를 단 하나만 대응 시킨 것이다.

• 함수에 대한 표현들
• 명제 : 상황이라는 정의역에서 {T, F}라는 공역으로 가는 함수
• bit String의 길이 : 숫자 {1, ..., n} 으로부터 bit {0,1}로 향하는 함수
• 집합 : 원소라는 정의역에서 존재하는지 여부인 {T, F}라는 공dur으로 가는 함수
• 집합 기호 : 집합으로부터 집합으로 가는 함수
  • ∩(({1,3},{3,4})) = {3}

Notations

• Y^X = f : X → Y 를 만족하는 모든 가능한 함수 F들의 집합

  • |F| = |Y|^|X|

• F ≡ 0, T ≡ 1, 2 ≡ {0, 1} = {F, T}

  f : A → B / f(a) = b (where a ∈ A & b ∈ B) A는 f의 정의역(domain) B는 f의 공역(codomain) B에서 f의 상(image)의 집합 치역(range) b는 f의 상(image) a는 f의 원상(pre-image)

• 상인 b는 일반적으로 1개 이상의 원상을 가진다

• 치역은 공역보다 작거나 같다

• 함수의 그래프 : f가 A→B인 함수일때, {(a, b) | a∈A 이고, f(a) = b, b∈B}인 순서쌍의 집합

  • 그림으로 표현할 수 있다.

Operator

• Operator : n개의 쌍에 대한 함수
  • Unary Operator : 인자가 1개 (ex. ~)
  • Binary Operator : 인자가 2개 (ex. ∪,∩)
• plus( + ) : 함수 합
  • (f + g)a = f(a) + g(a)
• times( × ) : 함수 곱
  • (f × g)a = f(a) × g(a)
• compose( $\circ$ ) : 함수 합성
  • (f $\circ$ g)a = f(g(a))
  • 교환 법칙이 성립하지 않는다.

2. Special Functions

One-to-One Function(1-1)

• 단사함수 : f의 정의역에 속한 모든 a와 b에 있어서 f(a) = f(b) 이면 반드시 a = b인 함수. (일대일 함수)
• 1개의 치역 원소에 1개의 정의역 원소만 대응
• Strictly increasing(단조 증가 함수) : 정의역 안의 임의의 원소 x, y가 x<y이면 반드시 f(x) < f(y)인 함수
• Strictly decreasing(단조 감소 함수) : 정의역 안의 임의의 원소 x, y가 x<y이면 반드시 f(x) > f(y)인 함수
  • f 가 단조 증가 or 단조 감소 함수이면 f는 단사 함수이다 (역은 성립 X)

Onto Function

• 전사 함수 : 공역과 치역이 같은 함수
• 전사 함수 & 단사 함수 일수 있고, 한쪽만 만족할 수도 있다.

Bijections

• 전단사함수 : 전사함수이면서 동시에 단사함수인 함수. (일대일 대응)
• f가 전단사함수일때, f의 역함수 f^-1 : B → A 가 정의될 수 있다.
  • f^-1 $\circ$ f = I(identity function)

Identity Function

• 항등 함수 : I : A → A, 입력과 출력이 같은 함수
• 항등함수는 전단사함수이다.

Floor & Ceiling Function

• Floor Function $\lfloor x \rfloor$ : 실수 x에 대해 x와 같거나 작은 수 중 가장 가까운 정수를 대응하는 함수.

• Ceiling Function $\lceil x \rceil$ : 실수 x에 대해 x와 같거나 큰 수중 가장 가까운 정수를 대응하는 함수.

• if $x ∈ Z$, $\lfloor x \rfloor$ = $\lceil x \rceil$ = $x$

• ex) $\lfloor {x\over3} \rfloor$

3. Cardinality & Infinite Sets

• Define Cardinality for infinite set

• Cardinality : 1개의 relation(관계)에 포함되어 있는 tuple의 수

  두 집합 A와 B가 동일한 Cardinality를 가진다.(|A| = |B|) $$\Longleftrightarrow$$ A 로부터 B로 향하는 전단사함수가 있다.

• 무한 집합일지라도 셀 수 있는 집합이 존재한다

  • 집합이 유한 or |S| = |N| 할 때
  • ex) N(자연수 집합), Z(정수 집합), 자연수의 순서쌍(n, m)

• 셀 수 없는 집합.

  • 집합이 무한 or |S| > |N|
  • ex) R(실수), C(복소수),
  • [0, 1) = {r ∈ R| 0 $\leq$ r $<$ 1|}

• Diagonalization 대각선 논법 : 실수의 집합은 셀 수 없다

• Transfinite Numbers

  • 무한집합 S가 셀 수 있을 경우 S의 크기를 $\aleph_0$ 라고 표기.
  • |N| = $\aleph_0$
    • 가장 작은 transfinite cardinal number(무한기수)
  • |R| = $\aleph_1$
    • second transfinite cardinal

1. Basic of sets

Set(집합) : 순서를 고려하지 않는 서로 다른 개체들의 모임

Basic Notation

• 집합을 가르킬 때 S, T, U와 같이 영어 대문자 사용.

• 집합 내부에 속한 원소들은 영어 소문자 사용

• 원소 나열법 : 중괄호 안에 모든 구성원을 나열하는 표기법

• 조건 제시법 : 모든 원소를 나열하는 것이 불가능할 경우 사용.

  • {x| x는 속성 P를 갖고 있다}와 같이 사용

• 집합 A와 B가 같다 $\Longleftrightarrow$ 완전히 같은 원소를 가지고 있음.

• 집합은 벤다이어그램이라는 그림을 통해 나타낼 수 있다.

• 집합 A에 원소 a가 속할 때

  • A ∋ a 와 같이 표현한다.

• 집합도 원소가 될 수 있다.

  • {1} ≠ {{1}}

Special Sets

Infinite Sets

• 집합은 무한할 수 있다.
• 특수한 무한 집합에 대한 기호들
  • N : 자연수 전체의 집합
  • Z : 정수 전체의 집합
  • R : 실수 전체의 집합

Empty Sets

• ∅ 공집합 : 원소를 가지지 않는 특수한 집합.
• ∅ = {} = {x | false}

Subset

• S가 T의 부분집합이면 S의 모든 원소는 T에 속한다.
• S ⊆ T $\Longleftrightarrow$ ∀x(x ∈ S → x ∈ T)
• 공집합은 모든 집합의 부분집합이다.
• 자기 자신도 부분집합이다.
• S = T $\Longleftrightarrow$ S ⊆ T ∧ S ⊇ T
• S ⊆ T & S ≠ T이면 S ⊂ T이다. (진부분집합)

2. Utilization of sets

Function of Set

Cardinality

• |S| : Cardinality of S. 집합 S의 크기, S의 원소의 갯수
• 원소의 갯수 ∈ N 이면, S는 유한하다. 그 이상이면, S는 무한하다
• N, Z, R은 모두 무한하다.

Power Set

• P(S) : Power Set of S. S의 멱집합, S의 모든 부분 집합의 집합
• 집합 S = {0, 1, 2} 의 P(S) = {∅, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}}
• 2^S로 작성할 수 있다.
• |P(N)| > |N| 이다.

Cartesian Products of Set

Ordered n-tuples

• 순서가 있는 집합.
• (a₁, a₂, ..., a_n) 와 같이 나타낸다.
• (1, 2) ≠ (2, 1)

Cartesian Product 데카르트 곱

• A, B 가 집합일 때, 데카르트 곱 A×B는 A ∋ a, B ∋ b 일 때 모든 (a, b) 순서쌍의 집합이다.
• {a, b} × {1, 2} = {a, 1}, {a, 2}, {b, 1}, {b, 2}
• |A×B| = |A||B|
• 교환 법칙이 성립하지 않는다.

3. Laws of operations of sets

Operation of set

합집합(∪, union) : A와 B가 집합일 때, A 또는 B에 속하거나 양쪽에 모두 속하는 원소들을 포함하는 집합

교집합(∩, intersection) : A와 B가 집합일 때, A와 B 양쪽 모두에 속한 원소들을 포함하는 집합

서로소(disjoint) : 두 집합의 교집합이 공집합(A∩B = ∅)일 때, 두 집합은 서로소이다.

• |A∪B| = |A| + |B| - |A∩B|

차집합(-, set difference) : A와 B가 집합일 때, A-B은 A에 속하지만 B에는 속하지 않는 원소들만 포함하는 집합

여집합(^c, set complement) : A와 B가 집합일 때, $\overline{A}$ 는 U-A를 의미한다.

• A-B = A∩B^c

Set Identities

Identity : A∩U = A / A∪∅ = A

Domination : A∪U = U / A∩∅ = ∅

Idempotent : A∪A = A / A∩A = A

Double complement : (A’)’ = A

Commutative : A∪B = B∪A / A∩B = B∩A

Associative : A∪(B∪C) = (A∪B)∪C / A∩(B∩C) = (A∩B)∩C

Distributive : A∪(B∩C) = (A∪B)∩(A∪C) / A∩(B∪C) = (A∩B)∪(A∩C)

DeMorgan's Law : (A∪B)’ = A’∩B’ / (A∩B)’ = A’∪B’

집합의 동치 증명 방법

• 서로가 서로의 부분 집합임을 증명
• 진리표가 같음을 통해 보임

4. Generalized Set

Generalized Union

• 여러 집합들 중 적어도 하나의 집합에 나타나는 원소들을 포함한 집합. $$ A_1 \cup A_2 \cup ... A_n = \displaystyle{\cup_{i=1}^nA_i} $$

Generalized Intersection

• 여러 집합들 모두에 나타나는 원소들을 포함한 집합. $$ A_1 \cap A_2 \cap ... A_n = \displaystyle \cap_{i=1}^nA_i $$

Representation

• 한 이산 구조를 다른 이산 구조 표현으로 나타내기

• Set : 0 = ∅ / 1 = {0} / 2 = {0, 1} / 3 = {0, 1, 2}

• Bit Strings : 0 = 0 / 1 = 1 / 2 = 10 / 3 = 11 / 4 = 100

• 집합을 bit string으로 나타내기.

  • 그 원소를 가지고 있으면 1, 없으면 0 ex)
    • S = {2, 3, 5, 7, 11}
    • B = 001101010001 → 2, 3, 5, 7, 11번째 만 1

1.1 ADT

• 배열 : <index, value>의 쌍으로 구성된 집합
• 기본 기능 : 값 검색, 값 저장
• ADT Array

  Objects : index의 각 값에 대해 집합 item에 속한 한 값이 존재하는 <index, value> 쌍의 집합. index는 1차원 또는 다차원의 유한 순서 집합이다.

• Functions*:     모든 A∈Array / i∈index / x∈item / j,size∈integer     Array Create(j, list)         return j 차원의 배열     Item Retrieve(A, i)         if (i∈index)

                 **return** 배열 A의 인덱스 i 값과 관련된 항목

          else return 에러     Array Store(A, i, x)         if (i∈index)

     &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** 새로운 쌍 <i, x>가 삽입된 배열 A

          else return 에러

1.2 C에서의 배열

• 1차원 배열의 선언 : int list[5];(정수의 배열) / int *plist[5];(정수 포인터의 배열)

• 배열 간의 주소 차이는 배열을 구성하는 변수의 크기에 비례한다. → 정수형(4 byte) 만큼 주소값 증가

• C에서 list[i]는 정수의 포인터로 사용할 수 있다

  • int *list1 과 int list2[5]가 같은 것을 나타낼 수 있다
  • (list2+i) = &list2[i]
  • *(list2+i) = list2[i]

• 배열 프로그램의 예

  #define MAX_SIZE 100
  float sum(float a[], int n);
  float input[MAX_SIZE], answer;
  

void main(){ int i; for (i = 0; i < MAX_SIZE; i++) input[i] = i; answer = sum(input, MAX_SIZE); printf("The sum is: %f\n", answer); }

float sum(float a[], int n){ int i; float tempsum = 0; for(i = 0; i < n; i++) tempsum += a[i]; return tempsum; }

→ sum 함수 호출시 a배열의 첫 원소에 대한 주소값 복사.
→ main 에선 i번째 원소에 i 저장 
→ sum 에선 a의 모든 원소를 더함 

- [1차원 배열의 주소 계산]
`int one[] = {0,1,2,3,4};` 의 i 번째 주소와 그 주소 내 값을 출력하는 함수
```c
void print1(int *ptr, int rows){
  // 포인터를 사용해 1차원 배열을 출력
  int i;
  printf("Address Contents\n");
  for(i = 0; i < rows; i++)
    printf("%8u%5d\n", ptr + i, *(ptr + i));
  printf("\n");
}

2. Dynamically Allocated Array

2.1 1차원 배열의 동적 할당

// malloc 을 이용한 1차원 배열
int i,n,*list;
printf("Enter the number of numbers to generate: ");
scanf("%d",&n);
if(n < 1){
    fprintf(stderr, "Improper value of n\n");
    exit(EXIT_FAILURE);
}
MALLOC(list, n * sizeof(int));

// malloc 매크로
#define MALLOC(p,s) \ // 포인터 p, 자료형의 크기 s
    if ((p = malloc(s) == NULL) { \
        fprintf(stderr, "Insufficient memory"); \
                exit(EXIT_FAILURE); \
    }

2.2 2차원 배열의 동적 할당

// 2차원 배열의 동적 할당
int** make2dArray(int rows, int cols){
  // rows x cols 크기의 2차원 배열을 생성
  int **x, i;

  MALLOC(x, rows * sizeof(int *));  // 행에 대한 공간 생성
  for(i = 0; i < rows; i++) 
    MALLOC(x[i], cols * sizeof(int)); // 각 행마다의 열에 대한 공간 생성
  return x;
}

• void *calloc(elt_count, elt_size 함수
  • elt_size만큼의 데이터 크기를 가진 elt_count길이의 동적 배열을 만드는 함수
  • 사용자가 지정한 매모리 할당 & 0으로 자동 초기화(malloc은 초기화 X)
• void *realloc(p, s) 함수
  • 기존 포인터 p를 s만큼의 사이즈로 바꾸는 함수

3. Structures and Unions

3.1 구조체

• 구조체 : 서로 다른 타입의 데이터를 그룹화 하는 것

  // 구조체 만들기
  typedef struct {
    char name[10];
    int age;
    float salary;
  } Person;
  

// 값 할당하기 strcpy(person.name, "james"); person.age = 10; person.salary = 35000;

→ `typedef` + `struct`로 단축해서 생성 가능

- 구조체 값 자체의 동등성 여부는 검사할 수 없음. 대신 함수를 생성해서 처리해야 함
```c
// 구조체 비교
#define FALSE 0
#define TRUE 1
typedef struct{
  char name[20];
  int age;
  float salary;
} humanBeing;

humanBeing person1, person2;
// person1과 person2 직접적 비교는 불가능

int humansEqual(humanBeing person1, humanBeing person2){
  // 동일인 일시 TRUE, 그렇지 않으면 FALSE 반환
  if (strcmp(person1.name, person2.name))
    return FALSE;
  if (person1.age != person2.age)
    return FALSE;
  if (person1.salary != person2.salary)
    return FALSE;
  return TRUE;
}

• 구조체 속 구조체 정의 가능

  // 구조체 속 구조체
  typedef struct date{
    int month;
    int day;
    int year;
  } date;
  

typedef struct{ char name[20]; int age; float salary; date dob; } humanBeing;

// 접근 방법 humanBeing person; person.dob.month = 2; person.dob.day = 11; person.dob.year = 2022;

### 3.2 유니온
- 유니온 : 메모리 공간을 공용으로 사용
  - 여러 필드 중 한 필드만 활성화 되어 사용 가능

ex) humanBeing 에서 sexType을 추가해 한 필드에서 여자라면 출산 아동수를, 남자라면 턱수염 여부를 저장
```c
typedef struct {
    enum tagField {female, male} sex;
    union {
        int childern;  // 여자인 경우
        int beard;  // 남자인 경우 
    } u;
} sexType;

typedef struct{
  char name[20];
  int age;
  float salary;
  sexType sexInfo;
} humanBeing;

// 접근 방법
humanBeing person1, person2;

person1.sexInfo.sex = male;
person1.sexInfo.u.beard = FALSE;

person1.sexInfo.sex = female;
person1.sexInfo.u.childern = 4;

→ 먼저 enum을 통해 태그 필드에 값 설정 → union에 있는 필드의 활성화를 결정

• C언어는 union의 올바른 필드 사용을 요구하지 않는다 (오류 발생 X)

3.3 구조체의 내부 구현

• 구조체 내부 요소의 주소값
  • 구조 정의에서 명세된 순서로 주소의 위치를 저장
  • 실제로는 메모리를 맞추기 위해 padding 할 수 있다
• 구조는 같은 유형의 메모리 경계에서 시작하고 끝남.
  • 짝수 바이트 or 4, 8, 16 배수 메모리 경계

3.4 자기 참조 구조(Self-Referential Structures)

• 자기 참조 구조 : 구성 요소 중 자기 자신을 가리키는 포인터가 1개 이상 존재하는 구조
  • 동적 저장 관리 루틴(malloc / free)가 필요

    typedef struct {
    char data;
    struct list *link;
    } list;

    → data는 하나의 문자, link는 자기 자신(list)에 대한 포인터 → 이를 활용해 list 구조 여러 개를 서로 연결할 수 있다.

Collection

• 정의 : 객체 그룹을 저장하고 조작할 수 있는 아키텍쳐를 제공하는 Java의 프레임워크
  • Java Standard Library에서 제공해주는 기능. 미리 구현이 되어 있음
• 장점
  • Standardization : 같은 컬렉션 안에 있는 구조들은 비슷한 Operation을 구현
  • Reusability : 재사용 가능한 자료구조와 알고리즘 제공

Key Components

• Interface
  • 구현하는 기능들에 대한 설명
  • ex)
    • List : 중복이 허용되는 순서가 있는 구조
    • Set : 중복이 허용되지 않는 구조
    • Map : key, value 쌍이 있고, key 값이 중복되지 않는 구조
• Implementations
  • 인터페이스가 실제로 구현된 클래스들. 실제 기능을 제공
  • ex)
    • ArrayList : List를 implement 하는 크기 조정 가능한 배열
    • HashSet : Set을 implement 하는 순서를 저장하지 않는 해시 테이블
    • HashMap : Map을 implement 하는 null key 와 null value를 허용하는 해시 테이블
• Algorithms
  • 컬렉션들에서 공통적인 operation을 수행하는 메소드
  • Sort, Search, Shuffle 등등.

2. Interfaces

List Interface

• 요소간 중복이 허용되는 순서 있는 구조

  ArrayList

  
• 크기 조정 가능한 배열, 필요한 만큼 크기를 늘릴 수 있다.
• index를 통한 접근 속도가 빠르다 → O(1)
• 데이터 추가 / 삭제 속도가 느리다 → O(n)
• 중복 허용, null value 허용 → 잘 변하지 않는 list에 사용한다.

LinkedList

• List와 Deque를 모두 implement 하는 구조
• index를 통한 접근 속도가 느리다 → O(n)
• 데이터 추가 / 삭제 속도가 빠르다 → O(1)
• 중복 허용, null value 허용
• Queue(FIFO) 나 Stack(LIFO) 로 사용 가능 → 데이터의 추가 & 삭제가 빈번한 list에 사용한다.

import java.util.LinkedList;

public class Example {
    public static void main(String args[]) {
        LinkedList<Integer> numbers = new LinkedList<>();

        // Adding elements
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);

        // Accessing elements
        System.out.println("First element: " + numbers.getFisrt());

        // Removing elements
        numbers.removeFirst();

        // Size of the list
        System.out.println("Size of list: " + numbers.size());

        // Iterating over the list
        for (Integer number : numbers) {
            System.out.println(number);
        }
    }
}

Set Interface

• 요소간 중복이 허용되지 않는 순서 없는 구조

  HashSet

• Set을 구현, hash table의 백업을 받음
• null 값을 허용
• add(), remove(), contains() 에 대한 시간 복잡도 O(1) → 순서가 상관 없고, 빠른 접근이 필요할 때 사용

  import java.util.HashSet;
  

public class Example { public static void main(String args[]) { HashSet set = new HashSet<>();

    // Adding elements
    set.add("Dog");
    set.add("Cat");
    set.add("Bird");
    set.add("Dog"); // 중복 요소, 추가되지 않음

    // Checking if an element exists
    System.out.println("Contains 'Cat': " + set.contains("Cat"));

    // Size of the set
    System.out.println("Size of set: " + set.size());

    // Iterating over the set
    for (String animal : set) {
        System.out.println(animal);
    }
}

}

#### LinkedHashSet
- `Set`을 구현, hash table 과 linked list의 백업을 받음
- `HashSet`을 상속 받음. Double Linked List 유지
- 요소의 삽입 순서를 유지한다
- 기본적 Operation에 대한 시간 복잡도 O(1)
- null 값 허용
→ 중복 불가 & 삽입 순서 유지가 필요할 때 사용

#### TreeSet
- `SortedSet`을 상속하는 `NavigableSet` 을 구현
- red-black tree 의 백업을 받음
- 요소들을 key 기준으로 정렬 (오름차순 / 커스텀 가능)
- null 값 허용 X
- add(), remove(), contains() 에 대한 시간 복잡도 O(log n)
→ 정렬된 Set 이 필요할 때 사용
``` java
Map<integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");

System.out.println(treeMap); // key 순으로 정렬 : {1=One, 2=Two, 3=Three}

Map Interface

• Key - Value 의 쌍을 가지는 구조. 1개의 key에 1개의 Value mapping
• Key 값의 중복을 허용하지 않는다.

  HashMap

• Map을 구현, hash table의 백업을 받음
• 1개의 null key 와 여러 개의 null value 허용 (나머지 케이스들을 모두 저장하는 곳)
• key / value 의 순서 저장 X
• put(), get() 에 대한 시간 복잡도 O(1) → 순서 상관없이 빠른 접근이 필요할 때 사용

LinkedHashMap

• HashMap 상속 받음. Double Linked List 유지
• 1개의 null key 와 여러 개의 null value 허용
• 기본적 Operation에 대한 시간 복잡도 O(1)
• 순서가 예상 가능하다(넣은 순서) → 넣은 순서 유지가 필요할 때 사용

TreeMap

• NavigableMap 구현, red-black tree 의 백업 받음
• key가 정렬됨. (오름차순 / 커스텀)
• null key 허용 X (throws NullPointerException)
• 기본적 Operation에 대한 시간 복잡도 O(log n) → key를 정렬해야할 때 사용

3. Iterator

Definition

• 어떤 collection 이든 공통적으로 구현하는 것들
• 장점
  • Uniform access : 모든 collection에 대해 똑같은 방식으로 접근할 수 있도록 함
  • Encapsulation : 어떤 collection인지 감춰 실수로 바꾸는 것을 막을 수 있음

Types of Iterators

• hasNext() : 다음 요소가 존재하면 true 반환 (전체 요소 순회 시 사용)
• next() : 다음 요소를 반환
• remove() : 마지막으로 반환된 요소를 삭제

  List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
  Iterator<String> iterator = list.iterator();
  while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
  }

4. Using Collections for Data Manipulation

Sorting

• Collections.sort()

  • 요소들을 natural ordering 에 기반해 정렬 (알파벳 순, 대문자 > 소문자)

  • List<String> list = Arrays.asList("Banana", "Apple", "Cherry");
    Collections.sort(list);
    // Apple, Banana, Cherry 순으로 정렬

• List.sort()

  • list 인터페이스에 있는 기본적 메소드
  • list.sort(Comparator.naturalOrder());

• Arrays.sort()

  • array의 요소들을 오름차순으로 정렬

  •   int[] numbers = {4, 2, 7, 3};
    Arrays.sort(numbers);
    // 2, 3, 4, 7 순으로 정렬
    

Custom Sorting

• Comparator 인터페이스
  • comparator(T o1, T o2) 메소드를 제공하는 함수형 인터페이스
  • Collections.sort(list, Comparator.reverseOrder());
  • 함수 자체에서 입력값 두 개를 비교하기 위해 사용 → 입력값 2개
• Comparable 인터페이스
  • 객체의 값과 다른 객체 입력값 1개를 비교하기 위해 사용 → 입력값 1개

  •   public class Person implements Comparable<Person> {
        private String name;
        private int age;
        // getters, setters, constructor
            @Override
        public int comPareTo(person other) {
            return Integer.compare(this.age), other.age);
        }
    }
    

Searching

• Collection.binarySearch()

  • 이진 탐색 알고리즘을 사용해 탐색

  • int index = Collections.binarySearch(list, "Apple");

• Map.containsKey()

  • map 이 특정한 key 값을 가지고 있다면 true 반환

• List.contains()

  • list 가 특정한 요소를 가지고 있다면 true 반환

• 탐색의 시간 복잡도는 어떤 자료 구조를 사용하는지에 따라 달라진다.

• SOP(Sum of Product)표현에서 사용하기 적합한 곱항을 발견하는 도식적인 접근법

• Letter : 변수와 상수

• Literal : 상수와 변수와 그 보수 (중복해서 계산) ex) B = {0,1 }, variable : x, y

  • letter : x, y, 0, 1
  • literal : x, y, x', y', 0, 1

• Product term

  • 1
  • non-constant literal : 변수&보수
  • 곱으로만 묶여야 함. 한 literal이 두 번 나오면 안됨.
  • 1, x, xy' / x+y (X), xy'x (X)

• Sum term

  • 0
  • non-constant literal : 변수&보수
  • 합으로만 묶여야 함. 한 literal이 두 번 나오면 안됨.
  • 0, x, x+y' / xy (X), x+y'+x (X)

• Minterm : 모든 변수가 항상 한번씩 사용된 product term

• Maxterm : 모든 변수가 항상 한번씩 사용된 sum term

카르노 맵

• F(a, b, c, d) = a'b'c'd' + a'bc + ab'c + bd + cd (SOP) = $\Sigma$(0,3,5,6,7,10,11,13,15)

• Implicant : 2^k개 의 1의 묶음 → 카르노 맵 묶는 단위
• Prime Implicant : 더 큰 묶음에 포함되지 않는 묶음
• Essential Prime Implicant : 하나의 prime Implicant를 형성하고 있는 1들 중에서 적어도 하나는 다른 Implicant에 속하지 않고 자신의 Prime Implicant 묶음에만 속하는 Prime Implicant

→ 간략화된 함수에는 EPI 전부와 non-essential PI 일부가 포함된다

3.2 카르노 맵을 이용한 최소 합의 곱(SOP)

• 맵 방법 1

  • 모든 Prime Implicant를 찾는다
  • 모든 EPI를 포함시킨다
  • 아직 커버되지 않은 모든 최소항(minterms)을 포함하기 위해 최소 비용의 비필수(non-essential) 소수 임플리컨트 집합을 선택

• 2변수 맵

• 3변수 맵

• 4변수 맵

• 5변수 맵

3.3 Don't Cares

• 카르노맵에서 Don't care는 함수에 포함되는 포함되지 않든 상관하지 않는다.

• 맵 방법 2

  • 모든 필수 주항을 찾는다
  • 필수 주항에 의해 커버되는 모든 1들을 X로 바꾼다.
  • 그 후는 방법 1 이용.

3.4 곱의 합(POS)

1) 함수의 보수 맵을 만든다.(0은 1으로, 1은 0으로, X는 그대로) 2) 함수의 보수에 대한 최소 SOP 표현을 찾는다. 3) SOP 표현을 POS 표현으로 바꾼다.

• Requirement : 요구사항. 주어진 자료 입력 + 생성해내야 하는 결과(출력)

• Analysis : 분석.

  • bottom-up : 밑에서 위로. 코딩에 주안점을 둠
  • top-down : 문제를 분석해 작은 단위로 분리해 해결 → 더 좋은 방식

• Design : 설계. 추상 데이터 타입(ADT) + 알고리즘 설계

• Refinement and Coding : 자료 객체에 대한 표현 선택 & 알고리즘 작성

• Verification : 검증. 프로그램 정확성 체크, 테스트 & 오류 수정

  • 시간 복잡도 : running time
  • 공간 복잡도 : amount of memory used

2. Algorithm Specification

2.1 알고리즘이란?

• 알고리즘 : 특정한 일을 수행하는 명령어들의 유한 집합 1) Input : 입력. 외부에서 제공되는 데이터가 0개 이상 존재 2) Output : 출력. 적어도 한 개 이상의 결과를 생성 3) Definiteness : 각 단계들은 명확해야 함. 4) Finiteness : 알고리즘은 유한시간 안에는 반드시 끝나야 함. 5) Effectiveness : 모든 명령은 종이와 연필만으로 수행할 수 있을 정도로 기본적이어야 함.

• 알고리즘 표현 : 자연어, flowchart, 프로그래밍 언어

Selection Sort 1st : finding the smallest integer; 2nd : exchange (함수 or macro);

for (i=0; i<n; i++){     Examine list[i] to list[n-1]     and suppose that the smallest integer is at list[min]     Interchange list[i] and list[min] }

// Swap Function
void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Call : swap(&a, &b)

// Swap Macro
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t)

// Selection Sort 
void sort(int list[], int n){
      int i, j, min, temp;
      for(i = 0; i < n-1; i++){
        min = i;
        for(j = i+1; j < n; j++)
          if(list[j] < list[min]) 
            min = j;
           SWAP(list[i], list[min], temp);
      }
}

• Sort 알고리즘은 n $\geq$ 1 이상의 정수들의 모음을 정렬한다.

Binary Search 1st : 아직 검사할 정수가 남아 있는지 결정 2nd : searchnum과 list[middle] 비고

while(there are more integers to check){     middle = (left + right) / 2;     if (searchnum < list[middle])         return middle;     else left = middle + 1;

//Compare Function
int compare(int x, int y){
  if(x < y) return -1;
  else if(x == y) return 0;
  else return 1;
}

// Compare Macro
#define COMPARE (x,y) ((x) < (y)) ? -1: ((x) == (y)) ? 0 : 1)

// Binary Search
int binsearch(int list[], int searchnum, int left, int right){
  int middle;
  while(left <= right){
    middle = (left + right) / 2;
    switch(COMPARE(list[middle], searchnum)){
      case -1: 
        left = middle + 1; 
        break;
      case 0: return middle;
      case 1: right = middle - 1;
    }
  }
  return -1;
}

2.2 재귀 알고리즘

• Direct recursion : 직접 순환. 함수가 그 수행이 완료되기 전에 자기 자신을 다시 호출

• Indirect recursion : 간접 순환. 호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출

• [Binomial Coefficients] : 조합의 재귀적 표현

  $$ \left[ \begin{matrix} n \ m \ \end{matrix} \right] = {n!\over m!(n-m)!} $$

  $$ \left[ \begin{matrix} n \ m \ \end{matrix} \right] = \left[ \begin{matrix} n-1 \ m \ \end{matrix} \right] + \left[ \begin{matrix} n-1 \ m-1 \ \end{matrix} \right] $$

• [Fatorial] : 팩토리얼

  $$ n! = \begin{cases} n \times (n-1)! \quad if, \ n > 1\ 1 \quad if,\ n = 1 \end{cases}$$

• [Binary Search] : 이진 탐색

BSrch[key, left, right]
    if key < list[middle]
        BSrch[key, left, middle-1]
    if key = list[middle]
        list[middle]
    if key > list[middle]
        BSrch[key, middle+1, right]

// 이진 탐색 재귀적 구현
int binsearch(int list[], int searchnum, int left, int right){
  int middle;
  if(left <= right){
    middle = (left + right) / 2;
    switch(COMPARE(list[middle], searchnum)){
      case -1: 
        return binsearch(list, searchnum, middle + 1, right);
      case 0: return middle;
      case 1: 
        return binsearch(list, searchnum, left, middle - 1);
    }
  }
  return -1;
}

• [Fibonacci Number] : 피보나치 수열

f_n = 0 (if n = 0) f_n = 1 (if n = 1) f_n = f_n-1 + f_n-2 (if n > 1)

// 일반 함수
int fibo(int n){
    int g, h, f, i;
    if(n>1){
        g = 0;
        h = 1;
        for(i = 2; i <= n; i++){
            f = g + h;
            g = h;
            h = f;
        }
    }
    else f = n;
    return f;
}

// 재귀 함수
int rfibo(int n){
    if(n > 1) 
        return rfibo(n-1) + rfibo(n-2);
    else return n;
}

• [Permutations] : 순열 생성

// 순열의 재귀적 생성
void perm(char *list, int i, int n){
  int j, temp;
  if(i == n){
    for(j = 0; j <= n; j++)
      printf("%c", list[j]);
    printf("\n");
  } else {
      // list에 1개 이상의 문자가 들어있으면 재귀적으로 생성
    for(j = i; j <= n; j++){
      SWAP(&list[i], &list[j]);
      perm(list, i + 1, n);
      SWAP(&list[i], &list[j]);
    }
  }
}

3. Data Abstraction

• 데이터 타입 : 객체(object)와 그 객체를 가지고 하는 연산(operation)들의 모음

  • C의 기본 데이터 타입 : char, int, float, double ...
  • 여러 데이터를 grouping : array, struct
  • pointer 타입

• 추상 데이터 타입(ADT, Abstract Data Type) : 객체와 연산의 명세가 구현으로부터 분리된 데이터 타입. → 내부적 표현 or 구현에 대한 설명이 필요 없음

  • ADT 가 가지는 함수의 종류
    1. 생성자(creater)/구성자(constructor) : 지정된 타입에 맞는 새로운 인스턴스 생성
    2. 변환자(transformer) : 1개 이상의 다른 인스턴스를 사용해 지정된 타입의 한 인스턴스 만듬.
    3. 관찰자(observers)/보고자(reporter) : 인스턴스에 대한 정보 제공. 변화는 X

• [ADT Natural_Number ]

  Object : 0에서 시작해서 컴퓨터상의 최대 정수 값(INT_MAX)까지 순서화된 정수의 부분 범위

• Function*:     Nat_Number_의 모든 원소 x,y 그리고 _Boolean_의 원소 T     _NaturalNumber Zero() ::= 0     Boolean IsZero(x) ::=
          if (x) return FALSE
          else return TRUE     Boolean Equal(x,y) ::=
          if(x==y) return TRUE         else return FALSE     NaturalNumber Successor(x) ::=         if(x == INT_MAX) return x    &nbsp   &nbspelse return x+1    &nbsp_NaturalNumber_ Add(x,y) ::=    &nbsp   &nbspif((x+y) <= INT_MAX) return x+y    &nbsp   &nbspelse return INT_MAX    &nbsp_NaturalNumber_ Subtract ::=    &nbsp   &nbspif(x<y) return 0    &nbsp   &nbspelse return x-y

• 자세한 구현을 피하기 위해 ADT 사용

4. Performance Analysis

성능 분석의 기준

1. 프로그램이 원래의 명세와 부합하는가?
2. 정확하게 작동하는가?
3. 프로그램을 어떻게 사용하고 어떻게 수행하는지에 관한 문서화가 프로그램 내에 되어져 있는가?
4. 논리적 단위를 생성하기 위해 프로그램이 함수를 효과적으로 사용하는가?
5. 프로그램 코드는 읽기 쉬운가?

• 성능 분석

6. 프로그램이 메인 메모리와 보조기억장치를 효율적으로 사용하는가?
7. 작업에 대한 프로그램의 실행 시간은 허용할 만한가?

• Performance Analysis : 기계와 독립적인 시간 & 공간에 대해 평가
• Performace Measurement : 기계와 독립적이지 않은(의존적인) running time 계산. 비효율적인 코드 찾을 때 사용

4.1 공간 복잡도

• Fixed space requirement : 고정 공간 요구. 프로그램 입출력의 횟수나 크기와 관계 없는 공간 요구

  • 명령어 공간, 단순 변수, 고정 크기의 구조화 변수, 상수 등.

• Variable space requirement : 특정 인스턴스에 의존하는 크기를 가진 구조화 변수의 공간

• 전체 프로그램이 필요한 공간 : 고정 공간 + 가변 공간

  $S(P) = c + S_P(I)$

  → 공간 복잡도 분석시에는 가변 공간 요구에만 관심 가짐.

• 공간 복잡도 구하는 예시

  // 단순 산술 함수
  float abc(float a, float b, float c){
  return a+b+b*c+(a+b-c)/(a+b)+4.0;

  → $S_{abc}(I) = 0$

// 리스트에 있는 수를 합산하기 위한 반복 함수
float sum(float list[], int n){
  int i;
  float tempSum = 0;
  for(i = 0; i < n; i++)
    tempSum += list[i];
  return tempSum;
}

→ $S_{n}(I) = 0$ : 인자가 pass-by-reference일 때(포인터로 전달) → $S_{n}(I) = n$ : 인자가 pass-by-value일 때(전체 배열 복사)

// 리스트에 있는 수를 합산하기 위한 순환 함수
float rsum(float list[], int n){
  if(n) return rsum(list, n-1) + list[n-1];
  return 0;
}

→ 같은 함수라도 순환 함수로 구현하면 공간 요구가 더 커짐.

4.2 시간 복잡도

• 소요되는 총 시간 : 컴파일 시간 + 실행 시간

  $T(P) = c + T_p(I)$

  → 시간 복잡도 분석시에는 실행 시간에만 관심 가짐.

• 프로그램 단계 program step : 실행 시간이 인스턴스 특성에 구문적으로 / 의미적으로 독립성을 갖는 프로그램의 단위

• 시간 복잡도 구하는 예시

  // 리스트에 있는 수를 합산하기 위한 반복 함수
  float sum(float list[], int n){
  int i;
  float tempSum = 0;
  for(i = 0; i < n; i++)
    tempSum += list[i];
  return tempSum;
  }

  → 2n + 3

  • 단계 수 테이블 방식 : 명령문에 대한 단계수(s/e, steps/execution), 빈도수(명령문이 수행되는 횟수, frequency)
    • s/e * 빈도수 = 총 단계 수 (total steps)
    • 

• 같은 함수라도 case에 따라 step count가 다를 수 있다.

4.3 Asymptotic Notation (O, $\Omega$, $\Theta$)

• Step count를 직접 구하는 대신 점근 표기법 사용

  Big-O Notation

  f(x) = O(g(x)) ↔ x > k 일 때 항상 $|f(x)| \leq C|g(x)|$ 를 만족하는 상수 C와 k 가 존재한다.

• 최고 차항만 남기기

• Big-O의 예시

  • 3n + 2 = O(n)
  • 10n² + 4n + 2 = O(n²)
  • 6 $\cdot$ 2ⁿ + 4n² + 2 = O(2ⁿ)

Big-Omega

f(x) = $\Omega$(g(n)) ↔ x > k 일 때 항상 $|f(x)| \geq C|g(x)|$ 를 만족하는 상수 C와 k 가 존재한다.

• 빅오가 상한값이하면, 오메가는 하한값.
• 작은 것 중 가장 큰 것.
• Big-$\Omega$의 예시
  • 3n + 2 = $\Omega$(n)
  • 10n² + 4n + 2 = $\Omega$(n²)
  • 6 $\cdot$ 2ⁿ + 4n² + 2 = $\Omega$(2ⁿ)

Big-Theta

f(x) = $\Theta$(g(n)) ↔ f(x) = O(g(x)) && f(x) = Ω(g(x))

• Big-$\Theta$의 예시
  • 3n + 2 = $\Theta$(n)
  • 10n² + 4n + 2 = $\Theta$(n²)
  • 6 $\cdot$ 2ⁿ + 4n² + 2 = $\Theta$(2ⁿ)

시간 복잡도 구하기

• [Matrix addition]

  void add(int a[][MAX_SIZE] ...){
    int i, j;
    for(i = 0; i < rows; i++)
        for(j = 0; j < cols; j++)
            c[i][j] = a[i][j] + b[i][j];
  }

  → 시간 복잡도 : $\Theta$(rows * cols)

• [Binary Search] → 시간 복잡도 : $\Theta$(log n)

  • best case : $\Theta$(1)

• [Magic Square]

  // 매직 스퀘어 프로그램
  int main(void){
  // 정방형을 반복적으로 생성
  int square[MAX_SIZE][MAX_SIZE];
  int i, j, row, column;  // 지수
  int count; // 계수
  int size; // 정방형의 크기
  
  printf("Enter the size of the square: ");
  scanf("%d", &size);
  
  // 입력에 오류가 있는지 체크
  if(size < 1 || size > MAX_SIZE + 1){
    fprintf(stderr, "Error! Size is out of range\n");
    exit(1);
  }
  if(!(size % 2)){
    fprintf(stderr, "Error! Size is even\n");
    exit(1);
  }
  
  for (i=0; i<size; i++)
    for(j=0; j<size; j++)
      square[i][j] = 0;
  square[0][(size - 1) / 2] = 1; // 첫 번째 행의 중앙에 1 넣기
  // i와 j는 현재 위치
  i = 0;
  j = (size - 1) / 2;
  for(count = 2; count <= size * size; count++){
    // 다음 위치 계산
    row = (i - 1 < 0) ? size - 1 : i - 1;  // 위로
    column = (j - 1 < 0) ? size - 1 : j - 1;  // 왼쪽으로
    // 이미 채워져 있는지 확인
    if(square[row][column]){  // 아래로
      i = (++i) % size;
    }
    else{  // 정방형이 비어있을 경우
      i = row;
      j = column;
    }
    square[i][j] = count;
  }
  // 정방형 출력
  printf("\nMagic Square of size %d: \n\n", size);
  for(i = 0; i < size; i++){
    for(j = 0; j < size; j++)
      printf("%5d", square[i][j]);
    printf("\n");
  }
  printf("\n\n");
  }

  시간 복잡도 : $\Theta$(n²)

4.4 실용적 복잡도

5. Performance Measurement

• 시간 측정 방법 : <time.h> 사용

파일 읽기 : FileReader / BufferedReader

• 한 번 열면 반드시 닫아야 한다. → try-catch 블럭 사용
• FileReader : 한글자씩 읽음(비효율적)
  • 짧은 문자열 읽을 때 사용
• BufferedReader : readline() 사용 가능
  • 주로 이 class를 사용

try (BufferedReader br = new BufferedReader(new FileReader("file.txt"))) {
    String line;
    while ((line = br.readLine() != null){
        System.out.println(line);
    }
} catch (IOException e) {
    e.printStackTrace();
}

→ FileReader을 인자로 받아 읽도록 함

파일 쓰기 : FileWriter / BufferedWriter

• 한 번 열면 반드시 닫아야 한다. → try-catch 블럭 사용
• FileWriter : 한글자씩 씀(비효율적)
  • 짧은 문자열 쓸 때 사용
• BufferedWriter : String을 한 번에 입력 가능
  • 주로 이 class를 사용

    try (BufferedWriter bw = new BufferedWriter(new FileWriter("file.txt"))){
    bw.write("Hello, World!");
    } catch (IOException e) {
    e.printStackTrace();
    }

    → FileWriter을 인자로 받아 쓰도록 함

2. Serialization

시리얼화

• 어떤 타입의 객체(object)이던 상관없이 byte 타입으로 저장하는 것

• ObjectOutputStream / ObjectInputStream 사용

• How to?

  1. Serialzable 인터페이스 implement & serialVersionID 통해 check

        public class MyClass implements Serializable {
            private static final long serialVersionID = 1L;
     
            // class field and method
        }

  2. 객체를 시리얼화 : ObjectOutStream 사용 → File에 저장

        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("object.ser"))) {
            oos.writeObject(new Myclass()));
        } catch (IOException e) {
            e.printStackTrace();
        }

     → FileOutputStream을 인자로 받아 사용

  3. 시리얼에서 다시 객체로 불러오기 → File에서 불러와서 객체에 저장

        try(ObjectInputStream ois = new ObjectInputStream(new FileInputStream("object.ser"))){
            MyClass obj = (MyClass) ois.readObject();
        } catch (IOException | ClassNotFoundException e){
            e.printStactTrace();
        }

     → FileInputStream을 인자로 받아 사용

     시리얼화의 장점

• Persistence : 파일 or DB에 저장했다 다시 불러올 수 있음

• Distributed system : 다른 JVM에 전달 가능

• Deep copy : 객체의 깊은 복사할 때 사용 가능

• Caching : 캐싱할 때 좋음

• Interoperability : 여러 곳에서 사용 가능

• Versioning : 시리얼 ID를 통해 버전 체크 가능

Throwable

• Error와 Exception의 상위 클래스

• Throwable

  • Error
    • OutOfMemoryError
    • StackOverflowError
    • VirtualMachineError
    • etc.
  • Exception
    • RuntimeException
      • NullPointerException
      • ArrayIndexOutOfBoundsException
      • ClassCastException
      • etc.
    • IOException
    • SQLException
    • etc.

Error 클래스

• 컴퓨터에 영향을 줄 수 있어서 발생. JVM이 찾아냄
• 환경에 다뤄야 하는 부분 ex) OutOfMemoryError, StackOverflowError, VirtualMachineError

Exception 클래스

• 런타임 중에 발생. 직접 체크해야하는 부분

• Checked : try-catch 구문으로 예외를 처리해야 하는 부분

  • IOException, SQLException, ClassNotFoundException

• Unchecked : 코드 수정으로 처리해야 하는 부분

  • NullPointerException, ArrayIndexOutOfBoundsException

• 예외의 상하 관계 ex) FileNotFoundException < IOException < Exception

2. Try-Catch Block and Throw Clause

Try-Catch 블럭

try {
    // 예외를 찾을 수 있는 코드 넣기
} catch (ExceptionType2 e1) {
    // 오류 발생 시 실행할 구문
} catch (ExceptionType2 e2) {
    // 한 try에 여러 catch 사용 가능
} finally {
    // 오류 발생 여부 관계 없이 반드시 실행
}

• try에서 예외가 발생되는 순간 바로 catch로 넘어간다. 예외 발생 시점 이후의 try 구문은 무시된다.
• catch에 들어가는 예외는 작은 → 큰 순으로 적어야 한다.
• Exception 클래스는 모든 예외의 상위 클래스, 어떤 예외라도 받을 수 있다.

Throw clause

• 특정 메소드가 exception을 throw 할 수 있다고 경고하는 것

  public void myMethod() throws IOException {
  

}

- exception에 대한 경고가 있는 메소드는 반드시 try-catch로 처리해야한다.
  - 처리 위치는 상관이 없으나, 처리 안할시 오류 발생

## 3. Custom Exception
- 사용자가 직접 만드는 예외
  - 클래스 정의 & 생성자로 예외 생성
   ``` java
  public class MyCustomException extends Exception {
      public MyCustomException(String Message){ // 생성자
          super(message);
  }

 → Exception 클래스 상속 받기

• 예외가 들어갈 메소드 만들기 & 예외 던지기

  public class TestCustomException {
    public void myMethod() thorws MyCustomException{
         throw new MyCustomException("Custom error message");
     }
  }

• main : 예외가 들어간 메소드 실행 & 예외 처리

  public static void main(String[] args) {
    TestCustomException test = new TestCustomException();
     try{
         test.myMethod();    
     } catch (MyCustomException e) {
         System.out.println("Caught custom exception: " + e.getMessage());
     }
  }

OOP의 정의

Object-Oriented Programming : 객체지향적 프로그래밍

• Object : 객체, 데이터와 메소드를 캡슐화한 class의 인스턴스 단위
• Class : 클래스, Object의 청사진
• Data : 변수, field
• Code : 메소드, method

OOP의 장점

• Modularity 모듈성 : 하나의 큰 덩어리를 만들기 위해 작은 모듈로 나누는 것

• Reusability 재사용성 : 코드를 재사용 하기 좋음

• Extensibility 확장성 : 존재하는 코드의 기능을 늘리기 좋음 (상속)

  • core 한 기능을 구현 해놓고 파츠를 붙임

• Maintainability 유지성 : 부분들이 나눠져 있어 유지 보수에 좋음

  • 변화가 필요한 부분에만 코드 수정

2. Classes and Objects

Class - 클래스

Class : object를 만드는 청사진. 변수와 메소드를 정의함.

public class Car{
    String color;
    int speed;
    //field

    void accelerate(){
        speed += 10;
    }
    // method
}

Object - 객체

Object : class의 인스턴스. new 키워드를 사용해서 만들어짐.

Car myCar = new Car();
// Car 클래스의 myCar라는 새로운 객체 생성
myCar.color = "red";
myCar.accelerate();
// 클래스 정의 시의 변수와 메소드 사용 가능

3. Constructors and Methods

Constructor - 생성자

Constructor : 객체가 생성될 때 초기화 할 수 있는 특별한 메소드

• 생성자의 이름은 class 명과 동일.
• this 키워드 사용 가능(오직 생성자에서만 사용 가능)
• Overloading 가눙

public class Car{
    String color;
    int speed;

    //Constructor
    public Car(String color, int speed){
        this.color = color;
        this.speed = speed;
    }
}

Methods - 메소드

Method : class 안에 존재하는 함수들

public class Car{
    String color;
    int speed;

    // Method
    void accelerate(){
        speed += 10;
    }

}

3. Inheritance and Polymorphism

Inheritance - 상속

상속 : 다른 class의 메소드와 변수를 상속 받는 것

• extends 키워드 사용

  • superclass : 상위 클래스
  • subclass : 하위 클래스

• 장점 : Reusability(재사용성), Hierarchy(상하관계), Overriding(오버라이딩)

• 생성자에서 super 키워드 사용 가능

public class Animal{
    private String name;

    // Constructor
    public Animal(String name){
        this.name = name;
    }

    // Method
    public void makeSound(){
        System.out.println("Some animal Sound");
}

→ 상위 클래스

public class Dog extends Animal{ 
    // Constructor
    public Dog(String name){
        super(name);
    }

    @Override
    public void makeSound(){
        System.out.println("Bark");
}

→ 하위 클래스

• 상속에는 다양한 형태가 있다.

Polymorphism - 다형성

Method Overriding : 상위 클래스의 메소드를 하위 클래스에서 재사용 하는 것

Method Overloading : 같은 이름, 다른 인자를 가지는 메소드를 만드는 것. 반드시 다른 인자를 가져야 함.

public class MathOperations{
    // 두 정수 더하기
    public int add(int a, int b)
        return a + b;

    // 세 정수 더하기로 overloading
    public int add(int a, int b, int c)
        return a + b + c;

    // 두 실수 더하기로 overloading
    public double add(double a, double b)
        return a + b;
}

Dynamic Method Dispatch : 동적 메소드 디스패치. 하위 클래스는 상위 클래스를 대체할 수 있다.

public static void main(String[] args){
    Animal myDog = new Dog("Buddy");
    Animal myCat = new Cat("Whiskers");
}

• Animal 배열에 myDog, myCat이 들어갈 수 있다(Animal class를 상속하고 있기 때문에)

4. Encapsulation and Abstraction

Encapsulation - 캡슐화

• 접근 권한을 제한하기 위해 사용
• 접근 제한자를 활용한 데이터 숨김 → 함부로 열 수 없다
• Getter & Setter

Access Modifier - 접근 제한자

default : 기본값. 같은 package 내에서 사용 가능 public : 어디에서나, 누구나 사용 가능 private : class 내부에서만 사용 가능 protected : 같은 package + package 밖의 상속된 하위 클래스에서 사용 가능

• 보안 수준 : private < default < protected < public
• package 패키지 : 다른 패키지의 class를 이용하기 위해선 import 사용해야 한다.

Abstraction - 추상화

• 디테일이 없는, 모양만 잡아둔 것. class, method 에 사용할 수 있다

  abstract class Shape{ // 추상 클래스
    abstract double area();  // 추상 메소드
  }

• 추상 메소드는 내부에 코드를 작성하지 않는다.

5. Interfaces and Abstract Classes

Abstract Class - 추상 클래스

• class이지만 인스턴스를 생성할 수 없다. 상속의 역할.

• 추상 메소드 + 일반 메소드 both 생성 가능

• 변수 포함 가능

  abstract class Shape{
    double length;  // 변수
  
    abstract double area();  // 추상 메소드
    void display(){  // 일반 메소드
        System.out.println("Displaying Shape");
    }
  }

• 상속 후 overriding을 통해 메소드의 세부 내용을 채워야 함.

• A는 B다의 관계

  • 고양이는 동물이다
  • 직사각형은 도형이다

Interface 인터페이스

• 추상 메소드만 포함 가능.
• 클래스와 상관없이 사용 가능.
• implements 키워드 사용. 한 번에 다양한 인터페이스 implement 가능

  interface Sound {
    void makeSound();
  }
  

class Dog implements Sound{ @Override public void makeSound(){ System.out.println("Bark"); } }

```

• 기능에 관한 내용
  • 동물은 귀여운 소리를 낸다
  • 로봇은 귀여운 소리를 낸다

자바 프로그램의 기본 구조

class : object 를 만드는 청사진. 변수와 메소드로 구성

public class ClassName{
     // fields 변수
    // methods 함수
}

• main 함수 : 실행의 시작점. 클래스에 1개만 존재할 수 있음

  public static void main(String[] args) {
      // 실행할 코드
  }

문법 규칙

• 대문자 / 소문자 구별

• 이름 짓는 규칙

  • class : 대문자 시작, CamelCase 사용 MyClass
  • 메소드 & 변수 : 소문자 시작, camelCase 사용 myVariable / myMethod
  • 상수 : 대문자로만 작성, 공백은 _ 사용 MAX_VALUE

• 주석

  • 한 줄 주석 : //

  • 여러 줄 주석 : /* */

  • Documentation Comments : /** */

    public class Class{
      // 한 줄 주석
    
      /* 여러 줄
         주석 */
    
      /**
       * Documentation
       * Comments
       */
    }

2. Data Types, Variavles, and Operators

원시 데이터 타입

• 정수

• 실수

• 기타 타입

변수와 변수의 범위

변수의 선언과 초기화

int number;  // 선언
number = 10; // 초기화
int number = 10; // 선언과 동시에 초기화 가능

변수의 범위

• 지역 변수 : 메소드나 중괄호 블럭 내에 선언된 변수. 벗어날 시 소멸

  public void myMethod(){
    int localVar = 10;  // myMethod 내부에서만 존재하는 지역 변수
  }
  // 메소드 밖으로 나가면 소멸

• 인스턴스 변수(객체 변수) : 클래스 안에 있지만 메소드 밖에 있는 변수. 객체(인스턴스) 당 하나 → 클래스 안 모든 메소드에서 사용 가능. 객체(인스턴스) 소멸 시 같이 소멸

  public class myClass{
    int instanceVar;  // myClass 안에서 존재하는 인스턴스 변수
  }

• static variable 정적 변수, 클래스 변수 : static 키워드가 붙은 클래스 변수

  • 같은 클래스를 가지는 모든 객체(인스턴스)가 공유. 클래스 당 하나
  • 클래스가 로딩되는 시점에 생겨남. (객체 생성 이전)

    public class myClass{
    static int classVar;  // 같은 클래스를 가진 모든 객체가 공유하는 변수
    }

연산자

• 비교 연산자

• 논리 연산자

3. Control Flow Statements

조건문

• if, else if, else

  int number = 10;
  if (number > 0) {
    System.out.println("Positive");
  } else if (number < 0) {
    System.out.println("Negative");
  } else {
    System.out.println("Zero");
  }

• switch

  int day = 3;
  switch(day) {
    case 1 :
        System.out.println("Monday");
        break;
    case 2 :
        System.out.println("Tuesday");
        break;
    case 3 :
        System.out.println("Wednesday");
        break;
    default:
        System.out.println("Other day");
  }

반복문

• for
• while
• do ~ while

  int i = 0;
  do {
    System.out.println("Iteration: " + i);
    i++;
  } while (i<5);

Module #2: Basic Proof Methods

1. Predicate Logic

P(x) : x is greater than 3

• 명제함수(propositional function) P에서의 x의 값

• 주어* : x

• 술어(predicate)* : is greater than 3

• 규칙

  • 함수는 대문자, 변수는 소문자
  • 함수 그 자체(P)는 명제가 아님. 변수가 들어가야 명제 (P(3), P(x))
  • 변수는 1개 이상 가능 P(x, y, z)

• Universes of Discourse : 정의역

한정기호

전칭 한정기호(∀) : 정의역에 속하는 모든 x값에 대하여 P(x)이다.

• P(x)가 거짓이 되는 원소를 ∀xP(x)의 반례라고 부른다

존재 한정기호(∃) : 정의역에 속하는 적어도 하나의 값 x에 대하여 P(x)이다.

유일 한정기호(∃!) : 유일하게 한 개만 존재할 때 사용한다.

• 한정 기호의 순서에 따라 뜻이 달라진다

• 한정기호는 모든 논리 연산자보다 상위의 우선순위를 갖는다

  ∃xQ(x) ∨ P(x) = (∃xQ(x)) ∨ P(x)

한정 기호에 대한 드 모르간 법칙

∀xP(x) = ∃xP(x) ∃xP(x) = ∀xP(x)

구속 변수와 자유 변수

구속 변수 : 한정 기호가 적용된 변수

자유 변수 : 한정 기호가 적용되어 있지 않거나, 값이 할당되어 있지 않은 변수

ex) ∀xP(x,y)에서 x는 구속 변수, y는 자유 변수이다.

2. Proof

Proof Terminology

• Theroem(정리) : 참이라고 증명된 하나의 진술
• Axiom(공리), hypotheses(가설), premises(전제) : 우리가 추론하는 구조를 정의하는 가정들
• Rules of inference(추론 규칙) : 가설에서 결론을 도출하는 논리적으로 타당한 추론 패턴
• Lemma(보조정리) : 주요 정리를 증명하기 위한 중간 단계로 사용되는 작은 정리
• Corollary(따름정리) : 증명된 정리로부터 직접적으로 귀결될 수 있는 정리
• Conjecture(가설) : 어떤 부분적 증거에 근거해 참이라고 주장되는 문장.
• Theory(이론) : 주어진 공리 집합에서 증명할 수 있는 모든 정리들의 모음

Inference Rules 추론 규칙

• 전제가 모두 참이면 결론도 참이다.

Rule of Addtion (∨ 도입)

1. p __
2. p ∨ q

Rule of Simplification (∧ 제거)

1. p ∧ q __
2. p

Rule of Conjunction (∧ 도입)

1. p
2. q __
3. p ∧ q

Rule of modus ponens (the mode of affirming, → 제거)

1. p
2. p → q __
3. q

Rule of modus tollens (the mode of denying, 후건 부정)

1. ~q
2. p → q __
3. ~p

Rule of hypothetical syllogism (가설적 삼단논법)

1. p → q
2. q → r __
3. p → r

Rule of disjunctive syllogism (선언적 삼단논법, ∨ 제거)

1. p ∨ q
2. ~p __
3. q

Inference Rules for Quantifiers 양화사의 추론규칙

Universal instantiation (∀ 제거)

1. ∀x P(x) __
2. P(o) // 임의의 o 가정

Universal generalization (∀ 도입)

1. P(g) // 임의의 g 가정 __
2. ∀x P(x)

Existential instantiation (∃ 제거)

1. ∃x P(x) __
2. P(c) // 임의의 c 가정

Existential generalization (∃ 도입)

1. P(o) // 임의의 존재하는 o 가정 __
2. ∃x P(x)

증명의 오류들

• Affirming the conclusion : 결론 긍정의 오류. 결론이 참일지라도 전제가 거짓일 수 있다.
• Denying the hypothesiss : 가설 부정의 오류. p → q 일때, p가 거짓이라고해서 q가 거짓인 것은 아니다.
• Circular Reasoning : 순환 논증. 결론을 뒷받침하기 위해 결론을 다시 사용하는 오류

증명의 방법들 (p → q)

• Direct Proof 직접 증명 : p가 참일 때, q가 참임을 증명
• Indirect Proof 간접 증명(대우에 의한 증명) : ~q를 가정하고, ~p임을 증명
• Vacuous Proof 공허한 증명 : ~p를 증명
• Trivial Proof 자명한 증명 : q를 증명
• Proof by Contradiction 모순에 의한 증명
  • ~p → (q ∧ ~q) 이 참임을 보여 p가 참임을 증명
• Proving Existential
  • Existence Proof 존재 증명 : ∃x P(x)일 때, P를 만족하는 원소를 구함. → 생산적 증명
  • 비생산적 증명 : 존재 정량화의 부정을 모순법을 사용해 증명
• Proof by cases 경우에 의한 증명 : 모든 경우의 수를 고려해 증명

조합 시스템 Combinational System : 클락을 사용하지 않는 디지털 회로

디지털 회로(Digital circuit) : binary 정보를 조작하는 하드웨어 부품

논리 게이트는 논리 함수를 구현한다. 논리 함수 : AND, OR, NOT, XOR, NOR, NAND

Boolean Algebra : 논리 함수를 특정하고 변환하기 위한 수학적 시스템

Level of Abstraction 추상화 레벨

2.2 Logical Operation 논리 연산자

- 기본 연산자

AND ( · )

OR (+)

NOT (~)

XOR (⊕)

NAND / (xy)'

NOR / (x+y)'

XNOR (x⊙y)

- 스위치에서의 논리 연산자

AND → 직렬

OR → 병렬

NOT → 기본적으로 닫혀있는 스위치

똑같은 논리 함수에 대해 진리표(truth table), 논리 선도(logic diagram), 논리식(boolean equation)로 표현할 수 있다.

• 논리 선도

2.3 Switching Algebra

1. Commutative (교환 법칙) a + b = b + a ab = ba

2. Associative (결합 법칙) a + (b + c) = (a + b) + c a(bc) = (ab)c

3. Identity (항등원) a + 0 = a
   0 + a = a a · 1 = a 1 · a = a

4. Null (무효화) a + 1 = 1 1 + a = 1 a · 0 = 0 0 · a = 0

5. Complement (보수) a + a' = 1 a' + a = 1 a · a' = 0 a' · a = 0

6. Idempotency (등멱 법칙) a + a = a a · a = a

7. Involution (퇴화 법칙) (a')' = a

8. Distributive (분배 법칙) a(b + c) = ab + ac a + bc = (a + b)(a + c)

9. Adjacency (통합) ab + ab' = a (a + b)(a + b') = a a'b' + ab' + a'b + ab = 1 (a' + b')(a' + b)(a + b')(a + b) = 0

10. Simplification (간소화) a + a'b = a + b a(a' + b) = ab

11. DeMorgan (드 모르간의 법칙) (a + b)' = a'b' (ab)' = a' + b'

12. Absorption (흡수 법칙) a + ab = a a(a + b) = a

증명) a + ab = a · 1 + ab = a(1 + b) = a · 1 = a a(a + b) = a + ab = a

13. Consensus (컨센서스 법칙) at<sub>1</sub> + a't<sub>2</sub> + t<sub>1</sub>t<sub>2</sub> = at<sub>1</sub> + a't<sub>2</sub> (a + t<sub>1</sub>)(a' + t<sub>2</sub>)(t<sub>1</sub> + t<sub>2</sub>) = (a + t<sub>1</sub>)(a' + t<sub>2</sub>)

증명)
at₁ + a’t₂ + t₁t₂ = = at₁ + a’t₂ + 1 · t₁t₂ (identity) = at₁ + a’t₂ + (a+a’)t₁t₂ (complement) = at₁ + a’t₂ + at₁t₂ + a’t₁t₂ (distributive) = at₁ (1+t₂) + a’t₂ (1+t₁) (distribute) = at₁ · 1 + a’t₂ · 1 (null) = at₁ + a’t₂

14. ab + a'c = (a + c)(a' + b)

증명) ab + a'c = (ab + a')(ab + c) (distribute) = (a + a')(a' + b)(a + c)(b + c) (distribute) = 1(a' + b)(a + c)(b + c) (complement) = (a + c)(a' + b) (consensus)

- 표현의 단순화

논리 함수는 최대한 단순하게 표현한다.

AB + A'CD + A'BD + A'CD' + ABCD = AB + AB(CD) + A'C(D+D') + A'BD (교환 법칙, 분배 법칙) = AB + A'C + A'BD (흡수 법칙, 보수 법칙) = B(A + A'D) + A'C (분배 법칙) = B(A + D) + A'C (간소화)

- 드 모르간 법칙을 통한 보수화

F = wx'y + xy' + wxz F' = (w'+x+y')(x'+y)(w'+x'+z')

2.4 Canomical Forms 표준 형식

- Minterm

• x,y,z에 대한 minterms 곱으로 나타낸 모든 항

F<sub>1</sub> = m<sub>3</sub> + m<sub>5</sub> + m<sub>6</sub> + m<sub>7</sub> = x'yz + xy'z + xyz' + xyz → 1-minterms F'<sub>1</sub> = m<sub>0</sub> + m<sub>1</sub> + m<sub>2</sub> + m<sub>4</sub> = x'y'z' + x'y'z + x'yz' + xy'z' → 0-minterms

어떤 Boolean 함수라도 1-minterms의 합으로 표현할 수 있다.

ex) F<sub>1</sub> = ∑(3,5,6,7) F'<sub>1</sub> = ∑(0,1,2,4)

ex) F = x + yz = x(y+y')(z+z')+(x+x')yz =xyz+xyz'+xy'z+xy'z'+xyz+x'yz =xyz+x'yz+xyz'+xy'z+xy'z' =m<sub>7</sub> + m<sub>3</sub> + m<sub>6</sub> + m<sub>5</sub> + m<sub>4</sub> = ∑(3,4,5,6,7)

- Maxterm

• x,y,z에 대한 maxterms 합으로 나타낸 모든 항

ex) F<sub>1</sub>(x,y,z) = x'yz+xy'z+xyz'+xyz (F<sub>1</sub>)' = (x+y'+z')(x'+y+z')(x'+y'+z)(x'+y'+z') = M<sub>3</sub>M<sub>5</sub>M<sub>6</sub>M<sub>7</sub> = ∏(3,5,6,7)

F<sub>1</sub> = M<sub>0</sub>M<sub>1</sub>M<sub>2</sub>M<sub>4</sub>

ex) F = x'y'+xz =(x'y'+x)(x'y'+z) =(x+x')(x+y')(x'+z)(y'+z) =(x+y')(x'+z)(y'+z) =(x+y'+z)(x+y'+z')(x'+y+z)(x'+y'+z)(x+y'+z)(x'+y'+z) =(x+y'+z)(x+y'+z')(x'+y+z)(x'+y'+z) =M<sub>2</sub>M<sub>3</sub>M<sub>4</sub>M<sub>6</sub> =∏(2,3,4,6)

• Mintern 과 Maxterm은 서로 보수이다. f = m<sub>0</sub>+m<sub>1</sub>+m<sub>5</sub>+m<sub>7</sub> = M<sub>2</sub>M<sub>3</sub>M<sub>4</sub>M<sub>6</sub>

곱의 합 수식 sum of products(SOP) : 한 개 이상의 곱항들이 OR 연산자로 연결된 것.

합의 곱 수식 product of sums(POS) : 한 개 이상의 합항들이 AND 연산자로 연결된 것

디지털 시스템(Digital systems) : 임의 개수의 입력과 임의 개수의 출력이 있는 시스템. 데이터 입력 외에 클럭이라 불리는 타이밍 신호가 있는 경우도 있다.

디지털 시스템의 종류

1. 조합 시스템(Combinational Logic System) : 시스템 state 가 필요 없다. → Output = Function(Input)
2. 순차 시스템(Sequential System) : 시스템 state가 필요한 시스템, 기억 장치(메모리)가 있는 시스템 a) Synchronous Sequential System : state가 이산적으로 업데이트 되는 시스템. b) Asynchronous Sequential System : state가 연속적으로 업데이트 되는 시스템. → State = Function(State, Input) → Output = Function(State) || Function(State, Input)

디지털 시스템의 예시

1. Digital Counter Input : Count Up, Reset Output : Visual Display State : "Value" of stored digits → Asynchronous Sequential System (클락이 없기 때문에)

2. Digital Computer → Synchronous Sequential System (CPU라는 클락이 있기 때문에)

3. Embedded Systems 내장형 컴퓨터. 자동차, 스피커, 스마트폰, PC, TV 등등

1.2 진법에 대한 복습

1.2.1 Binary Value

디지털 시스템에선 정보를 전달하는 방법을 Binary Value 사용 연속적인 값 → 0 or 1

• Digital : 이산적인 값, 정수 값을 가짐
• Analog : 실수 값을 가짐, continuous in value & time Time : 주기적으로 발생하는 event, clock Asynchronous : clock과 비동기화, 시간 연속적, 값 불연속적 Synchronous : clock과 동기화, 시간&값에서 불연속적

1.2.2 Number System

$$ N = a_{n-1}r^{n-1}+a_{n-2}r^{n-2}+···+a_2r^2+a_1r+a_0$$ n : number of digits r : radix or base(밑) a<sub>i</sub> : coefficients(계수) (0 ≤ a<sub>i</sub> < r)

ex) $7642_{10}=7×10^3+6×10^2+4×10^1+2$ $101111_2=1×2^5+0×2^4+1×2^3+1×2^2+1×2^1+1\\quad \quad \quad ,,,, = 32+8+4+2+1=47_{10}$

10진수 : Demical number 2진수 : Binary number 8진수 : Octal number (3개씩 끊기) 16진수 : Hexademical number (09, AF / 4개씩 끊기)

1.2.3 정수의 음수 / 양수 표현법

Signed-Magnitude Representation : 부호-값 표현

→ 잘 사용되지 않는다

MSB : Most Significant Bit, 가장 중요한 비트, 부호를 표현

MSB 부호를 사용해 표현. Range : 0을 기준으로 대칭

$-(2^{n-1}-1)$ ~ $(2^{n-1}-1)$

→ 0 표현 방법이 2개 : +0, -0

2' Complement : 2의 보수 방법

→ 주로 이 방법을 사용한다

1. 음수일 때, 2진수로 변환
2. 보수를 취함 (0 → 1 / 1 → 0)
3. 1을 더함 (비트 한계를 넘어가는 값은 무시) Range : 음수가 1개 더 많음. 0이 1개이다.

   $-(2^{n-1})$ ~ $(2^{n-1}-1)$

1.2.4 이진수의 덧셈과 뺄셈

- 덧셈

각 자리 끼리 더함. 다음 비트에 대한 캐리까지 더한다.

오버플로우(Overflow) : 산술 연산의 결과가 정해진 범위를 벗어날 때

덧셈에서 서로 같은 부호를 더했는데 반대 부호가 나올 떄.

- 뺄셈

두 번째 피연산자에 대해 2의 보수를 취하고 두 수를 더하는 방식을 사용한다. a-b는 a + (-b) 와 같이 계산된다. 연산 과정중 오버플로우는 괜찮다.

1.3 BCD 코드

BCD(Binary Coded Decimal) : 이진코드 십진수

10진수를 표현하는 여러가지 방법들

1. 8421 code : 일반적인 이진법 코드
2. 5421 code : 첫 번째 비트가 5를 의미
3. 2421 code : 첫 번째 비트가 2를 의미
4. Excess 3 code : 3를 더한 값을 표시 (04, 59 보수 관계)
5. 2 of 5 code : 5개 비트 중 2개만 사용 → 에러 찾기 용이
6. 8,4,-2,-1 code : 각 비트가 8,4,-2,-1을 의미 (04, 59 보수 관계)

BCD 코드에서 덧셈의 오류 → 6을 더한다

• 용어 정리

  binary number ↔ decimal number : conversion decimal number ↔ BINARY CODE : coding

1.4 기타 코드들

1. Gray Code

• 일종의 채널 코딩. 숫자간 한 비트씩 차이남

2. Hamming Code

• Hamming 이 제작한 코드
• Single error correction code : error를 찾고 수정까지 할 수 있음
• 4개의 data bits, 3개의 check bits(a<sub>1</sub>, a<sub>2</sub>, a<sub>4</sub>)

Check bits a<sub>1</sub> = a<sub>3</sub> ⊕ a<sub>5</sub> ⊕ a<sub>7</sub> a<sub>2</sub> = a<sub>3</sub> ⊕ a<sub>6</sub> ⊕ a<sub>7</sub> a<sub>4</sub> = a<sub>5</sub> ⊕ a<sub>6</sub> ⊕ a<sub>7</sub>

Error Detecting bits e<sub>1</sub> = a<sub>1</sub> ⊕ a<sub>3</sub> ⊕ a<sub>5</sub> ⊕ a<sub>7</sub> e<sub>2</sub> = a<sub>2</sub> ⊕ a<sub>3</sub> ⊕ a<sub>6</sub> ⊕ a<sub>7</sub> e<sub>4</sub> = a<sub>4</sub> ⊕ a<sub>5</sub> ⊕ a<sub>6</sub> ⊕ a<sub>7</sub>

e는 모두 0이 나와야 한다. (자기 자신과 자기 자신의 XOR이기 때문) → 1이 나오면 오류

오류인 bit : 4e<sub>4</sub> + 2e<sub>2</sub> + e<sub>1</sub>

n의 check bit가 있다면, 2<sup>n</sup>-n-1개의 information bit가 있을 수 있다.

서론

이산구조란 무엇인가? 사실은 이산수학에 대한 내용이 대부분이다. Discrete 한 value들에 대한 연산, 구조, 내용들을 다룬다.

1. Basic Definition

명제(Proposition) : 참 또는 거짓 중 하나를 나타내는, 선언적 문장

의문문, 명령문, 감탄문 등은 참/거짓 판정이 불가하기에 명제가 아니다. x + 1 = 2 와 같은 명제는 값이 배정되지 않은 변수(x)가 존재하므로 명제가 아니다.

연산자(Operator) : 한 개 이상의 명제를 조합해주는 것

단일연산자(Unary) : 1개의 명제를 가짐 이항연산자(Binary) : 2개의 명제를 연결함(접속사)

논리 연산자

부정 : p가 명제가 하면 p의 부정(negation)은 ~p로 표기된다.

논리곱 : p, q가 명제면 p와 q의 논리곱(conjunction)은 p ∧ q로 표기된다. 이는 'p and q'를 의미한다.

논리합 : p, q가 명제면 논리합(disjuction)은 p ∨ q로 표기된다. 이는 'p or q'를 의미한다.

영어에서 or은 포괄적 논리합 / 베타적 논리합의 의미로 사용될 수 있다. 논리합 ∨은 포괄적 논리합에 대응한다.

여러 연산자가 같이 사용될 때

부정(~) 기호가 가장 높은 우선순위를 지닌다. ∧과 ∨이 동시에 사영될을 때는 ∧이 더 높은 우선순위를 지닌다. 그렇지만 괄호를 잘 사용해 헷갈릴 일이 없도록 하자.
베타적 논리합 : 베타적 논리합 : p, q가 명제면 p와 q의 베타적 논리합(disjunction)은 p ⊕ q로 표기된다. 이는 ‘p exclusive-or q’를 의미한다. 조건문(함축) : p, q가 명제면 p와 q의 조건문(implication)은 p → q로 표기된다. 이는 ‘if p, then q’를 의미한다. 이때 p를 가정, q를 결론이라고 한다.

가정이 거짓이면 항상 참임을 유의하자.

• p→q 의 영어 표현들
  • if p, q / q if p / if p, then q
  • p only if q / q provided that p
  • p is sufficient for q / q is necessary for p
  • p implies q / q is implied by p
  • when p, q / q when p / whenever p, q

조건문 p → q에 대해 역(converse) : q → p 이(inverse) : ~p → ~q 대우(contrapositive) : ~q → ~p

조건문 p→q가 참이라면, 대우 ~q → ~p도 항상 참이다.

상호 조건문 : p, q가 명제면 p와 q의 상호 조건문(biconditional statement)은 p ↔ q로 표기된다. 이는 ‘p if and only if(iff) q’를 의미한다.

비트(bit)와 비트 연산자

비트(bit) : binary digit. 0 또는 1로 구성된 이진수

• 0은 거짓, 1은 참을 의미한다.
• +은 'or'을 의미하고, · 은 'and'를 의미한다

비트 문자열 : 0개 이상의 비트를 갖는 비트열

2. Propositional Equivalence

동치(equivalent) : 두 개의 복합명제가 항상 같은 진리값을 가질 경우

항진명제(tautology) : 복합명제를 구성하고 있는 명제 변수가 어떠한 진리값을 갖는다 하여도 전체 복합 명제의 값이 항상 참일 때

모순(contradiction) : 복합명제를 구성하고 있는 명제 변수가 어떠한 진리값을 갖는다 하여도 전체 복합 명제의 값이 항상 거짓일 때

Equivalence Laws 동치 규칙들

항등 법칙 Identity : p ∧ T ≡ p / p ∨ F ≡ p

지배 법칙 Domination : p ∨ T ≡ T / p ∧ F ≡ F

등멱 법칙 Idempotent : p ∧ p ≡ p / p ∨ p ≡ p

이중 부정 법칙 Double negation : (p) ≡ p

교환 법칙 Commutative : p ∨ q ≡ q ∨ p / p ∧ q ≡ q ∧ p

결합 법칙 Associative : p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r / p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r

분배 법칙 Distributive : p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) / p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

드 모르간의 법칙 : ~(p∧q) ≡ ~p ∨ ~q / ~(p∨q) ≡ ~p ∧ ~q

부정 법칙 : p ∨ ~p ≡ T / p ∧ ~p ≡ F

흡수 법칙 : p ∨ (p ∧ q) ≡ p / p ∧ (p ∨ q) ≡ p

T는 항진 명제, F는 모순 명제

동치로 논리 연산자 정의하기

베타적 논리합 : p⊕q ≡ (p ∨ q) ∧ ~(p ∧ q)

조건문 : p → q ≡ ~p ∨ q / p → q ≡ p ∧ ~q

상호 조건문 : p ↔ q ≡ (p→q) ∧ (q→p)