백준 알고리즘 강의 후기(코드플러스): 중급3 - 다이나믹 프로그래밍3 (DP3)
백준/BOJ/코드플러스/알고리즘 강의 후기
1/2 1강
● 1300 - 다이나믹 프로그래밍 3
- 알약
- 욕심쟁이 판다
- 내리막 길
- 가장 큰 정사각형
- 1, 2, 3 더하기 7
- 1, 2, 3 더하기 9
- 고층 빌딩
- 홍준이의 친위대 : 여기까지 2강
- 좋아하는 배열 : 여기부터 3강
- 방법을 출력하지 않는 숫자 맞추기
- 숫자 맞추기
- 자물쇠
알약
한조각 F, 반조각 F
반조각: (F, H) -> (F-1, H+1)
한조각: (F, H) -> (F, H-1)
초기값은 D[0][0] = 1 <- 경우의 수는 하나라는 뜻.
바텀업으로 하면, 각각의 변수를 순회하는 방법을 고민해봐야함. 그렇기 때문에, 이런 경우에는 탑다운 방식의 재귀로 하는게 훨씬 좋다.
욕심쟁이 판다
탑다운 바텀업 둘다 가능
탑다운 : 모든 i,j 위치에서 얼마나 더 갈수있는지 본다
바텀업 : 탑다운이 빠르다고 하는데, 바텀업이 더 빠를것 같은데..
바텀업은 반복문으로 하는건데, 어떤 순서로 반복문을 할지 모르기 때문이다. 네방향이라서..
수의 크기를 기준으로 칸의 정보를 미리 내림차순으로 저장해놓아야함. 정렬때문에 엔제곱로그엔임.
내리막 길
앞에문제랑 비슷함.
가장 큰 정사각형
D[i][j] = min(왼쪽위, 바로위, 바로왼쪽) + 1
1, 2, 3 더하기 7
한문제에서 조건이 추가된 문제
1. 정수 n 을 1,2,3의 합으로 나타나는 방법의 수 + m개
1. d[n] = d[n-1] + d[n-2] + d[n-3]
어떤 조건이 문제를 어렵게 하면, 그 조건이 없다고 생각하고 일단 풀고, 그 조건을 추가해서 다시 생각해 본다.
i를 합으로 나타내는 방법의 수, 사용한 개수는 j개
D[i][j] = D[i-1][j-1] + D[i-2][j-1] + D[i-3][j-1]
초기값은?
수를 사용하지 않은상태, 합은 0, 사용한개수도 0
D[0][0] = 1 <- 방법의 수는 1
1, 2, 3 더하기 9
위와 비슷하지만 조금 다른 m개 이하.
위의 정답은 D[n][m]
이것의 정답은 D[n][1] + ... + D[n][m]
시간 복잡도도 똑같다.
여기에서 개선하고 싶은것은 초기값.
D[0][모든칸에] = 1을 넣어준다.
왜 이렇게 해야하나요?
프레임을 왼쪽 오른쪽으로 막 옮김.
그러면 맨 윗줄은 전부 1이 되고 맨 오른쪽 아래가 모두 누적되어 원하는 답이 됨.
그래서, m개 이하라고 하면 1로 채우고 하면 된다는 결론.
고층 빌딩
D[N][L][R]
높이가 1~N
높이가 2~N을 먼저 구하고 1을 더하는것으로 계산.
- 12/4일 여기까지 들음.
1강 11분 다시들어야할듯
홍준이의 친위대
12/19 대충이해함
여기까지 2강
좋아하는 배열
여기부터 3강
D[N][A]
첫수가 A인 배열의 개수
조건이 매우 독특하다
다시듣기
방법을 출력하지 않는 숫자 맞추기
왼쪽으로 돌리면 아래에 있는 나사가 같이 돈다는 조건 때문에 각 층이 독립적이지 않으므로 까다로운 문제가 되었다.
중요1. 한바퀴돌면 원래 자리로 온다.
위의 조건 때문에 맨 위에부터 맞춰야한다.
cur 을 b[index] 로 만들기 위해 (b[index] + 10 - cur) % 10 이런 수식이 필요하다.
숫자 맞추기
방법을 기록해 두면 된다.
자물쇠
상태를 잘관리해야 한다.
● 1301 - 다이나믹 프로그래밍 3 (연습)
로봇 조종하기
여행
구간 나누기
크리스마스 트리
자두나무
숫자 박스
즐거운 단어
미로에 갇힌 상근
돌다리 건너기
● 1302 - 다이나믹 프로그래밍 3 (도전)
등차수열
선물 전달
집합의 개수
팰린드롬 경로
팰린드롬 보행
사다리 게임
같은 탑
경로 찾기
경찰차
직사각형 만들기
서로소의 개수
그래프 매칭
