자료구조 1-1강 | Introduction | 숙명여대 학점교류

학점교류로 수강하는 숙명여대 자료구조 계절학기 수업

 

Software and Data structure

 

- 시스템

ㄴ 소프트웨어

ㄴㄴ 알고리즘 : 문제를 해결하기 위한 명령어들의 모음

ㄴㄴ 데이터 : 값을 측정한 것의 모음

ㄴ 하드웨어

 

- Data structures

ways of, or structures for efficientyly processing and organizing

a large amount of data for solving problems 

 

: what to learn

- linear data structures : list, stack, queue, deque (데크?)

- non-linear data structures : tree, graph

- advanced DS : BST, weight Networks

- searching and sorting algorithms

 

 

algorithm

 

자료구조와 알고리즘이 연관성 높음

 

def)

a finite set of instructions -> 유한한 명령어들

for accomplishing a particular task

 

알고리즘과 프로그램의 차이는?

대표적으로 유한성이 있다. 

 

criteria)

input : no explicit input - 상관 없음

output : at least one output

definiteness : specific and unambiguous instructions 명확성

finiteness : terminates after finite steps 유한성 -> 일반적인 프로그램과의 차이점

effectiveness : without unusefulness, efficiently

 

description)

어떻게 문서화하는가? 

pseudo code, flow chart

natural language, programming language

 

system life cycle

소프트웨어 공학에서 많이 다루는 내용

시스템의 개발 주기

( Requirement -> analysis -> design -> implementation -> verification ) -> release

-> improve

 

- requirement - 문제

a set of specifications that define the objectives of a project

users, platform, functions, interface

 

- analysis - 모듈 단위로 분석

from one big project into smaller modules

== divide and conquer strategy

top-down approach 하향식

: build the hierarchy from the primary goal to components

: program -> (함수)subroutines -> (내부 명령어) instructions

button-up approach 상향식

: components comprises the entire system

 

- design - 어떤 것이 필요한지 설계

objects and functions for each module

설계하는 중

ex) 학사관리시스템이라고 하면, 여러 object 필요(학생, 강의실, 교수 등)

 

- implementation - 구현

write executable codes for objects and algorithms

ex) java, python, web 등

 

- verification - test 잘 동작하는지 검증

correctness proof of algorithms and program test

black box test : 입출력만 봄

white box test : 내부 코드를 함께 봄

 

- improve - 개선

 

- release - 배포

 

 

 

algorithm examples

- fibonacci numbers

def fibo(fb):
    a = 0
    b = 1
    fb.append(a)
    fb.append(b)
    while True:
        a, b = b, a+b
        if b > n: break
        fb.append(b)

n = 100000
fb = []
fibo(fb)
print(fb)
print("# of fibos", len(fb))

>>> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025]
# of fibos 26

 

(recursive 파트에서 다시 나올 것임)

 

- prime numbers

natural numbers that are greater than 1, and not divisible, except 1 or itself

fine all prime numbers between 2 and n

def find_prime(num):
    for i in range(2, num+1):
        prime = 1
        for j in range(2, i):
            if i%j == 0:
                prime = 0
                break
        if prime: prime_list.append(i)
        
prime_list = []
max_num=1000
find_prime(max_num)

for i in range(2, max_num):
    if i in prime_list: print('%3d' %i, end='')
    else:
        print('__', end=' ')
    if i%50 == 0: print()

print()
print('# of prime numbers = ', len(prime_list))

소수 탐색의 빈도

 

data type

- defa collection of objects and associated operations that act on those objects오브젝트와 정수 값에 대하여 연산자가 앞서 구현되어있다. 

 

- built-in data typesbasic type : char, int, floatcollection type : <sequence type> string, list, <collection type> tuple, set, dictionary 군집 자료형

 

파이썬은 list와 dictionary, string이 편리함

 

기본 자료형만으로는 부족한 점이 많다. -> ADT-> User defined data type

 

- abstract data type : ADTobject data type ( 파이썬은 class C는 struct, typedef?)

 

 

abstract data type

- object data type (ADT)

data type that abstracts objects of properties and operations (method, behavior)

attributes, member variables : 멤버 변수

methods(파이썬), member functions(C++) 

 

- object and instance (cf. Class)

개발자로 일할 때 ADT를 잘 기술할 수 있는 것이 매우 중요함

가독성을 높이고, 유지 보수를 용이하게 하기 때문임

Bank account : 계좌 번호, 주인, 등등

Student : 이수 학점, 등등

Fraction : 분수

 

- OOPL : Object Oriented Programming Language

C++

C#

Java

Python

이 중에 아주 숙달된 언어를 가지고 있어야 한다. !!

 

Example - Fraction

class Fraction:
    def __init__(self, up, down):
        self.num = up 
        self.den = down
    def __str__(self):
        return str(self.num)+"/"+str(self.den)
    
    # private method
    def __add__(self, other):
        new_den = self.den * other.den
        new_num = self.den * other.num + self.num * other.den
        common = self.gcd(new_den, new_num)
        return Fraction(new_num//common, new_den//common)
    def multiply(self, other):
        new_den = self.den * other.den
        new_num = self.num * other.num
        common = self.gcd(new_den, new_num)
        return Fraction(new_num//common, new_den//common)
    def gcd(self, a, b):
        while a % b != 0:
            a, b = b, a % b
        return b
    
    #implement 
    
def fraction_example():
    num1 = Fraction(1, 4)
    num2 = Fraction(1, 2)
    num3 = num1 + num2
    print(num1, "+", num2, "=", num3)
    num1 = Fraction(2, 3)
    num2 = Fraction(4, 5)
    num3 = num1 + num2
    print(num1, "+", num2, "=", num3)
    num1 = Fraction(2,5)
    num2 = Fraction(3, 8)
    num3 = num1.multiply(num2)
    print(num1, "*", num2, "=", num3)
    num1 = Fraction(3,4)
    num2 = Fraction(2,9)
    num3 = num1.multiply(num2)
    print(num1, "*", num2, "=", num3)    
    
fraction_example()

 

class에서 __add__ method는 __init__과 같이 특별한 method

# shape.py

class Shape:

    area = 0

    def __add__(self, other):
        return self.area + other.area

 

a + b로 __add__ 클래스를 자동으로 실행해준다

>>> a = shape.Shape()
>>> a.area = 20
>>> b = shape.Shape()
>>> b.area = 10
>>> a + b
30

7.5. 특별한 메서드들

__str__ method는

출력 형식을 지정해준다. 

str 메서드
클래스 자체의 내용을 출력하고 싶을 때(init에서 규정한),
형식을 지정하는 메서드