📗 CS/Algorithm

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합 2 문제는 연속합 1 문제에서 숫자를 하나 뺀 경우까지 조사한다는 점에서 차이가 있습니다. 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 예를들어 수열 A가 다음과 같을 때, 10 -4 3 1 5 6 -35 12 21 -1 연속합 1 문제에서는 수열에서 몇개의 수를 선택해서..

문제 수열 A가 주어졌을 때 가장 긴 증가하는 부분수열의 길이와 부분수열을 출력하는 문제. 증가 수열의 길이는 DP를 이용하여 쉽게 구할 수 있습니다. 우선 증가수열의 길이부터 구해봅시다. 1. dp 배열 값을 모두 1로 초기화 합니다. : v 배열에서 모든 인덱스의 배열값은 증가 수열의 시작이 될 수 있기 때문에 1로 초기화 해줍니다. 2. 0번째부터 n-1번째 까지 이중 포문으로 현재 인덱스 위치의 값보다 다음 인덱스 위치(j번째)의 값이 더 크다면 dp 배열의 j번째 값과, i번째 값 + 1중 큰 값을 dp배열의 j번째 값에 삽입합니다. 3. 가장 긴 증가하는 부분 수열을 출력 dp 배열을 이용하여 역추적하여 증가하는 부분수열을 쉽게 구할 수 있습니다. 역추적하지 않고 dp값이 1인 배열부터 순서대..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수를 풀었다면 매우 쉽게 접근할 수 있는 문제입니다. 매커니즘은 동일한데, 오큰수와 달리 어떤 값을 비교하고 어떤 값을 정답 배열에 저장해야하는지만 잘 파악하면 쉽게 풀 수 있습니다. 우선 세팅을 하기 위해 배열을 입력받고 map을 이용해 카운팅하여 c 배열에 해당 숫자가 나온 횟수를 넣어줍니다. 오큰수에서는 배열 값을 스택에 넣고 스택의 탑값과 비교했다면, 오등큰수 배열을 만드는 과정에서는 비교 과정에서..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 요약 1. 크기가 N인 배열에서 2. i번째 인덱스의 배열의 값에서 오른쪽에 있는 수 중 가장 큰 수를 출력 3. 만약 오른쪽에 있는 수가 현재 인덱스의 배열의 값보다 작다면 -1 출력 이중 포문으로 해결은 가능하지만 최악의 경우에 1,000,000 * 1,000,000 = 1,000,000,000,000 (1조) 즉, 1조 / 1억(1s) = 10,000s가 걸리게 되어 시간초과가 발생합니다. 문제는 배열의 i번째 값에서 오른쪽에 있는 수 중 가장 큰 수를 어떻게 빠르게 ..

C++에서 스트링을 입력받을 때 std::cin을 이용해 입력받곤 합니다. 이 때 입력받는 스트링에 공백을 포함하고 싶을 때, 예를 들면 "hello world" 라는 스트링을 하나의 변수에 저장하기 위해서는 getline()을 통해 입력을 받아야 합니다. 하지만 이 때 getline을 호출하기 전 받는 입력이 있다면, 버퍼에 개행문자(\n)가 남아있기 때문에 '\n'이 getline에 바로 입력되어 버리게 됩니다. cin은 '\n'을 처리하지 않고 입력버퍼에 남겨둠 ➡️ getline()은 입력버퍼에 남아있는 '\n'을 가져와서 처리 ➡️ 입력받아 저장된 스트링 변수의 앞부분에 '\n'이 함께 저장됨. int n; string s; cin >> n; getline(cin, s); // n을 입력 이후 ..