-
'동전 0'문제.
-
그리디, 탐욕법으로 풀이.(현재 상태에서 가장 좋아보이는 것을 선택.)
-
조건에서 동전이 배수, 약수라고 주어졌기에 문제가 풀릴 수 있었음.
-
'RGB 거리' 문제.
-
브루트포스로 풀어보기.
N이 3이라고 했을 때, 1번집에 빨간색으 선택보고 2번째 집은 초록이나 파랑 중 하나.
각각에 대해서도 또 경우에 수가 나옴.
1번 집을 선택할 경우의 수는 3. 하나에 대해서 다음 선택 가능한 건 2. 그 다음 집도 2.
각각 독립적이니 곱하기를 해야함.
2^1000 정도의 시간복잡도를 가져서 우주가 끝나도 못 풀게 됨. -
DP로 풀기.
목적은 rgb 색을 칠하는 최소비용 찾는 것.
Cn(color)(C는 cost): n번째 집을 color로 색칠했을 때 최소비용.
우리가 원하는 것은 min{Cn(R), Cn(G), Cn(B)}
n+2의 색은 상관이 없음. 바로 옆집의 색만 중요하기 때문에.
Cn(R) = Rn의 비용 + min{Cn-1(G), Cn-1(B)}
Cn(G), Cn(B)에 대한 식도 이와 같이 구성해주면 됨.
초기화는 C1(R) = R1, C1(G) = G1, C1(B) = B1
DP는 점화식을 세울 수 있으면 된다. -
'쿼드 트리' 문제
-
분할 정복으로 풀기.
4등분을 한 다음에 모든 게 같은 숫자면, 그걸 하나로 표시하겠다는 문제.
같지 않으면 더 나누고, 같은 숫자가 나올 때까지 나눠서 그걸 계층 간의 괄호로 표시해서 나타내겠다는 문제.
문제는 문제를 '분할'하기를 요구하고 있음.
P(n, w(위치 정보))을 정의했을 때 2가지 케이스가 있음.
전부 같을 때와 그 외일때. 전자는 압축되어 문제 없음.
그 외일 경우, 문제를 나눔.
P(n/2, 1), P(n/2, 2), P(n/2, 3), P(n/2, 4) --> 위치가 다르다는 것을 나타냄.
합쳐주는 것은 순서에 맞게 출력만 하면 되는 것. -
부루트포스로 풀기.
n은 최대 15.
첫번째 선택을 할지 말지라는 2가지 경우의 수, 두번째도, n번째도 마찬가지
그래서 시간복잡도는 2^n이 나옴.
그래서 다 해도 2^15니까 컴퓨터로 금방 풀 수 있음.
문제의 제약 조건을 보고 그걸 맞춰서 잘 푸는 것이 중요함.앞으로는 '그래프 알고리즘에 무엇이 있나?'에 대해서 살펴보겠다.
