한자리숫자 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;
	}
	

}


결과




'문제풀이(BOJ) > 문자열' 카테고리의 다른 글

[백준 9226] 도깨비말  (0) 2019.12.06
[백준 1431] 시리얼 번호  (0) 2019.12.04
[백준 11536] 줄 세우기  (0) 2019.12.02
[백준10174] 팰린드롬  (0) 2019.12.02
[백준2935]소음  (0) 2019.12.01

문제 출처: 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.";
	

}

결과

개념

에라토스테네스의 체는 소수를 판별하는 알고리즘으로, 소수를 구하는 방법중 가장 효율적인 방법이라고 할 수 있다.

아래의 그림이 에라토스테네스의 체를 설명하고있다.

그림을보면, 2부터 120까지의 숫자중, 2부터 시작하여, 2를 제외하고 모든 2의배수를 체크한다. 

그리고 3으로 넘어가서 역시3을 제외한 모든 3의배수들을 체크한다. 다음으로 4인데, 4는이미 2의배수를 체크할때 체크되어서 4는 걸러지고 

모든 4의배수들이 체크된다. 이런 순서로 모든 수를 확인한 후 최종적으로 체크가 안 된 수들이 전부 소수다.

아래에 1~120까지의 수 중 소수를 판별하는 코드를 나타냈다. 소수의 시작은 2라서, 반복문의 시작을 i=2로했다. 

1은 별도로 1로 초기화 해준다.


코드

#include<iostream>
using namespace std;

//0~120까지의 수를 담을 배열
int arr[121];
int main()
{
	//1로체크된 수는 소수가 아닌 수임

	//1은 소수가 아니므로 체크
	arr[1] = 1;
	for (int i = 2; i <= 120; i++)
	{
		//4부터걸러지므로 j=i*i
		//j의 배수만큼 걸러지므로 증감값은 j+=i
		for (int j = i * i; j <= 120; j += i)
		{
			//걸러져있으면 다음 수로 넘어간다.
			if (arr[j] == 1)continue;
			//거른다. (소수가 아니다.)
			arr[j] = 1;
		}
	}
	//확인
	for (int i = 2; i <= 120; i++)
	{
		if (arr[i] != 1)
			cout << i << " ";
	}
	cout << endl;
}


결과

에라토스테네스의 체의 시간복잡도는 O(NloglogN)이다.(이유는 모르겠다.ㅠㅠ)


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


문제

악독한 코치 주혁은 선수들을 이름 순으로 세우는 것을 좋아한다. 더 악독한 것은 어떤 순서로 서야할지도 알려주지 않았다! 

선수들의 이름이 주어질 때 어떤 순서로 이루어져있는지 확인해보자.


입력

첫째 줄에 N개의 이름이 주어진다. (2 ≤ N ≤ 20)

다음 N개의 줄에는 각 선수들의 이름이 주어진다. 이름은 2 이상 12 이하의 대문자로만 이루어져있다. 선수의 이름은 중복되지 않는다.


출력

이름이 증가하는 순으로 나타나면 INCREASING, 감소하는 순이면 DECREASING을 한 줄에 출력한다.

 만약 위의 두 경우가 아니라면 NEITHER를 출력한다.


알고리즘

1.문자열끼리 비교해야하므로 2차원배열(행:N개의이름, 열:이름의 길이)를 선언한다.

2. 증가,감소를 판별하기위해 각각의 bool형자료형의 2변수를 선언한다.

3.첫문자열~마지막 문자열까지 차례대로 비교하며 증감을 파악한다.

4. inc, dec의 결과에따라 결과를 출력한다.

#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;

}



'문제풀이(BOJ) > 문자열' 카테고리의 다른 글

[백준 9226] 도깨비말  (0) 2019.12.06
[백준 1431] 시리얼 번호  (0) 2019.12.04
[백준 2703] Cryptoquote  (0) 2019.12.02
[백준10174] 팰린드롬  (0) 2019.12.02
[백준2935]소음  (0) 2019.12.01

문제출처: 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;
	}
}


'문제풀이(BOJ) > 문자열' 카테고리의 다른 글

[백준 9226] 도깨비말  (0) 2019.12.06
[백준 1431] 시리얼 번호  (0) 2019.12.04
[백준 2703] Cryptoquote  (0) 2019.12.02
[백준 11536] 줄 세우기  (0) 2019.12.02
[백준2935]소음  (0) 2019.12.01

문제 출처: 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;

}


'문제풀이(BOJ) > 탐색' 카테고리의 다른 글

[백준 1668] 트로피 진열  (0) 2020.01.14

+ Recent posts