F.R.I.D.A.Y.

주어진 배열에서 연속하는 각 요소의 합이 최대인 값 구하기. 코드 #include using namespace std; #define max(x,y) ((x) > (y) ? (x) : (y)) int main() { int n; int* arr; cin >> n; arr = new int[n]; for (int i = 0; i > arr[i]; int result = arr[0]; { for (int i = 1; i 0 && arr[i - 1] + arr[i] > 0) { arr[i] += arr[i - 1]; } result = max(arr[i], result); } } cout 0 위 조건을 추가해 점화식을 적용하면 다음..

최대 합이 되는 경로 검색 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 2차원 배열로 구성을 했다변 더 좋았겠지만, 2차원 배열을 굳이 사용하지 않더라도 수식만으로 2차원 배열을 사용하는 것처럼 구성이 가능하다는 것을 보이기 위해 1차원 배열을 사용해봤다. #include using namespace std; int main() { int n; cin >> n; int* arr = new int[n * n]; cin >> arr[0]; for (int i = 1; i > arr[i * n]; arr[i * n] += arr[(i - 1) * ..

LIS를 해결하는 시간 복잡도 O(nLogn)의 알고리즘 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include using namespace std; int main() { int n; cin >> n; int* input, * dp; input = new int[n]; dp = new int[n + 1]{}; for (int i = 0; i > input[i]; int maxLength = 1..

가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include int main(void){ int size, max = 1; int data[1000], dp[1000]; scanf("%d", &size); for(int i = 0; i d..

11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 입력받은 동전들의 가치로 입력받은 금액을 만드는 동전 개수에서 가장 개수가 적은 값을 출력하는 문제입니다. 문제의 알고리즘 분류를 보면 과 이 들어가 있습니다. 문제 해결에 앞서 그리디 알고리즘에 대해 알아봅니다. 그리디 알고리즘 그리디 알고리즘을 간단히 설명하면 현재 상황에서 가장 최선의 값을 선택하는 알고리즘으로 아래와 같은 상황에서 A 루트를 선택하는 경우입니다. 전체를 보았을 때 B 루트가 최..

10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 이번에는 BAEKJOON 10845번이자 대표적인 선입선출의 구조를 같은 큐(Queue) 문제를 풀어봅니다. Code. #include #include typedef struct{ int *arr; // 데이터 메모리 포인터 int maxLength;// 가용 가능한 공간 길이 int length; // 현재 데이터가 담긴 길이 }queue; // 큐의 정보를 담은 스트럭처 queue* newQueue(int m..

스택을 이용하는 문제라고는 하지만 잘 생각해보면 굳이 스택을 사용하지 않아도 되는 문제입니다. 문제의 핵심은 결국 괄호의 특성을 이해하는 것이라고 생각합니다. 결국 괄호가 제 기능을 하기 위해서는 여는 괄호( 와 닫는 괄호) 가 1대 1로 잘 맞아 떨어져야합니다. 단순히 숫자가 맞아야하는 것이 아니라, 앞서 여는 괄호가 n개 나왔다면 뒤에 닫는 괄호는 여는 괄후 수만큼, 즉 n개가 나와야합니다. 생각을 해보면 스택을 이용하지 않아도 됩니다. 정수를 저장하는 변수를 선언하여 여는 괄호를 만나면 1 올려주고, 닫는 괄호를 만나면 1 내려주면 됩니다. 이 변수의 값이 0보다 작으면 바로 문제에서 설명하는 올바르지 않은 괄호 문자열(VPS)가 아닌게 되는 것입니다. 위에서 설명한 변수가 아래에서는 parenth..