이 글들은 백준 온라인 저지의 백준님이 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개를 시도하는데 걸리는 시간
- 문제의 가능한 경우의 수를 다 계산해본다.
- 가능한 모든 방법을 다 만들어낸다.
- 각각의 방법을 이용해 답을 구해본다.
- 주로 재귀로 푼다
▲ 문제풀이
· 날짜 계산
- 경우의 수 : (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
- 메모이제이션 코드 추가
- 사실 다이나믹 문제지만 제한이 작아서 브루트포스로 풀 수 있는 것
'공부 > 백준 2020년 1~2월 알고리즘' 카테고리의 다른 글
5번째 수업 (0) | 2020.01.22 |
---|---|
4번째 수업 (0) | 2020.01.19 |
2번째 수업 (0) | 2020.01.11 |
1번째 수업 복습 (0) | 2020.01.08 |
1번째 수업 (0) | 2019.12.31 |