본문 바로가기

분류 전체보기167

잃어버린 괄호 #1541 c++ 문제풀이 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 처음에는 문제조건을 잘못보고, 한번만 괄호를 쳐야하는줄알고 애를 먹었는데 곰곰히 생각해보니 그럴필요가 있나하고 맞춘 문제이다. 결국 가장 작은 수를 만들려면 - 에서 -가 나올때까지 괄호를 씌워서 음수로 만들어주면 된다. ex) + - + - + + => + - - - - - 2023. 11. 22.
DP 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. Dynamic Programming이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요는 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. 메모이제이션 기법을 사용한다. 그것이 핵심이다. Dynamic Programming 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 저장해 두어야 한다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복이 일어나는 경우. 같은 문제는 구할 때마다 정답.. 2023. 11. 22.
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.

티스토리툴바