이것 저것 &

문제 링크: https://www.acmicpc.net/problem/2437

문제풀이 자체는 정말 쉬운데, 생각하는 과정이 필요했던 문제입니다.

N은 1 이상 1,000 이하이다. 라는 문제 조건을 가진다.

즉 모든 추들을 더하고 빼며 모든경우의 수를 도출(dfs방식)하는 방식으로는 시간 초과를 받을 수밖에 없다.

우선은 누적합 개념에 대해서 이해하셔야 합니다. 

for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

정렬되어 있는 상태라면 위와 같은 방법으로 O(n) 만에 측정할 수 없는 결과값을 도출할 수 있습니다.

sum은 0부터 시작되며 정렬되어 있는 arr배열에서 가장 작은 값부터 하나씩 증가하며 값을 확인합니다. sum + 1 보다 클 경우 sum + 1에 해당하는 값은 측정할 수 없기 때문에 break를 써서 반복문에서 나가게 되는 구조입니다. 

아래는 정답코드 입니다. 

#include <iostream>
#include <algorithm>
using namespace std;

int n = 0, len = 1;
int arr[1001];
int sum = 0;


int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n); //오름차순 정렬

	for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

	cout << sum + 1 << endl;
}

위처럼 간단한 방식으로 정답을 도출할 수 있습니다. 

문제링크: https://www.acmicpc.net/problem/1783

문제의 규칙입니다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

그리고 4회이상 이동시 4가지이동을 포함해야한다는 규칙이 있습니다.

만약 n이 1이라면, m값과 관계없이 이동이 불가하기 때문에 1입니다.

만약 n이 2이라면, 2번과 3번 이동이 가능해집니다.

올라갔다 내려갔다 하면서 이동할 수 있겠죠! 하지만  4회이상 이동시 4가지이동을 포함해야한다는 규칙때문에 3회의 이동까지만 가능합니다. (1번, 4번이동은 2칸 씩 이동해야하지만 그것이 불가능하기 때문에) 

만약 n이 3이상이라면, 규칙적으로 이동하게 됩니다. m이 7이상이여서 문제의 규칙 1, 2, 3, 4번 이동이 모두 가능하다면 각각 4번의 이동를 하고 그 이후부터는 1, 4번 이동만을 반복할 것입니다. (가장 많이 탐색하기 위해서)

즉, m-2번 탐색이 가능해집니다.

위의 3가지 규칙을 생각하면서 예외를 처리해주시면 됩니다.

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int main() {
	cin >> n >> m;
	if (n == 1) {
		cout << 1 << endl;
	}
	else if (n == 2) {
		if (m >= 7)
			cout << 4 << endl;
		else
			cout << (m + 1) / 2 << endl;
	}
	else {
		if (m >= 7) {
			cout << m - 2 << endl;
		}
		else {
			cout << min(4, m) << endl;
		}
	}
}

n 의 갯수마다 처리해야할 예외가 다릅니다. 

조건문들의 조건은 직접 그림을 그리며 이해해보세요.

화이팅! :)

문제링크: https://www.acmicpc.net/problem/2352

꽤나 애를 먹었습니다.

문제를 읽고 dp문제인 것을 인지했습니다. 

이 문제는 dp알고리즘 중에서도 LIS( Longest Increasing Subsequence) 입니다.

최대 부분 증가 수열이라고도 합니다.

만약 

10 20 40 30 70 50 60  의 배열이 있을때

10 20 30 50 60 이 최대 부분 증가 수열로써 가장 길이가 깁니다.

아래와 같은 뉘앙스로 해결해주면 됩니다.

#include <iostream>
using namespace std;

struct info {
	int count;
	int port_num;
};
int n,result=0;
struct info dp[40001];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> dp[i].port_num;

	dp[1].count = 1; //초기값 설정

	for (int i = 2; i <= n; i++) {

		for (int j = i - 1; j > 0; j--) {
			if (dp[i].port_num > dp[j].port_num &&dp[i].count < dp[j].count)
				dp[i].count = dp[j].count;
		}
		dp[i].count++;
		if (result < dp[i].count)
			result = dp[i].count;
	}
	cout << result << endl;
}

 
하지만 문제가 생깁니다. 위의 알고리즘은 O(n^2)을 가지게 됩니다.

이 문제에서는  n(1 ≤ n ≤ 40,000) 입니다. 즉, 최악의 경우에 O(n^2) = 40000 X 40000 = 1,600,000,000 이 되기 때문에 시간제한 2초로는 어림도 없죠 ( 1억번 연산 당 대략 1초)

즉 O(n) or O(nlgn)의 풀이법을 찾아야합니다. 해당 문제에서 이전값들을 비교해서 결과를 도출해야 하기 때문에 O(n)은 불가능합니다.

C++ stl에서 제공하는 기능은 1.Lower Bound 2.인덱스 트리 입니다. (정확한 메소드내용은 모르겠지만 탐색시 O(lgn)번의 탐색으로 위치를 전달합니다. 

함수들에 관한 자세한 설명은  출처:https://dyngina.tistory.com/16

제가 만든 정답 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n = 0,len=1;
int arr[40001] ;
int arr2[40001] = { 0 };
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	arr2[len] = arr[1]; //초기값 설정
	
	for (int i = 2; i <= n; i++) {
		if (arr2[len] < arr[i]) {
			arr2[++len] = arr[i];
		}
		else {
			int val = lower_bound(arr2 + 1, arr2 + len + 1, arr[i]) - arr2;
			arr2[val] = arr[i];
		
		}
		
	}
	
	cout << len << endl;
}

생각해보니 arr는 필요가 없더군요 매번 값을 입력받고 arr2에 저장해주면 됩니다.

그리고 lower_bound메소드의 역할을 이분탐색을 통해서 구현을 할 수 도 있겠군요.

#include <stdio.h>
#define M 40010
int port[M];
int up[M] = { 0x80000001, };
int ref[M];
int n, max;

int search(int left, int right, int x) {
	int mid;

	if (left > right) return left;

	mid = (left + right) / 2;

	if (ref[mid] < x)
		return search(mid + 1, right, x);
	else if (ref[mid] > x)
		return search(left, mid - 1, x);
	else
		return mid;
}

int main() {
	int i, cursor;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", port + i);
		cursor = search(0, max, port[i]);
		ref[cursor] = port[i];
		up[i] = cursor;
		if (cursor > max)
			max = cursor;
	}
	printf("%d\n", max);
	return 0;
}

어려웠습니다...

우선 첫번째로 고려하셔야 하는게 "문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다." 입니다

일반적인 방법으로 문제에 접근하면 "어 그냥 반복해서 문자열을 지워주다가 지울게 없으면 출력하면 되겠네" 겠죠.

이때, 최악의 경우 O(n^2)입니다. (n X n/2) 

시간제한범위를 한참 넘습니다. (1억번의 연산당 1초정도입니다.)

1000000 X 1000000/2 = 500000000000 > 200000000

따라서, 다른방법을 생각해보아야 합니다. 

스택을 사용해야합니다. 

1. 모든 문자열을 스택에 넣는다. 

2. 넣으면서 폭발문자열의 끝 문자와 같다면 스택을 검사합니다.

3. 폭발문자열이 있는지 확인하고, 있다면 해당문자열을 지워줍니다. 

위 의 방식으로 O(n) 번만에 값을 찾을 수 있습니다.  

두번째로 고려하셔야 할게 있습니다. 

저는 string의 erase함수를 사용하며 데이터를 지우면서 결과값을 도출했는데, 45%에서 시간초과가 났습니다. 

1. C의 strlen
2. C++의 string.erase
3. Java의 String.replaceAll
4. Python의 str.replace, str.find, list.pop(i) etc

굳이 내장함수가 아니더라도 단순히 문자열의 중간을 한 번 지울 때마다 거의 무조건 O(N)이 걸립니다. 즉 지우는 행위를 하면 안됩니다. 

곰곰히 생각해보니까 해당 스택자체가 결과값이더군요... ( 연결되는 모든 폭발 문자열을 지운 문자열 그자체..)

이거를 늦게 알아서, 고생한 문제 였습니다. 

#include <iostream>
#include <string>
using namespace std;

string basic,bomb;
char result[1000001];
int  result_cur = 0;
int main() {
	char lastword;
	cin >> basic;
	cin >> bomb;
	lastword = bomb[bomb.size() - 1];

	for (int i = 0; i < basic.size(); i++) {
		result[result_cur++] = basic[i];
	

		if (basic[i] == lastword) //마지막 문자열과 다르면 스택에 담습니다.
		 { 
			
				bool jud = true;
				for (int j = bomb.size() - 1; j >= 0; j--)
				{
					if (bomb[j] != result[result_cur - 1 - (bomb.size() - 1) + j]) { // 스택의 가장위쪽부터 한칸씩 내려오면서 검사
						jud = false; //즉 해당문자열이 아니면 false
						break;
					}
				}
				if (jud == false) {
					continue;
				}
				else { 
								
					for (int j = 0; j < bomb.size(); j++) {
						result_cur--;				
					}
				}	
		}
	}
	if (result_cur==0)
		cout << "FRULA" << '\n';
	else {
		
		for (int i = 0; i < result_cur; i++) {
			cout << result[i];
		}
		cout << '\n';
	}
}

result 는 스택, 결과값 입니다. 

for (int j = bomb.size() - 1; j >= 0; j--)
				{
					if (bomb[j] != result[result_cur - 1 - (bomb.size() - 1) + j]) { // 스택의 가장위쪽부터 한칸씩 내려오면서 검사
						jud = false; //즉 해당문자열이 아니면 false
						break;
					}
				}

3. 폭발문자열이 있는지 확인하고,

for (int j = 0; j < bomb.size(); j++) {
						result_cur--;				
					}

있다면 해당문자열을 지워줍니다. (스택에서 단순히 커서를 내려줌으로써 지울 수 있겠죠.)

화이팅:)

너무 쉬워서 설명은 생략입니다

#include <iostream>
#include <string>
using namespace std;
string arr;

int main() {
	cin >> arr;
	for (int i = 0; i < arr.size(); i++)
	{
		if (arr[i] == 'C' || arr[i] == 'A' || arr[i] == 'M' || arr[i] == 'B' || arr[i] == 'R' || arr[i] == 'I' || arr[i] == 'D' || arr[i] == 'G' || arr[i] == 'E'){
			arr.erase(i, 1);
		i--;
		}
	}
	if (arr.size() == 0)
		cout << ' ' << endl;
	else
		cout << arr << endl;
}

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이룰 수 있다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

해당규칙들을 만족시켜야한다. 

즉, '(' 과 ')' 의 개수가 일치하여야 하고 '(' 가 이전에 있어야한다. (대괄호도 마찬가지)

((())) -> yes이고 (())) , ((()) -> no 이다. 

짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 

해당규칙에 따라 ([] [] )(()) ->yes  이고 (([(])) -> no가 된다.

#include <iostream>
#include <string>
using namespace std;

string arr;

int main() {

	while (1) {
		int	stacked[100] = { 0 };
		bool jud = true;
		int small_bracket = 0, big_bracket = 0, stack_index = 0;
		
		getline(cin, arr);
		if (arr[0] == '.'&& arr.size()==1)
			break;

		for (int i = 0; i < arr.size(); i++) {
		
			if (arr[i] == '(') {
				small_bracket++;
				stacked[stack_index++] = 1; // 1이 small 2가 big
			}
			else if (arr[i] == '[') {
				big_bracket++;
				stacked[stack_index++] = 2; // 1이 small 2가 big
			}
			else if (arr[i] == ')') {
				if (small_bracket < 0) {
					jud = false;
					break;
				}
				if (stacked[stack_index-1] != 1) {
					jud = false;
					break;
				}
				else 
					stacked[--stack_index] = 0,small_bracket--;

			}

			else if (arr[i] == ']') {
				if (big_bracket < 0) {
					jud = false;
					break;
				}
				if (stacked[stack_index - 1] != 2) {
					jud = false;
					break;
				}
				else
					stacked[--stack_index] = 0, big_bracket--;

			}

		}

		if (small_bracket != 0 || big_bracket != 0)
			jud = false;

		if (jud == false)
			cout << "no" << endl;
		else
			cout << "yes" << endl;

	}
}

전형적인 낚시문제.. 

앞, 뒤에 공백이 있을 수 있다는 사실을 모른채 뉴비들의 정답률을 뺏어간 25퍼짜리 문제입니다..

쉽습니다.  앞뒤 공백을 제외한 공백의 갯수 + 1이 단어의 개수가 됩니다.

(공백이 연속해서 나오는 경우는 없다. ) 라는 조건 때문입니다. 이것을 고려해서 코드를 짜면 

#include <iostream>
#include <string>
using namespace std;

string arr;
int cnt = 0;
int main() {
	getline(cin,arr);

	for (int i = 0; i < arr.size(); i++)
		if (arr[i] == ' ')
			cnt++;
	if (arr[0] == ' ')
		cnt--;
	if (arr[arr.size() - 1] == ' ')
		cnt--;
	cnt++;
	cout << cnt << endl;

}

이렇게 간단한 코드가 나옵니다.

c언어의 strtok이라는 함수를 이용해서 단어를 구분하는 방법도 있습니다. 

#include <stdio.h>
#include <string.h>

int main() {
	int count = 0,k=0;
	char arr[1000001];
	gets(arr);
	char *a;
	a = strtok(arr, " ");
	while (a != NULL) {
		count++;
		a = strtok(NULL, " ");
	}
	printf("%d\n", count);
	
}

꼭 직접 손으로 짜보시면서 연습하시길 바랍니다. 

정말 쉬운 문자열 처리문제입니다. 

푸는방법도 다양합니다.

저는 가장 긴 문자열 기준으로 값을 비교하면서 다른값이거나 문자열이 없다면, ? 

모두 같은 문자라면 해당문자를 추가하는식으로 결과값을 도출했습니다. 

#include <iostream>
#include <string>
using namespace std;

int n = 0;
string arr[50];
string result; 

int main() {
		
	int len = 0,len_index=-1;
	// input 
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i].size() > len) len = arr[i].size(), len_index = i;
	}

	for (int i = 0; i < len; i++) {
		char word = arr[len_index][i];
		bool jud = false;
		for (int j = 0; j < n; j++) {
			if (i > arr[j].size() - 1) {
				result += '?';
				jud = true;
				break;
			}
			else if(word != arr[j][i]) {
				result += '?';
				jud = true;
				break;
			}
				
		}
		if (jud == false)
			result += word;

	}
	
	cout << result << endl;
}