33건의 항목
실버1 : 동적 계획법 문제이다. 생각 전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.
실버5 : 동적 계획법 문제이다. 생각 생각 보다 힘들게 푼 문제이다. n이 50000이고, 시간 제한이 0.5초이기 때문에 완전탐색으로 풀면 힘들 것이라 생각했다. 그래서 동적 계획법 방법으로 풀이를 채택했다. 이 문제는 동전 문제와 비슷하게 생각해야 한다.
골드5 : 동적계획법 문제이다.
실버1 : 동적계획법 문제이다. 생각 동적 계획법하면 유명한 문제이다. 나는 동적 계획법을 풀 때 보통 두가지 방법을 많이 사용한다. 상태에 대한 정의와 점화식을 직관으로 때린다. (감..) 순차적으로 완전 탐색 방법으로 그려본다.
실버2 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다.
골드3 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다. 이 문제는 가장 긴 감소하는 부분 수열, 가장 긴 증가하는 부분 수열을 합한 문제이다.
골드4 : 동적 계획법 문제이다. 생각 전형적인 dp 문제이다. 다만 이 문제는, 경로를 추적해야 한다는 점에서 조금 다르다. 경로를 추적하는 방법으로는 dp를 미리 구해놓고, 이것을 역으로 추적하여 구하는 방법이 가장 간단하다.
실버2 : 동적계획법 문제이다.
실버2 : 동적계획법 문제이다. 풀이 그냥 합을 구하는 문제이다.
실버1 : DFS 문제이다. 풀이 DFS와 동적계획법이 섞인 문제이다. 일단, 특정 위치까지 갈 수 있는 모든 경우의 수를 구해야 하는데, 그냥 방문할 때마다 count를 늘려준다면, 중복해서 방문하는 곳이 너무 많아 비효율 적이다.
골드4 : dp & DFS 문제이다. 풀이 이게. 접근 방식을 약간 반대로해서 오래걸렸다. 바텀 업 방식으로 사고를 하여, 마지막 지점까지 가는데 있어 4방향의 경로를 더해주어야 한다고 생각했다. 그런데 그렇게 생각을 하니 쉽게 점화식이 떠오르지 않았다.
실버4 : 메모이제이션 문제이다. 생각 고등학교 때 많이 풀어본 함수의 개수 구하는 문제와 같다. 결국은 공역단에서 N개의 site를 고르게 되면 자동으로 순서가 결정되기 때문이다.
실버1 : 동적 계획법 문제이다. 생각 다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.
실버1 : 동적 계획법 문제이다. 생각 다이나믹의 유형 중 중요한 유형이다. 대부분의 동전 문제의 방식과 비슷하다. 1차원 다이나믹이지만 2개의 반복문을 통해 2차원 처럼 생각하는 것이 필요하다.
플레티넘1 : 동적 계획법, Convex Hull 문제이다. 생각 일단 완전 탐색을 생각해 본다. 음. 말도 안된다. 몇개를 겹쳐서 만드는지 완전탐색을 한다면 시간 복잡도가 O(n!) 이다. 이 문제는 그냥 직관적으로 동적 계획법 냄새가 난다.
골드1 : 동적 계획법 문제이다. 생각 dp의 정의는 간단하게 생각할 수 있다. 특정한 상태의 발전소로 오는 방법은 몇가지로 정해지기 때문이다. 그래서 정의를 잡으면 다음과 같다.
실버2 : 동적계획법 문제이다. 풀이 기본적인 동적계획법 문제이다.
실버1 : 동적계획법 문제이다.
실버2 : 동적계획법 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드3 : 동적 계획법 문제이다. 생각 이 문제는, BOJ - 평범한 배낭(12865)과 매우 비슷하다. 한번 푸는 것이 좋다. 이 문제는 memory의 범위가 매우 크기 때문에, 이 것을 기준으로 로직을 짜면 메모리가 터진다.
실버1: 동적 계획 법을 사용하는 문제이다. 대표적인 동적계획법 문제이다. 기초적인 동적 계획법 문제를 풀 때에는 펜을 갖고 쓰는 것이 중요해보인다. 기본적으로 점화식을 갖고 해결하는 방식이기 때문에, 수열 문제를 푸는 것도 같은 사고로 접근해야 한다.
골드1 : stack 문제이다. 생각 아, 어려웠다. 처음에 dp로 풀생각을 했더니, O(n^2) 이라 500,000인 input에 맞지 않는다. 또한 그 과정에서 세그먼트 트리 혹은 우선 순위 큐를 사용하려 했지만 구현 난이도가 올라가 고민했다.
골드3 : dp? 문제이다. 풀이 음..풀이를 이상하게 했는지는 모르겠지만 일단 맞았다. 다른 사람들을 보니, 각각의 시작 위치에서 dfs를 돌려서 최대 거리를 구한뒤 max 를 취하는 방법을 사용한 것 같았다. 이렇게 풀었어도 될 걸 이상하게 풀었다.
실버1 : 동적 계획법 문제이다. 생각 DFS나 BFS로는 depth가 깊어져 시간초과가 난다. 이 문제는 동적계획법으로 풀어야 한다. 그저 최대 사탕의 개수만 출력하면 되기 때문이다.
실버3 : 동적계획법 문제이다. 생각 이 문제의 핵심은, 최고자리 숫자가 0 또는 1일 때의 상황을 분리해서 생각해보는 것이다. 이유는 나열하면 금방 알아차릴 수 있다.
실버1 : 동적계획법 문제이다. max_element 최대한 쓰지 말자. 그리고 sizeof는 바이트수를 리턴해준다.
실버2 : 동적 계획법 문제이다. 생각 앞으로 보내는 dp문제이다. 정의 이 문제는 위치에 따라 개수가 결정되므로 dp의 인자를 좌표의 위치로 잡는 것이 수월하다.
골드5 : 동적 계획법 문제이다. 생각 결국 무게 제약이 있는 문제이다. 나는 이 문제를 풀 때 감을 잡기 참어려웠는데, 무게에 제약이 있다는 점을 갖고 완전 탐색을 한다는 아이디어를 가지고 생각했다.
실버1 : 동적계획법 문제이다. 생각 dp[i] : i번째 포도주의 위치에서 마실 수 있는 최대 포도주 양 i번째 포도주의 포도주 양은 세가지 경로에서 답을 찾을 수 있다.
실버3 : 동적 계획법을 사용하는 문제이다.
골드5 : 동적계획법 문제이다. 풀이 잘 접근했다고 생각했는데, 점화식을 잘 못 구했다.
level2 : 구현, 또는 동적 계획법을 사용하는 문제이다. 처음 풀이로는 빠르게 풀기 위해서 그냥 단순히 구현을 했다. 입력이 1000 x 1000 이라, 완전 탐색을 수행하더라도 로직을 최대한 덜 쓰도록 짜야된다는 생각을 하면서 짰다.
풀이 실패했다. 뭔가 감은 오는데 기존의 dp처럼 풀려고 하니 문제가 안잡히는 기분. 일단 접근 방법은 맞으니, 엑셀처럼 나열하면서 규칙을 찾는 것이 좋다.