[알고리즘] 3회차 수업

RGB문제

1) 색칠할 수 있는 최대의 경우 : 3의 n승 => 완전탐색으로는 구하기 어렵다.

문제해결

1) func(idx, color) 함수를 정의

2) idx 번쨰 집을 color로 칠한다

3. 이 때 idx부터 n번째 집까지 칠하는데 드는 최소비용.

문제해결

1. func(idx, color)는 재귀적으로 어떻게 정의?

2. 현재 위치를 칠할 때는 이미 cost가 정해져있다. 

3. func(idx, color) = min(func(idx+1, c1), func(idx+1, c2)) + cost[idx][color]  => 이것 자체만으로는 완전탐색과 다를바가 없다.

4. 메모이제이션 하는 코드가 들어가 있어야 한다.

DP 문제의 경우 ~ 경우의 수를 구하여라, 최소값을 구하여라, 최대값을 구하여라 와 같이 끝맺음을 맺는다.

피보나치 함수

1. 피보나치 함수를 재귀로 짠다

2. 0일 경우, 1일 경우 둘 다 비슷하다.

3. 하지만 기저사례가 달라지게 되므로 서로 다른 함수가 필요

int&는 무엇인가?

int a = 10;

a = 20;

int& b = a;

b = 20; // a => 20;

즉 a의 별명이 b가 된 것이다.

이친수 문제

1. 완전탐색으로 짜려면 인자가 몇개가 필요한가? : 다음을 결정할 떄 중요한 인자는 현재 인덱스이다. 그리고 여기서의 조건은 1이 두 번 연속으로 나올 수 없다. 그렇기 때문에 현재 인덱스와 현재의 숫자가 인자 2개로 넘어가야 한다.

2. 

[문제 해결]

1. func(idx, num)

if

2. 캐시테이블은 인자로 

합분해 문제

문제해결

1. func(cur, count)

2. 현재 cur이란 숫자를 count개의 수를 이용해서 만듬

3. 이 때 N까지 만드는 경우의 수

4. func(cur, count) = sigma[i = 0..N] func(cur + 1, count + 1)

memset함수란?

1byte => 8bit

1byte => 0

0000000000000000 => int

1byte => -1

8bit 

2의 보수 

1. 모든 비트를 반전시킨다.

2. 1을 더한다

1byte에서 1은 (0)0000001 => 1

(1)1111111 => -1

11111111111111111111111111111111 int => -1 

알고리즘 분석

- cache 테이블의 크기가 시간 복잡도

: 재귀함수는 캐시테이블의 크기만큼 돈다.

동전1, 내려가기 문제

문제해결 

1) 메모이제이션이 아니라 반복문으로 풀 수 있는 문제

2) 

점프

1, 2, 3 더하기

1. F(n)을 재귀적으로 정의

2. F(n) = F(n-1) + F(n-2) + F(n-3)

계단 오르기

1. F(idx, cost)를 재귀적으로 정의

2. F(idx, count) = max(

if cost < 1: F(idx - 1, cost + 1), F(idx -2, 0)

) + cost[idx]

시간복잡도

1) Cache 테이블의 크기가 시간 복잡도

2) 

LCS

1) 두 문자열이 주어진다

2. 두 문자열의 최대 공통 부분 수열을 구해라

문제해결

1. F(x, y)

2. A[x], B[y]부터 만들어 갈 수 있는 최대 공통부분 수열의 수

3. F(x, y) = max(

F(x+1, y )

F(

)

퇴사

1. F(idx)

2. idx날부터 상담을 할 수 있을 때 벌 수 있는 최대 금액

부분집합의 합

1 1 1 2 2 2 2 3 3 3 3 3 

        L         U

Lower bound : 내가 찾고자 하는 수의 첫 번째 수를 찾는다.

Upper bound : 내가 찾고자 하는 수의 마지막 수 바로 다음 숫자