3번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

▲ 다이나믹 프로그래밍 문제풀이

· 가장 긴 증가하는 부분수열

- 영어로 LIS (Longest Increasing Subsequence)

- 수열의 길이가 N일때, 부분수열은 2^N개

- D[i] = LIS의 길이, A[i]가 가장 마지막에 있는 수열

- A[i] 바로 앞에 오는 A[j]

- 조건1 : A[j] < A[i] (증가해야 하므로)
- 조건2 : j < i (순서를 유지해야 하므로)

- D[i] = max(D[j]) + 1 (j < i & A[j] < A[i])
- 시간복잡도 : O(N^2)

 

· 가장 긴 증가하는 부분수열 4

- 길이 + 해당 수열 출력

- 역추적(정답을 다시 찾아감) 필요

- V라는 배열을 만들어 D[i]가 D[j]+1로 바뀔때 왜 바뀌었는지 기록

 

· 연속합

- 연속된 숫자중 몇개를 택해서 구할 수 있는 합 중 가장 큰 합

- 정답에 음수가 포함될 수 있다.

- 1. i 혼자 : A[i]
- 2. i-1 선택 + i : D[i-1] + A[i]

- D[i] = i번쨰 수가 가장 마지막인 최대 연속합
        = max(A[i], D[i-1]+A[i])

- 정답이 다이나믹 배열의 가장 마지막에 들어있지 않다.

 

· 제곱수의 합

- 1, 2, 3합, 방법의 수 , 차이는 없음
- 합 : N-i^2 + i^2 = N
- D[N] = min(D[N-i^2]+1)
- 시간복잡도 : O(N*sqrt(N))

- 팁 : 이 문제의 정답은 항상 4보다 작다.

 

· 합분해

- ○+○+○+ ... +○ = N
     N-L           + L
 └──정수 K개─┘

- N-L은 K-1개로 만들어야 한다.
- D[K][N] = 정수 K개로 N을 만드는 방법의 수
             = ∑ D[K-1][N-L]  (0≤L≤N)

- 시간복잡도 : O(KN^2)

 

● 브루트포스

• 모든 경우의 수를 다 해보는 것
• 브루트포스를 풀 때는 항상 방법이 몇가지 있는지 세봐야 한다.
• 시간복잡도 = 방법의 수 x 방법 1개를 시도하는데 걸리는 시간

1. 문제의 가능한 경우의 수를 다 계산해본다.
2. 가능한 모든 방법을 다 만들어낸다.
3. 각각의 방법을 이용해 답을 구해본다.

• 주로 재귀로 푼다

▲ 문제풀이

· 날짜 계산

- 경우의 수 : (E, S, M)의 조합 = 15*28*19=7980

- 브루트포스로 충분히 해결 가능하다.

 

· N과 M (1)

- 수를 기준으로 할 것인가? 위치를 기준으로 할 것인가? 그에 따라 구현방법과 시간복잡도가 달라진다.

- 위치를 기준으로 - 배열을 만들어 앞에서 사용했는지 표시한다.

- 시간복잡도 : O(N!)

 

· N과 M (2)

(위치 기준)

- 수열이 오름차순이어야 한다.

- 수가 어디서부터 시작하는지도 기록

- 시간복잡도 : O(N!)

------------------------

(수 기준)

- 각각의 수를 어느 위치에 넣을지, M+1개의 선택지가 주어진다.

- but 오름차순이면 3개의 수를 골랐을 때 나올수 있는 조합은 1개뿐

- 시간복잡도 : O(2^N)

 

· N과 M (3)

- 중복선택 가능
- 중복검사하는 코드 삭제해 주면 됨

- 시간복잡도 : O(N^M)

 

· N과 M (4)

- 중복가능 & 비내림차순

- 비내림차순 : 오름차순인데 같은걸 포함하게 만드는거
- 중복검사 지우고 start 추가

 

● 브루트포스 - 재귀

· 1, 2, 3 더하기

- 항의 최대 개수는 N개, 각 항마다 올 수 있는 숫자는 3개
- 경우의 수 : 3^10개 = 약 6만
- 단계 1. 정답을 찾음  / 2. 불가능한 경우  / 3. 다음 경우 호출

 

· 암호 만들기

방법 1.
- 알파벳을 먼저 정렬 -> 각 알파벳에 대하여 사용할지 말지 여부 결정
- 경우의 수 : 2^C (3≤C≤15) = 약 3만. 브루트포스 충분히 가능
- 사용하는 경우 : go(n, alpha, password+alpha[i], i+1)
- 사용하지 않는 경우 : go(n, alpha, password, i+1)
- 정답을 찾은 경우 : password의 길이 = n
- 불가능한 경우 : 더이상 할수 있는게 없는 경우
방법 2.
- 알파벳을 L개를 고른다음 정렬

 

· 퇴사

방법1 브루트포스
- N최대가15. 최대 경우의 수 2^15
- 중요한 변수 : 날짜(day), 그때까지 구한 수익(sum)
- go(day, sum) = day일이 되었을때, 그때까지 얻은 수익(day-1일까지 얻은)
- ① 문제의 정답 : (day == N) 일떄의 sum
- ② 불가능한 경우 : day > N 일 경우
- ③ 다음 경우 : day + T[day], sum+P[day]
방법2 다이나믹
- 이전의 상담결과에 영향을 받지 않음. 그저 앞으로 며칠동안 못할뿐
- 비슷한 문제 : 퇴사2
- 메모이제이션 코드 추가
- 사실 다이나믹 문제지만 제한이 작아서 브루트포스로 풀 수 있는 것