문제 링크

풀이 ) DP

  1원부터 시작하여 현재 금액의 memo[i] 값을 최댓값으로 초기화시킨 후 현재 금액보다 작은 가치의 동전을 뺀 memo[i - coin[j]] 값을 순회하면서 비교해준다.

  단 한번도 초기화된 이후에 값이 변하지 않은 경우 불가능한 것이므로 -1을 출력해준다.

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[100002];

int main()
{
    int n, k, coin[101] = {0, };
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i){
        scanf("%d", coin+i);
        memo[coin[i]-1] = 1;
    }

    for(int i = 0; i < k; ++i){
        if(!memo[i])
            memo[i] = 1e9;
        for(int j = 0; j < n; ++j){
            if(i>=coin[j]){
                memo[i] = min(memo[i], memo[i-coin[j]]+1);
            }
        }
    }
    if(memo[k-1] == 1e9)
        printf("-1\n");
    else
        printf("%d\n", memo[k-1]);
    return 0;
}

주의점 )

  동전의 가치가 오름차순으로 주어진 것이 아니기 때문에 i >= coin[j] 를 확인해 런타임 에러가 나지 않게 해주어야 한다.

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

프로젝트 구조

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 본격적인

문제 링크

풀이 ) DP

  스티커를 윗줄과 아랫줄 2줄에서 떼어낼 수 있으므로 memo 배열을 1차원 배열 2개로 구성했다.

  윗줄의 스티커를 떼어내기 위해서는 왼쪽 아래칸을 떼거나 아예 안떼는 경우가 있다.

  아랫줄의 스티커를 떼어내기 위해서는 왼쪽 윗칸을 떼거나 아예 안 떼는 경우가 있다.

  윗줄을 memo[n][0], 아랫줄을 memo[n][1],

  전전 칸(떼지 않은 경우)까지의 최댓값 tmp = max(memo[n-2][0], memo[n-2][1])라 할 때,

  memo[n][0] = max(tmp, memo[n-1][1]) + arr[n][0], memo[n][1] = max(tmp, memo[n-1][0]) + arr[n][1]이 되고

  답은 이중 최댓값인 max(memo[n][0], memo[n][1])이다.

#include <cstdio>
#include <algorithm>
using namespace std;

int arr[100002][2], memo[100002][2];

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < n; ++j)
                scanf("%d", &arr[j][i]);

        memo[0][0] = arr[0][0];
        memo[0][1] = arr[0][1];
        memo[1][0] = arr[0][1] + arr[1][0];
        memo[1][1] = arr[0][0] + arr[1][1];
        for(int i = 2; i < n; ++i){
            int tmp = max(memo[i-2][0], memo[i-2][1]);
            memo[i][0] = max(tmp, memo[i-1][1]) + arr[i][0];
            memo[i][1] = max(tmp, memo[i-1][0]) + arr[i][1];
        }
        printf("%d\n", max(memo[n-1][0], memo[n-1][1]));
    }
    return 0;
}

문제 링크

풀이 ) DP

  앞문 제인 2 x n 타일링과 다른 점은 시작하는 방법이 하나 추가됐다는 점이다.

  2 x 1 타일로 시작할 수 있고 이 때는 뒤에 2 x (n-1) 직사각형을 채우면 되고

  1 x 2 타일 2개로 시작하거나 2 x 2 타일로 시작하는 경우는 뒤에 2 x (n-2) 직사각형을 채우면 된다.

  따라서 점화식은 memo[n] = memo[n-1] + 2 * memo[n-2]이다.

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1002] = {0, 1, 3, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 3; i <= n; ++i)
        memo[i] = (memo[i-1] + memo[i-2]*2)%10007;
    printf("%d\n", memo[n]);
    return 0;
}

주의점 )

  앞 문제와 같이 모듈러 연산은 for문에서 한다.