코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/10828

풀이

전형적인 스택 구현 문제입니다. 스택의 개념을 공부하고 이 문제로 복습하면 좋을 것 같습니다.

본 풀이는 c언어스타일로 구현하였고 9012번문제https://www.acmicpc.net/problem/9012는 c++로 구현했습니다.

코드

#pragma warning (disable:4996)
#include<cstdio>
#include<cstring>
#define STACK_SIZE 10000
int stack[STACK_SIZE];
int top = -1;
void push(int num);
int is_full();
int is_empty();
int pop();
int count();
int peek();
int main()
{
	int n;
	scanf("%d", &n);
	int num;
	char choice[6];
	for (int i = 0; i < n; i++)
	{
		scanf("%s", choice);
		if (!strcmp(choice, "push"))
		{
			scanf("%d", &num);
			push(num);
		}
		else if (!strcmp(choice, "pop")) {
			if (top == -1)
				printf("-1\n");
			else
			{
				printf("%d\n", pop());
			}
		}
		else if (!strcmp(choice, "size"))
		{
			printf("%d\n", count());
		}
		else if (!strcmp(choice, "empty"))
		{
			printf("%d\n", is_empty());
		}
		else if (!strcmp(choice, "top"))
		{
			printf("%d\n", peek());
		}
	}
}
void push(int num)
{
	if (is_full())
		return;
	else stack[++top] = num;
}
int is_full()
{
	if (top == STACK_SIZE - 1)
		return 1;
	else return 0;
}
int is_empty()
{
	if (top == -1)
		return 1;
	else return 0;
}
int pop()
{
	if (is_empty())
		return -1;
	else return stack[top--];
}
int count()
{

	if (is_empty())
		return 0;
	else
	{
		return top + 1;
	}
}
int peek()
{
	if (is_empty())
		return -1;
	else return stack[top];
}

결과

한자리숫자 0~9는 거꾸로 만들어도 그대로 유지가 되는 반면

두자리,세자리 .. n자리 숫자를 거꾸로 만들어야 할 경우가 생길 때  아래와 같이 계산하면 됩니다.

설명은 주석으로 달아놨습니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int x;
	//거꾸로 만들 수를 입력한다.
	cout << "변경 전 수:";
	cin >> x;
	//결과값(거꾸로만들어진 수를 출력하기위해 변수m선언)
	int m = 0;
	//변경이 끝나면 x는 0이 되므로 탈출
	while (x > 0)
	{
		m *= 10;
		m += x % 10;
		x /= 10;
	}
	cout << "변경 된 수:" << m << endl;

}

문제출처: https://www.acmicpc.net/problem/2703

문제

Cryptoquote는 어떤 메시지가 있을 때, 각 알파벳을 다른 알파벳으로 변환해 암호화 하는 방법이다.

예를 들어, HPC PJVYMIY란 메시지가 있을 때, 이를 원래 메시지로 바꾼다면 ACM CONTEST가 된다.

위의 예를 바꾸는 규칙은 H=A, P=C, C=M, J=O, V=N, Y=T, M=E, I=S이다. 이처럼 Cryptoquote를 하려면, 문자와 문자 사이의 규칙이 있어야 한다.

암호화된 메시지와 문자와 문자 사이의 규칙이 주어졌을 때, 이를 원래 메시지로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1000)가 주어진다. 각 테스트 케이스는 다음과 같이 두 줄로 구성되어 있다.

테스트 케이스의 첫째 줄에는 암호화된 메시지가 주어지고, 둘째 줄에는 변환 규칙이 주어진다. 변환 규칙은 알파벳 대문자 26글자로 이루어져있고, 

첫 번째 문자는 A에 해당하는 문자, 두 번째는 B, ..., 26번째는 Z에 해당하는 문자이다. 변환 규칙은 중복되지 않는다. 암호화된 메시지에는 공백이 있을 수 있고, 이것은 원래 메시지에도 포함되어야 한다.

출력

각 테스트 케이스에 대해서 한 줄에 하나씩 원래 메시지를 출력한다.

풀이

1.입력받을 bef, 변경된 알파벳의정보를 저장할 aft string을 선언한다.

2. bef[0]은 aft문자열에서 알파벳bef[0]의 인덱스를 갖는 알파벳으로 변한다.

주의:n을 입력받고 버퍼에남은 개행문자를 지우고 문자열을 입력받아야한다.

코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
	int n;
	cin >> n;
	cin.ignore();
	for (int i = 0; i < n; i++)
	{
		string bef, aft;
		getline(cin, bef);
		getline(cin, aft);
		int size = bef.size();
		for (int i = 0; i < size; i++)
		{
			if (bef[i] == ' ')
				cout << " ";
			else
			{
				cout << aft[bef[i] - 'A'];
			}
		}cout << endl;
	}
	

}

결과

문제 출처: https://www.acmicpc.net/problem/2153

에라토스테네스의 체를 이용한 문제로, 개념을 잘 모른다면 https://jow1025.tistory.com/12을 참고하자.

문제

소수란 1과 자기 자신으로만 나누어떨어지는 수를 말한다. 예를 들면 1, 2, 3, 5, 17, 101, 10007 등이 소수이다. 

이 문제에서는 편의상 1도 소수로 하자.

알파벳 대소문자로 이루어진 영어 단어가 하나 있을 때, a를 1로, b를 2로, …, z를 26으로, A를 27로, …, Z를 52로 하여 

그 합을 구한다. 예를 들어 cyworld는 합을 구하면 100이 되고, abcd는 10이 된다.

이와 같이 구한 수가 소수인 경우, 그 단어를 소수 단어라고 한다. 단어가 주어졌을 때, 그 단어가 소수 단어인지 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 단어가 주어진다. 단어의 길이는 20자 이하이다. 

주어지는 단어는 알파벳 소문자와 대문자만으로 이루어져 있다.

출력

아래의 예제와 같은 형식으로 출력을 한다. 

소수 단어인 경우에는 It is a prime word.를, 아닌 경우에는 It is not a prime word.를 출력한다.

풀이

에라토스테네스의 체만 구현할 줄 알면되기때문에 나머지는 주석으로 설명한다.

코드

#include<iostream>
#include<string>
//한 숫자의 최대값은 52,길이는20자까지므로50*20+1넘는 크기로 배열 선언
int arr[1100];
using namespace std;
int main()
{
	string s;
	cin >> s;

	//에라토스테네스의 체 구현
	arr[1] = 0;
	for (int i = 2; i < 1100; i++)
	{
		for (int j = i * i; j < 1100; j += i)
		{
			if (arr[j] == 1)continue;
			else arr[j] = 1;
		}
	}
	//입력한 단어를 숫자로환산할 때 소수판별
	int sum = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] >= 'a' && s[i] <= 'z')
			sum += s[i] - 'a' + 1;
		else if (s[i] >= 'A' && s[i] <= 'Z')
			sum += s[i] - 'A' + 27;
	}
	if (arr[sum])
		cout << "It is not a prime word.";
	else
		cout << "It is a prime word.";
	

}

결과

문제출처: https://www.acmicpc.net/problem/11536

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char word[20][13];
int main()
{
	int n;
	cin >> n;
	cin >> word[0];
	bool inc = true,  dec = true;
	for(int i=1;i<n;i++)
	{
		cin >> word[i];
		int comp = strcmp(word[i - 1], word[i]);
		if (comp > 0)//B->A꼴이면 
			inc = false;
		else if (comp < 0)
			dec = false;
	}
	if (inc)
		cout << "INCREASING";
	else if (dec)
		cout << "DECREASING";
	else
		cout << "NEITHER";
	cout << endl;

}

문제출처: https://www.acmicpc.net/problem/10174

알고리즘 설명

1. 입력한 문자열의 길이/2의 횟수만큼 문자열의 (첫글자,마지막글자),(첫글자+1글자,마지막글자-1) ....식으로 비교합니다.

2. 대문자와 소문자는 구별하지않기때문에 같다고알려줘야하는데 위의 비교식에서 이를 해결하려면 코드가 너무지저분해집니다.

3. 2번문제를 해결하기 위해 애초에 1번을 하기전에 입력한문자열을 통째로 대문자나 소문자로 통일시킵니다.

4. 비교연산중 한번이라도 짝이안맞으면 틀리므로 check변수로 참유무를 갱신합니다.

5. 3->1->4 순으로 해결합니다.

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int n;
	cin >> n;
	cin.ignore();
	string s;
	for (int i = 0; i < n; i++)
	{
		getline(cin, s);
		bool check = true;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] >= 'A' && s[i] <= 'Z')
				s[i] = s[i] - 'A' + 'a';
		}
		int len = s.size();
		for (int i = 0; i < len / 2; i++)
		{
			if (s[i] != s[len - i - 1])
			{
				check = false;
				break;
			}
		}
		if (check)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
}

문제 출처: https://www.acmicpc.net/problem/2312

소인수분해의 전형적인 코드라고할 수 있습니다.

알고리즘은 다음과 같습니다.

m이 2부터시작하므로 n을 최대한 m으로 소인수분해하고 끝났을 때 m과 m으로 소인수분해한 횟수를 출력하고

n이 1될 때 까지(소인수분해가 끝날 때까지) m++하고 cnt=0으로 초기화하여 다시 소인수분해합니다.

n이 1일때 소인수분해가 끝난다는 것을 이용하면 쉽게풀 수 있습니다.

#include<iostream>
using namespace std;
int main()
{
	int n, t;
	cin >> t;
	while (t--)
	{
		int cnt = 0;
		cin >> n;
		//소인수분해를 시작할 값m-> n으로 m부터나누겠다.
		int m = 2;
		while (1) {
			//n=6 m=2;
			if (n % m == 0) {
				n /= m;
				cnt++;
			}
			//45행 마치고 n=3, m=2;
			else {
				if (cnt > 0) cout << m << " " << cnt << endl;
				//n==1일떄 소인수분해 끝난거라 break;
				if (n == 1) break;
				//m=2의경우 소인수분해끝나서 m초기화시킴
				cnt = 0;
				m++;
			}
		}
	}
}

문제 출처: https://www.acmicpc.net/problem/1940

시간제한이 2초인데 입력으로 들어오는 N이 15000까지라서 

O(N^2)으로 풀게된다면 시간초과가 뜰 수 도있습니다..

처음엔 고유값정렬 후 처음부터 하나씩  더해가며 M이될때 카운트했는데(버블정렬 처럼)

시간복잡도가 O(N^2)이여서 92ms가 걸려서  n개의 자료를 O(NlogN)으로 이분탐색을 응용하여 다시 풀어보았습니다.

결국 제가 제출한 코드의 시간복잡도는 퀵소트O(NlogN) +이분탐색O(NlogN)으로 

O(NlogN)이라고 유추할 수 있습니다.

어떤 방식으로 푸느냐에 따라 시간차이가 상당함을 알 수 있습니다.

알고리즘은 주석으로 대체하겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;
int arr[15001];
int res = 0;

int main()
{
	int n, m;
	cin >> n >> m;
	cin.tie(0);
	cin.sync_with_stdio(false);

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	//계산의 순서를 작은값부터 탐색하기위해 정렬시킴
	sort(arr, arr + n);

	//이분탐색 응용
	int start = 0, end = n - 1;
	while (start < end)
	{
		//start+end가 m이면
		//다음 탐색할 값은 start++,end--번쨰다.
		if (arr[start] + arr[end] == m)
		{
			start++, end--;
			res++;
		}
		//start+end<m이면 작은값+큰값<M이므로 작은값++;
		else if (arr[start] + arr[end] < m)
			start++;
		//start+end>m이면 작은값+큰값>M이므로 큰값--;
		else if (arr[start] + arr[end] > m)
			end--;
	}
	cout << res;

}