Created by potrace 1.16, written by Peter Selinger 2001-2019 J 『NOTE』

01. Introduction

  • J 『宋』

Definitions

Data
  • Data는 정보의 전달자

  • Data는 객관적인 것을 설명하는 데 사용할 수 있는 숫자, 문자 및 기타 기호들의 집합

  • Data는 두 개의 클래스로 나뉠 수 있음 :
    1. numerical data : int, float, complex, …
    2. non-numerical data : character, string, graph, voice …
Data structure

  • 데이터를 어떤 구조로 저장하고, 탐색하고, 삭제해야 가장 효율적일까?

  • 어떻게 메모리를 가장 효율적으로 사용할 수 있을까? :arrow_right: 실행속도 영향

  • Data structure는 하나의 Data object 및 그 object 를 구성하는 Data member 간의 관계

  • Data structure = {D,R}

    • D : Data object
    • R : D에 있는 모든 Data member들의 제한된 관계 집합

  • Data structure에는 세 가지 측면을 포함함

    1. Data의 논리적인 구조 : 从用户视图看，是面向问题的
    2. Data의 물리적인 구조 : 从具体实现视图看，是面向计算机的
    3. 관련된 동작 및 구현

  • Data structure의 분류

    data-structure

Data type

  • Data Type은 value의 집합과 이 value들을 조작하는 operation의 집합이 같이 있음

    Example. int

    • Value set = {…, -2,-1,0,1,2, …}

    • Operation set = { +, -, *, /, %, … }

  • 대부분의 프로그래밍 언어는 미리 정의된 Data type들을 제공함.

    • Atom data type : int, float, double, …
    • Structure data type : array, struct, …
Abstract Data Types (ADT)

  • Abstract : 정보를 숨기기 위해 사용되는 방법

  • Abstract Data Types : Type들과 그 Type들에 대한 연산들을 명기한 것

    Example.

    ADT NaturalNunber is
	objects:
		0 ~ MAX_INTEGER
	Function:
		Zero( ):NaturalNumber
		IsZero(x):Boolean
		Add(x,y):NaturalNumber
		Equal(x,y):Boolean
		Successor(x):NaturalNumber
		Subtract(x,y):NaturalNumber
  		
end NaturalNumber
Algorithm
  • Algorithm은 문제 해결의 Operation 순서
    • 포함되어야 되는 특징들 : finite, deterministic, initial action, sequence ends

Mathematics Review

Series

Screen Shot 2021-08-13 at 4.08.28 PM

Screen Shot 2021-08-11 at 3.25.57 PM

Modular Arithmetic

  • A is congruent to B modular N

    • A ≡ B ( mod N), if N divides A-B

    Example. 81 ≡ 61 ≡ 1 (mod 10)

Recursion

  • Recursion의 두 가지 기본 규칙 :
    1. Base cases 정의
    2. progress 만들기
  • Direct Recursion : a function calls itself
  • Indirect Recursion : the function f1 calls another function f2 and f2 calls f1

Example. Computes the sum of the elements a[0] through a[n-1]

public static int Rsum(int[] a , int n) {
  if (n>0)
		return Rsum(a,n-1)+a[n-1]; 
  return 0;
}

Rsum(a,4) 의 경우 동작 과정 :

Screen Shot 2021-08-11 at 3.38.08 PM

Example. Hanoi tower problem

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것

[1] 한 번에 하나의 원판만 옮길 수 있다.

[2] 큰 원판이 작은 원판 위에 있어서는 안 된다.

Tower_of_Hanoi_4_alt1

import java.io.*;

public class TowersOfHanoi {
    public static void moveDisk(int n, char fromTower, char toTower, char auxTower){
        if(n==1){
            System.out.println("move disk "+n+" from "+fromTower+" to "+toTower);
        }else{
            moveDisk(n-1, fromTower, auxTower, toTower);
            System.out.println("move disk "+n+" from "+fromTower+" to "+toTower);
            moveDisk(n-1, auxTower, toTower, fromTower);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader( new InputStreamReader ( System.in ) );
        System.out.println("Enter number of disks");
        int n = Integer.valueOf(in.readLine());
        System.out.println("The moves are :");
        moveDisk(n, 'A', 'B', 'C');
    }
}

Exercise

  1. Write a recursive method that returns the number of 1 s in the binary representation of N. Use the fact that is equal to the number of 1 s in the representation of N/2, plus 1, if N is odd.

    public int count(int n){
  if(n==1){
    return 0;
  }else{
    return n%2 + count(n/2)
  }
}

  2. Write the routines wise the following declarations :

    public void permute( String str );

    private void permute( char[] str, int low, int high )

    The first routine is a driver that calls the second and prints all the permutations of the characters in String str. If str is “abc”, then the strings that are output are abc, acb, bac, bca, cab,and cba. Use recursion for the second routine.

        public void permute (String str){
        permute(str.toCharArray(), 0, str.length());
    }
   
    private void permute (char[] str, int low, int high){
        if(low == high){
            System.out.println(str);
        }else{
            for(int i=low; i<high; i++){
                str = swap(str, low, i); // i번째 index의 character를 가장 1번째 위치에 두기
                permute(str, low+1, high);
                str = swap(str, low, i); // i번째 index의 character를 원위치로
            }
        }
    }
   
    private char[] swap(char[] str, int index1, int index2){
        char temp = str[index1];
        str[index1] = str[index2];
        str[index2] = temp;
        return str;
    }

    💁🏻 permute( {'a','b','c'}, 0, 3 ) 일 때, Recursion 부분 동작 방식

            for(int i=0; i<3; i++){
            char temp = str[0];
            str[0] = str[i];
            str[i] = temp;
            for(int j=1; j<3; j++){
                char temp2 = str[1];
                str[1] = str[j];
                str[j] = temp2;
                for(int k=2; k<3; k++){
                    char temp3 = str[2];
                    str[2] = str[k];
                    str[k] = temp3;
                    System.out.println(str);
                    temp = str[2];
                    str[2] = str[k];
                    str[k] = temp;
                }
                temp2 = str[1];
                str[1] = str[j];
                str[j] = temp2;
            }
            temp = str[0];
            str[0] = str[i];
            str[i] = temp;
        }

  3. 已知a[n]为整型数组，试写出实现下列运算的递归算法。

    • 求数组a中的最大整数

      // n : a.length
// a[n] 원소를 a[n-1], a[n-2], ... , a[0] 순서로 하나씩 원소를 비교하면서 최댓값 구함   
public int findMax(int[] a, int n) {
        if(n==1){
            return a[0]; 
        }else{
            int temp = findMax(a, n-1);
            return temp > a[n-1] ? temp : a[n-1];
        }
}

    • 求n个整数的平均值

      public double getAverage(int[] a, int n) {
        if(n==1){
           return a[0]; 
        }else{
           return (getAverage(a, n-1)*(n-1) + a[n-1]) / n;
        }
}

《Reference》

  1. 2016年 数据结构与算法 : 汤恩义
Search