본문 바로가기

Algorithm9

[구름톤 챌린지] 1주차 학습 일기 #2 문제 설명 구름 햄버거는 다양한 재료를 사용하여 만들어서 맛있기로 유명하다. 구름 햄버거는 개의 재료를 순서대로 쌓아서 만들고, 구름 햄버거의 맛은 사용된 모든 재료의 맛의 정도를 더한 값이다. 완벽한 구름 햄버거를 만들기 위해서는 맛의 정도가 가장 높은 재료를 기준으로 위랑 아래로 갈수록 재료의 맛의 정도가 감소하거나 같아야 한다. 플레이어는 N개의 재료를 순서대로 쌓아서 구름 햄버거를 하나 만들었다. i번째로 쌓은 재료의 맛의 정도가 ki라고 할 때, 플레이어가 만든 구름 햄버거의 맛을 구해보자. 만약 플레이어가 완벽하지 않은 구름 햄버거를 만들었다면 0을 출력한다. 입력 첫째 줄에 구름 햄버거에 들어가는 재료의 개수 N개가 주어진다.(1 > num; arr.push_back(num); } int f.. 2023. 8. 17.

[구름톤 챌린지] 1주차 학습 일기 #1 문제 설명 보통의 계산기는 한 번에 하나의 계산 결과만 나타낼 수 있다. 그래서 여러 개의 계산 결과가 필요한 경우에는 이전 계산 결과를 따로 기록해 둬야 하는 번거로움이 있었다. 플레이어는 이러한 점을 해결하기 위해서 합 계산기를 만들었다. 합 계산기는 여러 개의 계산식을 입력받은 뒤, 각각의 계산 결과를 모두 합해서 출력하는 기능을 가지고 있다. 합 계산기에 입력할 수 있는 계산식은 아래 조건을 만족해야 한다. 계산식은 형태이다. 에는 더하기, 빼기, 곱하기, 나누기의 네 가지 사칙 연산 기호가 들어갈 수 있다. 이때, 나눗셈 결과의 나머지는 버린다.합 계산기에 입력할 개의 계산식이 주어질 때, 합 계산기의 출력 결과를 구해보자. 입력 첫째 줄에 식의 개수 가 주어진다. 다음 T 개의 줄에는 계산식이.. 2023. 8. 16.

DP- 동적 계획법 - DP란?DP는 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미한다. 알고리즘의 분류로 넣긴 했으면 이는 사실 방법론이라고 하는 게 더 맞는 것 같다. 이름의 뜻이 뭔가 깊은 의미가 담겨 있어 보이지만, 그냥 멋있어서 지은 이름이므로 이름과 해당 방법에 연관이 있다는 생각은 버리는 것이 좋다. - 왜 쓰나요?결론부터 말하자면 최적화다. 후에 설명될 Momozation 기법을 사용하여 처음 값을 보관해놓고 이를 활용하는 방식이기 때문에 같은 연산을 여러 번 반복할 필요가 없어 최적화에 용이하다. - 언제 쓰나요?DP를 적용해보기 위해서는 2가지 조건이 필요하다.1. 겹치는 소문제작은 문제로 나누었을 때, 중복되는 부분이 없이 각 소문제의 결과를 활용할 수 없다면 DP를 적용하기 어렵다.2... 2023. 8. 15.

이전 1 2 다음

티스토리툴바