전체 글 (125) 썸네일형 리스트형 1912 연속합 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 고민을 많이 한 문제였는데, 놓친 부분은 다음과 같다. 1. 부분합이 음수가 될 수 있음 2. 부분합 < 0이면, 현재 원소가 가장 큰 부분합 점화식을 세우는게 어렵구나.. 추론이 부족한듯하다. #include #include using namespace std; int arr[100001] = { 0, }; int dp[100001] = { 0, }; int N; int main() { int result = 0; ci.. 1759 암호 만들기 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net #include #include #include using namespace std; int L, C; vector charset; vector vowels = { 'a', 'e', 'i', 'o', 'u' }; bool IsPassword(vector& picked) { /* 암호를 판단하는 기준 모음의 개수 >= 1 조합의 길이 - 모음의 개수 >= 2 */ int cnt = 0; for (const auto& .. 완전탐색 본 글은 프로그래밍 대회에서 배우는 문제해결전략 책과 다른 완전 탐색 구현방법을 보고 정리하는 글이다. 완전 탐색은 다른 말로 brute-force 직역하면 무차별 대입, 모든 경우를 다 구해보는 것이다. 컴퓨터의 장점을 가장 잘 이용하는 방법으로 단순한 문제들을 빠르게 계산할 수 있기 때문에 효율적인 알고리즘을 설계하기 전에 생각해보는 방법이다. 흔히 재귀 호출로 쉽게 구현할 수 있는데, 기저 사례 (base case)의 선택과 상태 공간 트리의 순회방법을 어떻게 구현할 지 고민해야 한다. (상태공간트리 : 완전 탐색에서 해의 조합들을 트리 (tree) 형태로 나타낼 수 있는데, 부분 문제들을 한 눈에 알 수 있다.) 또한 부분 문제가 또 다른 부분 문제를 구하는 과정에서 쓰일 수 있기 때문에 메모이제.. 이전 1 ··· 36 37 38 39 40 41 42 다음
