3.1 스택

삽입, 삭제가 top에서만 이루어진다.

LIFO(Last In First Out)

* 시스템 스택: 프로그램이 런타임에 함수 호출 시 사용

처음 top을 -1로 정해 빈 스택 확인

3.1.1 추상자료형

생성

삽입, isFull: 스택이 가득 찼는지 확인한 후 삽입

삭제, isEmpty: 스택이 비어있는지 확인 후 삭제

push(item);
item = pop();

3.2 동적 배열을 이용한 스택

위의 방식처럼 MAX_STACK_SIZE를 통해 스택을 생성하는 경우 최적의 크기를 알아야 한다는 결점 -> 동적 할당된 배열을 통해 해결

처음 스택의 크기를 1로 설정하여 배열 생성

스택이 가득 차있는 경우 realloc( )을 이용하여 기존 스택의 크기를 2배로 증가

: 시간 비용이 많이 드는 것처럼 보이지만 아니다!

​ => 메모리 할당에 O(1), 스택 원소 복사에 O(1)의 시간 복잡도가 요구된다는 가정하에 O(스택_크기)의 시간 복잡도(스택 크기는 2의 멱수)

​ => 2^k^의 원소에 대한 총 시간 복잡도 다음과 같다.
$$
{O(\sum\limits_{i=1}^{k}2^i)} = O(2^{k+1}) = O(2^k)
$$

3.3 큐

삽입과 삭제가 다른 끝에서 발생하는 리스트

삽입되는 끝: rear

삭제되는 끝: front

스택에서는 top만 이용하는 것과 달리 rear, front 2개의 변수 사용

* 작업 스케줄링: 우선순위를 사용하지 않는 OS에서 작업을 들어오는 순서대로 처리

​

3.3.1 추상자료형

생성

삽입, isFull: 큐가 가득 찼는지 확인 후 삽입

삭제, isEmpty: 큐가 비었는지 확인 후 삭제

rear가 MAX_QUEUE_SIZE-1가 됐을 때(큐가 가득 찼을 때), 전체 큐를 이동시켜 front가 -1이 되도록 이동 -> 비용 多

=> 원형 큐를 이용해 해결: (MAX_QUEUE_SIZE-1) + (1) = (0), (0) - (1) = (MAX_QUEUE_SIZE-1) : 모듈러 연산 이용

​ * 원형 큐의 문제점: 큐가 가득 차거나 비어있을 때 모두 rear == front, 구분 불가

​ => 큐가 가득 차기 직전에 큐의 크기를 늘려서 rear == front인 상황이 비어있는 경우만 존재하도록 제한

3.4 동적 할당 배열을 이용한 원형 큐

realloc을 이용해 배열의 크기를 2배로 만들고 추가적인 작업 필요

[0]	[1]	[2]	[3]	[4]	[5]
C	D	E		A	B

front = 3, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
C	D	E		A	B

front = 3, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
C	D	E								A	B

front = 9, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
A	B	C	D	E

front = 11, rear = 4

1. 새로운 큐 newQueue 생성
2. 뒷부분에 해당하는 queue[front+1]부터 queue[capacity-1]까지를 newQueue[0]부터 newQueue[capacity-front-2]에 복사
3. 앞부분에 해당하는 queue[0]부터 queue[rear]까지를 newQueue[capacity-front-1]부터 newQueue[capacity-front-1+rear]에 복사

3.5 미로 문제

3.6 수식 계산

3.6.1 수식

연산 순서를 결정하는 상위 계층 존재

안쪽 괄호 먼저 계산

C에서의 연산자 순서

1. ->

   ( ): 함수 호출

   [ ]: 배열

   ->, .: 구조체 또는 공용체 멤버

2. ->

   --, ++: 후위 연산자

3. <-

   --, ++: 전위 연산자

   !: not

   ~: 보수

   , +: 단항(부호)

   &, *: 역참조, 참조

   sizeof: 크기(바이트 단위)

4. <-

   (type): typecast

5. ->

   *, /. %: 곱

6. ->

   +, -: 합, 차

7. ->

   <<, >>: shift

8. ->

   >, =>, <, <=: 비교

9. ->

   ==, !=: 등위

10. ->

    &: 비트연산자 and

11. ->

    ^: 비트연산자 xor

12. ->

    |: 비트연산자 or

13. ->

    &&: 논리연산자 and

14. ->

    ||: 논리연산자 or

15. <-

    ?:: 조건연산자

16. <-

    =, +=, -=, /=, %=, <<=, >>=, &=, ^=, |=: 할당

17. ->

    ,: 콤마

3.6.2 전위식

대부분의 컴파일러가 사용하는 수식

계산 시 왼쪽에서 오른쪽으로 스캔

연산자를 만날 때까지 스택에 피연산자 삽입

연산자를 만나면 스택에서 필요한 피연산자를 삭제 후 계산 결과를 삽입

* 입력받은 숫자가 ASCII 값이기 때문에 '0'을 빼서 원하는 값을 갖도록 한다. ex ) '1' - '0' = 1

** 호출되는 함수에서 case문을 사용 시 각 케이스에 return을 사용하면 break 불필요

3.6.3 중위식 -> 전위식

1. 수식의 모든 계산에 괄호
2. 연산자를 닫는 괄호로 이동
3. 괄호 제거

스택을 이용한 수식 전환

괄호가 없는 식

피연산자는 즉시 출력

연산자를 만나면 top에 있는 연산자와 비교하여 우선순위가 낮을 때까지 pop한 후 push

수식의 끝에 도달했을 때 스택이 비어있지 않다면 모두 pop

괄호가 있는 식

위와 동일한 방식으로 진행하되 닫는 괄호가 나올 경우 여는 괄호까지의 연산자 pop

여는 괄호는

• 스택 내부에서의 우선순위(isp)는 가장 낮아야 하고 - 스택에 들어간 이후 다른 토큰이 스택에 들어갈 수 있기 때문
• 삽입 시 우선순위(icp)는 가장 높아야 한다. - 입력 시 반드시 스택에 들어가 위해

분석: O(n)

* 중위식 -> 후위식

1. 입력된 문자열 뒤집기
2. 뒤집어진 문자열을 전위식으로 정리
3. 전위식 뒤집기

3.7 다중 스택과 큐

• m의 메모리에 n개의 스택을 사용하는 경우

  공간을 n등분하여 boundary로 구분 (# of boundary = n+1)

  • top[i] == boundary[i+1]: stackFull
  • top[i] == boundary[i]: stackEmpty
• 다른 스택에 여유 공간이 있는데 꽉 찬 스택(i)에 삽입이 발생하는 경우
  1. 사용하지 않고, i < j < n을 만족하는 최소의 j를 찾아 i+1부터 j까지 오른쪽으로 한 스택씩 이동
  2. 1로 해결되지 않은 경우, 사용하지 않고, 0 <= j < i를 만족하는 최대의 i를 찾아 0부터 i까지 왼쪽으로 한 스택 씩 이동
  3. 2로 해결되지 않은 경우, stackFull

worst case: O(MEMORY_SIZE)

* 단어

• shortcomming 결점
• * This is not the case 사실이 아니다
• intriguing 흥미로운
• precedence 상위
• mnemonics 기억술
• auxiliary 보조적인
• empirically 경험적으로
• futile 쓸모없는

2.1 배열

2.1.1 추상자료형

대부분의 언어가 제공하는 배열의 표준연산: 생성, 검색, 저장

2.1.2 C에서의 배열

배열의 첫 원소의 주소를 base address라고 한다.

int list[5]에서의 base address는 list[0]의 주소
list[i]의 주소는 base address + i*sizeof(int)
(list2+i) = &list2[i], *(list2+i) = list2[i] (자료형의 크기를 곱하지 않는다.)

2.2 동적 할당 배열

2.2.1 1차원 배열

배열의 크기를 매우 크게 정하면
프로그램이 실행 시간에 실패하는 가능성은 떨어지지만,
메모리 부족으로 인해 컴파일에 실패할 가능성 증가

2.2.2 2차원 배열

할당

int **list;

MALLOC(list, rows*sizeof(*list));
// list = (int **)malloc(rows*sizeof(*list));
for(int i = 0; i < rows; ++i)
    MALLOC(list[i], cols*sizeof(**list));
    // list[i] = (int *)malloc(cols*sizeof(**list));

해제

for(int i = 0; i < rows; ++i)
    free(list[i]);
free(list);

calloc: 할당 후 0으로 초기화
realloc: 크기 조정

2.3 구조체와 공용체

2.3.1 구조체

cf ) 배열 - 동일 자료형
필드(멤버)로 구성
멤버 연산자 '.'
typedef 사용
패딩비트 사용

typedef struct _Human{
    char name[10];    // char pad[2]; 패딩비트
    int age;
    float salary;
} Human;

sizeof(Human);    // 20 ( 패딩비트 )

구조체의 대입 연산은 가능하지만 비교 연산은 불가능 // 비교 연산 시 각각의 멤버 변수에 대해서 비교
구조체 멤버로 구조체 사용 가능

2.3.2 공용체

공용체의 필드는 메모리 공간 공유 -> 한 필드만 주어진 시간에 기능을 한다.
크기는 가장 큰 필드의 크기
구조체와 같이 패딩비트 사용

union {
    char name[10];
    int age;
} info;

sizeof(info);    // 12 ( sizeof(name) > sizeof(age), 패딩비트 )

2.3.3 자기 참조 구조체

하나 이상의 멤버가 자신의 포인터인 구조체

typedef struct _List *ListPointer;
typedef struct _List{
    char data;
    ListPointer link;
} List;

2.4 다항식

2.5 희소행렬

2.6 다차원 배열의 표현

다차원 배열을 표현할 때 배열의 배열 꼴이 아닌 선형 리스트의 1차원 배열과 같은 꼴로 나타내는 경우 주소 공식이 복잡해진다.
다차원 배열 a[upper_0][upper_1][upper_2]...[upper_n-1]의 element 수: upper_0*upper_1*upper_2*...*upper_n-1

본 책에서는 다차원 배열의 표현법인 row major order와 column major order 중 row major order만 고려

A[upper_0][upper_1]은 upper_0줄이 각각 upper_1개의 element를 가지고 있는 형태이므로

A[0][0]의 주소를 a라고 할 때, A[i][0]의 주소는 a+i*upper1, A[i][j]의 주소는 a+i*upper_1+j

B[upper_0][upper_1][upper_2]는 upper_0 개의 upper_1*upper_2 2차원 배열로 구성된 형태이므로
B[0][0][0]의 주소를 b라고 할 때, B[i][0][0]의 주소는 b+i*upper1*upper2, B[i][j][k]의 주소는 b+i*upper_1*upper_2+j*upper_2+k

일반화하여, C[upper_0][upper_1]...[upper_n-1]에서
C[0][0]...[0]의 주소를 c라고 할 때,
C[i_0][i_1]...[i_n-1]의 주소는 c+sigma{j=0

n-1}(i_j*a_j), a_j = pi{k=j+1

n-1}(upper_k)

2.7 문자열

2.7.1 추상자료형

생성, 읽기 or 출력, 합성(연쇄), 비교, 삽입, 삭제, 찾기

2.7.2 C에서의 문자열

끝이 널문자(\0)로 끝나는 문자 배열

char s[100] = {"dog"};
// vs
char s[] = {"dog"};

strcat(s, t)를 호출했을 때, s에 t를 추가할 공간이 없다면 overwrite될 가능성 존재

* 참고: http://www.jbox.dk/sanos/source/lib/string.c.html
\ strspn에서의 control map의 비트를 설정하는 부분이 이해가 되지않는다.

insert = strncpy -> strcat -> strcat

2.7.3 패턴 매칭

strstr으로 가능

가장 쉬운 방법은 각 문자에 대해서 순차적으로 비교: O(nm)의 계산 시간 필요
비교하는 문자열의 길이를 고려하는 것으로 1차 개선
첫, 끝 글자를 비교하여 2차 개선
2번의 개선하더라도 최악의 경우에는 O(nm)의 계산 시간 필요

KMP 알고리즘의 계산 시간은 O(n+m)
\ KMP 알고리즘

* 단어

• sparse 부족한
• consecutive 연속적인
• retrieve 검색하다
• bracket 대괄호
• abbreviate 줄여 쓰다
• retrieve 검색하다
• stipulation 약정

Java와의 차이점

• 함수 선언 시 'fun' 키워드 사용  ex ) fun main( )
• 파라미터 이름 뒤에 파라미터 타입을 쓴다.  ex ) args: Array<String>
• 문장 끝에 세미콜론(;) 생략 가능
• 클래스 상속 표현 시 콜론(:) 사용
• 함수의 반환 값이 없는 경우 'void' 생략

코틀린의 안드로이드 확장 플러그인이 제공하는 기능

• View Binding : XML에서 만든 UI 요소를 findViewById( ) 없이 접근
• parcelable : 객체를 직렬화

TextView를 사용할 때 변경하거나 이벤트를 처리할 필요가 없는 고정적인 UI 요소는 ID 신경 쓸 필요 X

  cf ) 다른 UI를 기준으로 해당 UI를 배치하는 경우 ID를 의미 있는 이름으로 바꾸는 것이 좋다.

setContentView( ) : UI로 사용할 레이아웃 XML 파일 지정

안드로이드 UI가 XML 리소스로 분리되어 있는 이유 : 재사용

Activity 간 화면 전환을 위해 Intent 클래스 사용

startActivity(Intent(this@MainActivity, ~Activity::class.java)) : Intent로 ~Activity를 타겟으로 지정하고 startActivity로 시작

Activity 화면 상단에 나타나는 타이틀은 Activity의 Label 값으로 기본 설정, 매니페스트 파일에서 설정

findViewById( )는 자원 소모가 큰 함수 -> 많이 호출하면 성능면에서 안 좋은 패턴

Third Party Library : 제품을 제조하는 원래 회나 이외의 기업에서 개발한 라이브러리

※ Parcelable : 클래스를 액티비티 간에 한 번에 전달되고 받아볼 수 있도록 해주는 것

System.currentTimeMillis( ) : 현재 시간을 밀리세컨드 단위로 정수 형태로 리턴 ( long형 )

SimpleDateFormat zmffotm : 시간 관련된 텍스트를 포맷화

객체 지향 언어에서는 객체의 상태에 따라 함수에 입력된 조건이 같아도 결과가 달라진다.

  -> 단점 : 결과 예측이 어렵다 = 문제 발생 시 대처하기 어렵다 -> 대체제 : 함수형 프로그래밍 - 불변성 중요

변수 선언

var : 변경 가능한 참조 변수

val : 변경 불가능한 참조를 저장하는 변수, 초기화 후 재 대입 불가

변수를 불변으로 선언할 경우 메모리, 멀티쓰레드 안전성, 함수형 코드 등의 이점 존재 -> 필요한 경우에만 var 권장

변수의 타입 추론

  - 정적 타입 언어 : 컴파일 시점에 타입을 결정  cf ) 동적 타입 언어 : 런타임 시점에 타입 결정

  장점 : 컴파일 시 타입 캐스팅 문제 확인 가능, 실행이 빠르다.

  단점 : 변수 선언 시 반드시 타입을 적어야 한다.

  스마트 캐스팅 : 변수의 타입을 체크한 경우 블록 내에서 타입 캐스팅이 자동으로 되는 것

    -> 코드를 간결하게 하고, 실수를 줄여준다.

* 최상위 클래스 Object / Any : 모든 클래스로 캐스팅 가능 -> 다형성 측면에서 편리

조건문

  if/else 는 자바와 동일

  when( cf. java - switch)

// Java

switch(number){
    case 1:
    case 2:
    case 3:
    case 4:
        {A}
        break;
    case 9:
    case 11:
        {B}
        break;
    default:
        {C}
        break;
}


// Kotlin

when(number){
    in 1..4 -> {A}
    9, 11 -> {B}
    else -> {C}
}

  코틀린에서는 break를 넣지 않아도 해당되는 케이스만 실행된다.

  케이스의 코드가 2줄 이상이면 중괄호로 감싼다.

  'in' 키워드를 사용하면 '..' 기호를 사용해 범위를 지정할 수 있다.

  또, ','를 사용할 수도 있다.

반복문

  for

// Java
String[] array = {"apple", "banana"};
for (String item : array){
    System.out.println(item);
}



// Kotlin
val collection = mutableListOf<String>("apple", "banana")
for(item in collection){
    println(item)
}

for(i in 0..100){
    println(i)
}

for((index, value) in collection.withIndex()){
    println("$value at $index")
}

* collection이 val로 선언되었기 때문에 add를 통한 추가는 가능하지만 reassign은 불가능

  while / do~while

  while문은 자바와 동일

  do~while문에서 조건식에 do 블럭 내부 변수에 접근 가능

do{
    val y = retrieveData()
}while(y!=null)

  break / continue

  레이블 : 'break' 또는 'return' 이후 어떤 블럭을 빠져나가는지 알 수 있다.

loop1@ while(true){
    var x = retrieveData()
    if(x == null) break@loop1
    else{
        loop2@ while(true){
            var y = getData()
            if(y == null) break@loop2
        }
    }
}


// 중첩 반복문

loop@ for(i in 1..100){
    for(j in 1..100){
        if(~) break@loop
    }
}

continue는 자바와 동일

함수

  선언 : 'fun' 키워드 사용

// Java
public void function1(int age){
}

public int function2(int age){
    return 0;
}


// Kotlin
fun funtion1(age:int){
}

fun function2(age:int):int{
    return 0
}

* 코틀린에는 'void'와 같은 형태로 'Unit' 타입이 있는데 생략 가능

  정적 유틸리티 클래스 : 객체 상태 정보가 없고, 정적 함수만 제공하는 클래스

    자바에서는 모든 함수가 클래스 내부에 있어야 하기 때문에 연관성이 없는 클래스 객체를 new로 생성하여 호출 시 효율성과 직관성이 떨어지기 때문에 사용

  Kotlin의 최상위 함수

    클래스 외부에 있는 함수

  Java에서 Kotlin 최상위 함수 사용

    코틀린과 자바는 100% 상호 호환 -> 코틀린의 최상위 함수는 컴파일 단계에서 자동으로 새로운 클래스에 포함

    '@file:JvmName'을 활용하여 접근하는 클래스 이름 변경 가능

  Java 함수의 디폴트 파라미터

    메소드 오버로딩으로 해결

    * 파라미터의 수가 많아짐에 따라 같은 메소드가 오버라이딩 되는 횟수가 증가하는 단점이 있다.

  Kotlin 함수의 디폴트 파라미터

    * Java 컴파일러는 코틀린의 파라미터 기본값 처리 불가 => 어노테이션 기능 사용(@JvmOverloads)

  함수의 이름 붙인 인자

    함수 호출 시 인자 이름을 사용하여 가독성 향상

# 버전 선택 : 버전마다 지원되는 요소가 다 다르지만 다 숙지하는 데는 어려움이 있다. -> 점유율을 참고할 수 있다.

프로젝트 구조

manifests : 환경설정 파일 및 메타 정보 파일

• allowBackup : 앱 데이터 백업, 복원 여부 (Default : true)
• icon : 앱 아이콘과 구성 요소에 대한 기본 아이콘
• label : 사용자가 읽을 수 있는 레이블과 구성 요소에 대한 기본 레이블
• roundIcon : 원형 아이콘이 적합한 경우 원형 아이콘 사용
• supportsRtl : 오른쪽에서 왼쪽으로 레이아웃을 지원할지 여부 ( Default : false)
• theme : 기본 테마 스타일, Activity 마다 다르게 설정 가능

java : 실제 코드 부분, 유닛 테스트(기능별 테스트)를 지원하기 때문에 3가지

res : layout : 화면의 UI를 담당하는 레이아웃 리소스

• layout : 화면의 UI를 담당하는 레이아웃 리소스
• mipmap : 애플리케이션 아이콘 등 이미지
• values : 문자열, 컬러

Gradle Scripts : 앱의 설정 정보, 기타 앱이 의존하는 라이브러리 정보

# import 과정에서 매번 [ Alt + Enter ]로 진행하는 것이 불편하기 때문에 Settings에서 Auto Import를 활성화한다.

컴파일 vs 빌드

• 컴파일 : 통역
• 빌드 : 컴파일 + 링킹 + 로드

  - 링킹 : 여러 개의 코드로 분리된 기능들을 취합하는 과정

  - 로드 : 실제로 메모리에 올리는 것

주석

• java 주석 : 한 줄 - "//", 여러 줄 - "/*" ~ "*/"
• javaDoc 형식의 주석 : "/*" ~ "*/", 도움말로 참조 가능
• XML 주석 : "<!--" ~ "-->"

진입점

안드로이드는 단일 진입점이 없다. cf) Java, C, C#의 main

4대 컴포넌트가 진입점 역할

• Activity :화면에 포커싱 되어 사용자와 상호 작용
• Service : 백그라운드에서 실행되는 구성 요소, 사용자 UI 제공 X
• BroadCast Receiver : 시스템 변경 사항 알림
• Content Provider : 데이터 공유

#안드로이드 런처 : 안드로이드의 홈 화면을 담당하는 특수한 앱, 'Home' 키를 누르면 복귀하는 앱

코드의 재사용성과 유지/보수

클래스 vs 인스턴스

• 클래스 : 객체를 위한 설계도
• 인스턴스 : 설계도(Class)를 통해 생성된 실제 객체

캡슐화

  - 객체의 내부 정보를 외부로부터 은닉하는 것

• 내부의 복잡한 로직을 숨겨 외부에서 기능을 사용에 용이하게 한다.
• 내부의 주요 속성들을 외부로부터 보호

* 접근 지시자 : 캡슐화를 지원하기 위해 존재

• public : 프로그램의 모든 위치에서 액세스 가능
• protected : 동일한 패키지 또는 다른 패키지의 서브 클래스에서만 액세스 가능
• default : 동일한 패키지에서만 액세스 가능
• private : 자신의 클래스에서만 액세스 가능, 클래스나 인터페이스는 불가

  필드에서도 public을 사용하여 외부에서 접근할 수 있지만 외부에서 객체의 속성에 직접 접근 가능해지기 때문에 캡슐화 원칙이 지켜지기 어렵다. -> 외부와의 상호 작용은 public 메소드 사용을 권장

상속

  - 다른 클래스의 기능을 그대로 사용하면서 자신만의 기능을 추가하는 확장의 개념

• 메소드 오버 로딩 : 같은 기능을 하지만 입력받는 파라미터의 자료형이 다를 때 사용
• 메소드 오버 라이딩 : 상속에서 부모가 제공한 기능을 그대로 쓰지 않고 바꿔서 사용하는 것

라이브러리

  - 개발의 생산성 향상을 위하여 자주 사용하는 기능을 여러 곳에서 사용할 수 있도록 묶은 것

  - bulid.gradle에서 dependencies에 의존성이 있는 라이브러리를 적는다.

프레임워크

  - 라이브러리처럼 자주 사용하는 기능을 묶어 개발 생산성 향상을 목적으로 한다.

  - 공통적인 부분은 상위 클래스에서 구현, 추가 구현 부분은 하위 클래스의 Callback을 호출

※ 라이브러리 vs 프레임워크 : 코드 흐름의 제어권

•   라이브러리 : 앱 흐름을 직접 제어
•   프레임워크 : 앱 코드가 프레임워크에 의해 사용된다.

Callback 함수

  - 외부에서 불려지는 함수 (직접 호출 X)

책 링크

안드로이드 공부를 시작하는데 자바와 코틀린으로 쓰여진 프로젝트 실습을 할 수 있는 책을 찾다가 구매했다.

1.1. 시스템 생명 주기

1.1.1 요구사항

모든 대형 프로그래밍 프로젝트는 프로젝트의 목적을 정의한 명세로부터 시작
입력과 출력에 대한 정보

1.1.2 분석

접근법 : 상향식(bottom-up), 하향식(top-down)

• 상향식 : 프로그래머의 master plan 없음 -> 각 프로그램의 연관이 적고, 에러를 발생시키는 부분 많다.
• 하향식 : 최종 제품을 관리할 수 있는 부분으로 나눔, 문제에 대한 대안책을 개발하고 비교하는 단계

1.1.3 설계

프로그램에 필요한 데이터 오브젝트와 동작 관점에서 접근

• 데이터 오브젝트 관점 : ADT(추상 데이터 타입)
• 동작 관점 : 알고리즘과 알고리즘 설계 전략

1.1.4 구현

데이터 오브젝트 표현 방법 선택, 관련된 효율적인 알고리즘 결정

1.1.5 검증

• 정확성 증명 : 증명은 시간이 오래 걸리고 어려움 -> 증명된 알고리즘을 선택하여 에러 감소

  코딩 전 또는 중간에 가능

• 테스트 : 동작하는 코드와 테스트 데이터 필요, 테스트 데이터는 모든 가능한 케이스를 포함

  running time도 중요

• 에러 제거 : 설계와 코딩에 따라 쉬워진다.

1.2 포인터와 동적 메모리 할당

1.2.1 포인터

포인터형의 값은 메모리 주소

• & : 주소 연산자
• * : 역참조 연산자

int i, *pi;
pi = &i;

사칙연산과 비교 연산 가능

크기는 컴퓨터(OS)에 따라 다르다.

※ null pointer는 아무것도 가리키지 않는 상태 -> 역참조 불가

if(!ptr)
    ptr = malloc();

1.2.2 동적 메모리 할당

공간을 예측할 수 없을 때 heap 구조를 사용하여 런타임에 할당

• malloc() : 성공 시 시작 포인터, 실패 시 null 리턴
• free() : 메모리 해제, 일반적으로 자료형 생략

메모리 부족으로 인한 malloc 실패를 위한 전처리

#define MALLOC(p, s) \
    if(!((p) = malloc(s)) { \
        fprintf(stderr, "Insufficient memory");    \
        exit(EXIT_FAILURE);    \
    }

동적으로 할당된 위치를 잃게 되면 허상 포인터(dangling pointer)가 될 수 있다.

원인과 해결

무질서한 malloc()과 free() 호출 -> free() 이후 NULL로 리셋,

스택에 할당된 지역 변수의 주소를 리턴하는 경우 -> static으로 정의

1.2.3 포인터의 위험성

포인터 자료형의 형 변환 주의

1.3 알고리즘 명세

1.3.1 도입

• 입·출력
• 명확성, 유한성, 효율성

알고리즘 - 프로그램 : 유한성 O - X

예제 1 - 선택 정렬

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

※ 정수형 한정 (^연산자 활용)

#define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))

※ math.h 라이브러리 함수 rand()는 프로그램을 실행할 때마다 같은 결괏값을 내기 때문에 다른 값을 원한다면

srand(time(NULLL))을 사용할 수 있다.

예제 2 - 이진 탐색

#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1))
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
    }
}

c에서는 함수의 그룹이 따로 컴파일 가능 -> 논리적으로 관련된 알고리즘의 그룹을 포함하는 라이브러리 생성

1.3.2 재귀 알고리즘

예제 3 - 이진 탐색

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);
    }
}

예제 4 - 순열

for(j = i; j <= n; ++j){
    SWAP(list[i], list[j]);
    perm(list, i+1, n);
    SWAP(list[i], list[j]);
}

※ 재귀 함수 종류

• 원시 재귀 함수 : 반복 수를 앎 -> for loop 가능
• 일반 재귀 함수 : 반복 수 모름 -> for loop 불가 ex) 아커만 함수 (stack을 사용하여 해결 가능)

1.4 데이터 추상화

1.4.1 데이터 그룹화

• 배열 : 같은 자료형
• 구조체 : 다른 자료형

1.4.2 자료형 : 객체 + 연산자

종류

• 이미 정의된 자료형 ex) char, int, float, double, ...
• 사용자 정의 자료형

추상 자료형(ADT)

명세와 표현, 실행이 별개

명세 구성 : 함수명, 매개변수명, 반환형, 기능 (내부 표현, 세부 구현 X)

• 생성자(Creator / Constructor) : 새 인스턴스 생성, 필드 값 초기화
• 설정자(Transformers) : 필드 값 변경
• 접근자(Observers / Reporters) : 인스턴스에 대한 정보 제공 (변경 X)

※ Class / Object / Instance

• 붕어빵 틀 - Class
• 붕어빵 - Object
• 각 붕어빵 - Instance
• 붕어빵 굽기 - Instance화

※ ADT 정의

• 이름
• Object
• Function

1.5 성능 분석

1.5.1 공간 복잡도 : 완전히 실행하기 위해 필요한 메모리량

• 고정 공간 : 명령 공간(코드) + 변수(구조체, 상수)
• 가변 공간 : 각 인스턴스, 재귀 시 추가

공간 복잡도 분석 시 주로 가변 공간만 고려

언어에 따라 가변 공간의 크기가 다를 수 있다.

• 파스칼 : 배열 전달 시 값으로 전달 -> 가변 공간 O
• C : 배열 전달 시 주소로 전달 -> 가변 공간 X

1.5.2 시간 복잡도 : 완전히 실행하기 위해 필요한 시간

컴파일 시간 + 런타임

컴파일 시간은 인스턴스에 영향이 없으므로 거의 고정, 잘 동작하면 재컴파일 없이 실행

-> 시간 복잡도 분석 시 주로 런타임만 고려

system clock을 사용하여 측정 가능 -> 대안으로 연산 수

program step : 문법적으로, 의미적으로 의미 있는 세그먼트

(간단히 할당하는 문장 = 복잡한 계산 문장 = 한 단계)

재귀가 반복문에 비해 연산 수가 적을 수는 있지만 주로 더 느리다.

예제 11 - 행렬 합

rows x columns 행렬의 합의 경우 (2rows+1)*columns+1 회 연산, 즉 열이 큰 것이 행이 큰 것에 비해 영향이 크다.

-> "행 >> 열"인 경우 행렬을 바꿔줘야 한다.

Tabular method : Total = ∑Total steps = ∑( Steps/Execution(s/e) * Frequency )

• best case
• worst case
• average

1.5.3점근적(Asymptotic) 표기법

1 Big 'oh' : 상한

정의 : f(n) = O(g(n)), f(n) ≤ c * g(n)을 n>= n0에서 항상 만족시키는 양수 c가 존재한다.

예시 : 3n + 2 = O(n), 3n + 3 = O(n^2), 3n + 4 ≠ O(1)

교환 법칙 X

2 Omega : 하한

정의 : f(n) = Ω(g(n)), f(n) ≥ c * g(n)을 n>= n0에서 항상 만족시키는 양수 c가 존재한다.

예시 : 3n + 2 = Ω(n), 3n + 3 = Ω(1), 3n + 4 ≠ Ω(n^2)

교환법칙 X

3 Theta : 상한 & 하한

정의 : f(n) = θ(g(n)), c1 * g(n) ≤ f(n) ≤ c2 * g(n)을 n>= n0에서 항상 만족시키는 양수 c1, c2가 존재한다.

예시 : 3n + 2 = θ(n), 3n + 3 ≠ θ(1), 3n + 4 ≠ θ(n^2)

1.6 성능 측정

1.6.1 시간

라이브러리 함수 사용

1.6.2 테스트 데이터 생성

최악의 경우의 데이터셋을 만드는 것이 어려울 때 무작위 케이스 중 최악

평균 시간은 항상 구할 수 있는 것은 아니다.

* 단어

• rudiment 기본
• fleeting 순식간의
• rigorous 엄밀한
• delineate 묘사하다
• earnest 진지한
• akin 비슷한
• scrap 폐기하다
• abound 풍부하다
• arsenal 무기
• constraint 강제
• erroneous 잘못된
• feasible 실행할 수 있는
• flowchart 순서도
• discrepancy 모순
• syntactically 문법적으로
• semantically 의미적으로
• decipher 풀다
• extricate 구해 내다
• elapse 경과하다
• legitimate 본격적인