본문 바로가기

전체 글145

Greedy와 DP 알고리즘에 대한 고찰 문제를 풀면서, 깨닫는게 많아지면서 변화할 생각을 적어보고자 한다. 결국 DP의 미학은 계산한걸 또 계산하지 않겠다는 것이다. 그래서 메모이제이션이 필요한 것이다. 점화식을 구하는 것이 핵심인데, 점화식이라는 어려운 말보다 다음 껀 어떻게 구할래? 이렇게 생각하면 편할것이다. DP의 경우 N번째가 모두 정답이다. 곧, 정답만 저장된다는 것도 그 정답을 이용해 다음 정답을 이끌어내야하는 과제가 있다. 실버문제의 경우 초기식을 세우고 dp[0] 처럼 하드코딩으로 내가 정의할 수 있는 경우가 많다. 그 후, 문제를 풀때 dp[1], dp[2]는 어떻게 될지 나열하다보면, 결국 문제는 풀리기 마련이다. 골드문제의 경우 dp의 자료구조를 어떻게 정할지에 대해 고민스러웠던 경험이 있었다. dp자체에 어떤 정답을 담.. 2023. 11. 22.
주짓수 #15724 c++ 풀이 https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 전에 이와 비슷한 누적합 문제를 풀었기에 갈피를 잡기 쉬웠다 도형적인 접근이 필요하다. 공식처럼 누적합의 성질을 이용하면 된다. #include using namespace std; int N, M; //영토의 크기 N >> M; for (int i = 1; i population[i][j]; } } dp[1][1] = population[1][1]; dp[1][2] = dp[1][1] + popula.. 2023. 11. 20.
포도주 시식 #2156 c++ 풀이 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 계단 오르기 문제와 매우매우 유사하나, 마지막 계단을 밟지 않아도 되고 꼭 계단을 두칸씩 밟을 필요도 없는 계단오르기라고 생각하면 될 것 같다. #include using namespace std; int n; int arr[10001]; int dp[10001]; int main() { cin >> n; for (int i = 1; i > arr[i]; } //dp[0] = 0; dp[1] = a.. 2023. 11. 15.
요세푸스 문제 #1158 c++ 풀이 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 보자마자 queue를 이용해야겠다고 생각이 들었던 문제 넣고 2번 빼고 뺄때마다 다시 넣고 뽑고 출력하고를 반복하면 풀린다. #include #include #include using namespace std; int main() { int n, k; cin >> n >> k; queue q; for (int i = 1; i 2023. 11. 10.

티스토리툴바