Lecture 0

• Function
  • Library function : 시스템이 제공하는 Predefined function
  • User-defined functions : 프로그래머에의해 작성된 function
  • argument : 함수를 부르는 곳에서 괄호안에 들어있는 인자
  • parameter : 함수를 정의하는 곳에서 괄호안에 들어있는 매개변수
• Call by value & reference
  • Call by value
    • 인자의 값을 매개변수를 통해 전달받아 함수에서 사용하는 것
    • 함수에서 값을 변경해도 실제 넘겨받은 인자의 값은 변하지 않음
  • Call by reference
    • 인자의 주소를 매개변수를 통해 전달받아 함수에서 사용하는 것
    • 주소에 접근하는 것이므로 값이 변경됨
    • 매개변수에 포인터를 달아주고, 인자에 &를 붙여주어 사용
• Recursive Call
  • 재귀함수 → 종료조건을 잘 설정해주자
• Structures
  • Array vs Structure
    • Array → 모든 요소 같은 타입(인덱스 통해서 접근)
    • Structure → 다른 타입의 요소로 구성될 수 있음(변수 명을 통해 접근)
  • Structure tag를 통해 변수를 선언해주면 같은 구조체 타입이 됨
    • 같은 member로 구성되어도 각자 정의하여 선언하면 서로 다른 타입이라 =, ==, !=불가능
  • 구조체로 선언된 데이터 타입은 각 멤버들이 메모리에 순차적으로 할당됌
    • int → 4byte, char → 1byte, float → 4byte
• Pointer variable
  • 포인터 변수는 변수명은 같으나 변수선언을 할 때, *연산자를 사용한다.
    • int *a → int형 포인터 (포인터 변수는 타입과 상관없이 4바이트)
  • 포인터 주소할당문제 잘 확인하기!
• Array
  • 배열의 주소값 계산 : starting address + Offset-value(시작주소로부터 떨어진 거리)
• Stack
  • LIFO 늦게 넣은게 처음으로 나오는
  • Push : 요소 넣기, Pop : 맨위에걸 추출, 출력
• Queue
  • FIFO 처음 넣은게 처음으로 나오는
  • rear, front, addq, deleteq
  • circular queues
    • empty queue : 빈공간이 있는 원형 큐
    • Full queue : 빈공간이 없는 원형 큐
• Lists
  • Singly Linked Lists
    • Data part / Link part 존재
      • Data part : 값을 담고 있음 / Link part : 다음 노드의 주소를 가르킴
  • Doubly Linked Lists
    • Item part / Llink / Rlink 존재
      • Item part : 값을 담고 있음 / Llink : 이전 노드의 주소를 가르킴 / Rlink : 다음 노드의 주소를 가르킴

Lecture 1~2

• Algorithm 알고리즘
  • 입출력 관계를 잘 묘사하기 위해 만들어진 특정한 계산을 요구하는 절차이다.
• Running Time
  • Best case (Big - Ω, 빅오메가)
  • Worst case (Big - O, 빅오)
  • Average case (Big - Θ, 빅세타)
• Sorting 정렬

  • Insertion sort 삽입 정렬

    • In-place sorting → 입력을 제외하고 약간의 메모리공간만 사용하는 정렬(추가메모리x)
    • Stable 알고리즘 → 중복된 숫자가 있어도 그들의 위치가 변하지 않음
    • 2번째 자료부터 선택하여 앞에 정렬된 자료들과 비교하여 위치를 정하고 그 다음 자료를 또 비교하는 방식으로 정렬하는 방법

    

    • Running Time
      • Best case : T(n) = an + b(linear in n) = Θ(n) → 선형적이다 = 단순하다(모든 요소가 정렬되어있을때)
      • Worst case : T(n) = an^2 + bn + c.. = Θ(n^2)
        • Worst case에 집중하자! 왜?
          • 시간복잡도의 상한선(최대시간)을 제공해주고, 가장 종종 발생함
        • 러닝타임 계산은 식의 최고차항 차수를 보면 파악할 수 있음!(함수의 증가속도)

  • Merge sort 합병 정렬

    • Devide and Conquer 알고리즘 (분할정복), Stable 알고리즘
    • 주어진 자료들을 절반으로 계속 나누어 1개씩 분리될때까지 나누고 다시 병합하는 과정에서 투포인터로 정렬하면서 병합하여 정렬하는 방법
    • 재귀함수를 통해 구현됨 → 리턴값들을 메모리에 가지고 있으므로 메모리 효율성 낮다

    

    • Running Time
      • Devide + Conquer + Combine 시간을 합쳐야함
      • T(n) = aT(n/b) + D(n) + C(n)
        • D(n) → devide 시간 재귀함수로 한번 나누기만 하면 되므로 Θ(1) → 무시가능
        • C(n) → combine 시간 재귀함수로 합치려는 n개의 요소를 1번씩만 돌면 되므로 Θ(n)
          • 따라서 T (n) = 2T(n/2) + Θ(n)