코딩무식자 전공생

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

문제

두 정수 A와 B가 주어졌을 때, 두 정수 사이에 있는 수의 합을 구하는 프로그램을 작성하시오. 사이에 있는 수들은 A와 B도 포함한다.

입력

첫째 줄에 두 정수 A, B가 주어진다. (-2,147,483,648 ≤ A, B ≤ 2,147,483,647)

출력

첫째 줄에 답을 출력한다. (-2,147,483,648 ≤ 답 ≤ 2,147,483,647)

풀이

제가 작성한 글중의 https://jow1025.tistory.com/35 의 첫번째 공식을 이용하면 되고, a>b일 때만 고려해주면됩니다.

코드

#include<iostream>
using namespace std;
int main()
{
	long long a, b;
	cin >> a >> b;
	if (a <= b)
		cout << (b - a + 1) * (b + a) / 2;
	else
		cout << (a - b + 1) * (b + a) / 2;
}

결과

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

문제

팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다.

상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC 문제가 저장되어 있는 서버에 접속할 수 있는 비밀번호에 대한 힌트이다. 비밀번호는 k개의 단어 중에서 두 단어를 합쳐야 되고, 팰린드롬이어야 한다. 예를 들어, 단어가 aaba, ba, ababa, bbaa, baaba일 때, ababa와 ba를 합치면 팰린드롬 abababa를 찾을 수 있다.

단어 k개 주어졌을 때, 팰린드롬을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 공책에 적혀져있는 단어의 수 k(1 ≤ k ≤ 100)가 주어진다. 다음 k개 줄에는 a부터 z까지 알파벳으로 이루어진 단어가 한 줄에 하나씩 주어진다. 모든 단어 길이의 합은 10,000보다 작거나 같다.

출력

각 테스트 케이스마다 팰린드롬을 출력한다. 만약, 가능한 팰린드롬이 여러 가지라면 아무거나 출력한다. 팰린드롬을 만들 수 없는 경우에는 0을 출력한다.

풀이

string을이용해서 풀었습니다. string 배열에 값을 입력하고, 팰린드롬일때 ,아닐 때 의 값을출력하는 함수, 팰린드롬진위여부 확인함수 2개를 이용합니다. 코드를 보면 이해가 쉬울것이고, 주의해야할 것은 33행과 35행의 변수선언입니다. ba,ababa일때 ba와 ababa만 비교하고 ababa와 ba를 비교하지않으면(예를들어 버블정렬처럼 변수 선언 시) 0이 출력됩니다. 그리고 37행은 같은 문자열은 무조건 팰린트롬이 될 수 없으므로 연산을 건너뛰게해줍니다.

코드

#include<iostream>
#include<string>
using namespace std;
string s[100];
void func1();
bool func2(string x);
int k;
int main()
{
	cin.tie(0); cin.sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
	{
		func1();
	}
}
bool func2(string x)
{
	for (int i = 0; i < x.size() / 2; i++)
	{
		if (x[i] != x[x.size() - i - 1])
			return false;
	}
	return true;
}
void func1()
{
	cin >> k;
	for (int i = 0; i < k; i++)
		cin >> s[i];

	for (int i = 0; i < k ; i++)
	{
		for (int j = 0; j < k; j++)
		{
			//i==j면 같은 글자이므로 절대 불가능
			if (i == j)continue;
			//팰린드롬이면
			if (func2(s[i] + s[j]))
			{
				cout << s[i] + s[j] << '\n';
				return;
			}
		}
	}
	//다 비교했는데도 팰린드롬아니면 0출력
	cout << 0 << '\n';
}

결과

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

문제

한신이는 대학교에서 "복붙의 달인"으로 유명하다. 한신이는 타이핑 속도가 느리기 때문에 대학에서 가능한 모든 일을 복붙으로 해결한다. 그는 n개의 문자를 입력하는데 있어서 n초의 시간이 걸리지만 뛰어난 "붙여넣기" 스킬을 이용하면 어떠한 개수의 문자도 단 1초만에 타이핑 할 수 있다. 만약 한신이가 "bana"를 복사한 상태에서 "banana"를 타이핑한다면, "bana" 붙여넣기 1초, 'n' 입력, 'a' 입력으로 총 3초가 걸린다. 한신이가 클립보드에 저장한 p를 알고 있을 때 s를 입력하는데 걸리는 최소 시간을 계산해보자!

입력

첫 번째 줄에는 테스트케이스의 개수 T(T ≤ 25)가 입력된다. 각 테스트케이스는 한 줄에 2개의 문자열 s와 p가 공백으로 구분되어 입력되며 한신이는 p를 복사하여 s를 만들어 내는 것을 목표로 한다. s의 최대 길이는 10,000이고, p의 최대 길이는 100이다.

출력

각 테스트 케이스에 맞는 한신이가 p를 이용하여 s를 타이핑할 때 걸리는 최소 시간(초 단위)을 출력하라!

풀이

string에 부분문자열을 구할 수 있는 substr기능으로 쉽게 풀 수 있습니다. 정답을 구하기위해선 일단 비교연산을 최대 s.size()만큼 해야하겠죠?(15행) 그리고 18행을 보면, s의 현재인덱스~p.size()만큼의 문자열이 p라면 start변수에 p.size()만큼 더해야합니다.(복붙하고 다시 또 복붙할게있나 확인하는연산), 아니라면 start를 한칸 옮겨주면서 다시 비교합니다. 한번 비교를 끝내고 연산 횟수를 카운팅해주며 최소횟수를 출력하면됩니다.

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int t;
	cin >> t;
	string s, p;
	for (int i = 0; i < t; i++)
	{
		int ans = 0;
		cin >> s >> p;
		int start = 0;
		//최대 s크기만큼연산
		while (start<s.size())
		{
			//s의 현재 부분문자열이 p면
			if (s.substr(start, p.size()) == p)
				//p사이즈만큼 건너뜀
				start += p.size();
			//아니면,start를한칸 옮김
			else
				start++;
			//연산한번 하고나서 한번씩카운팅
			ans++;
		}
		cout << ans << endl;
	}
}

결과

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

문제

바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 놓고 왔다는 것이었다. 원피스를 가진 자는 이 세상을 가질 수 있다는 매혹적인 얘기였다.

모두들 말도 안 된다고 고개를 저었지만 교정이는 동료를 모아 원피스를 찾아 여행을 떠났다. 하늘섬을 지나 어인섬도 지나고 사황을 무너뜨린 뒤 교정이와 동료들은 결국 원피스의 위치가 적힌 결정적인 단서를 찾아냈다. 이 단서는 한 눈에 봐서는 해독이 어려웠다. 왜냐하면 여기에는 그저 알파벳 대문자들이 연속해서 적혀있었기 때문이다.

하지만 천재적인 두뇌를 가진 교정이의 동료이자 해적단의 항해사 진아는 단번에 이 단서에 어떤 특정 문자열이 여러 번 등장한다는 것을 직감했다.

이 특정 문자열이 어떤 문자열인지는 잘 알 수 없었던 진아는 자신이 생각한 모든 문자열이 이 단서에서 총 몇 번 등장하는지 알아보기로 했다. 아마도 가장 많이 등장한 문자열이 원피스의 위치를 알려줄 것이라고 생각했기 때문이다.

진아는 밀짚모자 해적단의 프로그래밍 담당인 당신에게 도움을 요청했다. 단서 전체에 진아가 원하는 문자열이 몇 번 등장하는지 알아내는 프로그램을 작성하라.

입력

입력의 첫 줄에는 해적단이 획득한 단서의 문자열 H가 주어진다.(0 < |H| ≤ 100,000)

입력의 두 번째 줄에는 진아가 H에서 등장 횟수를 알고 싶은 문자열 N이 주어진다.(0 < |N| ≤ 10)

단, N과 H는 공백 없는 문자열로 주어지며, 모두 알파벳 대문자로 이루어져 있다.

출력

H에서 N이 몇 번 등장하는지 출력한다.

풀이

이런 "A문자열에서 B문자열이 몇번나오냐?" 문제를 효율적으로 풀 수 있는 KMP알고리즘이있습니다. 

아래의 저의 풀이는 O(N*M)이지만, KMP알고리즘을이용한 풀이는 무려 O(N+M)입니다.. 그런데 아직 제가 KMP알고리즘을 몰라서 다음에 다시 이 방법으로 풀어보려합니다.(알고계시면 좋을 것 같아서..)

제 풀이 중 어려운 것은 없지만 A와 B를 비교 하기위해 12행의 조건식을 사용한것을 이해하셔야합니다.  이렇게 일일이 비교하는것입니다. 

그리고 19~22행은 B문자열이 A에없을 때 빠져나오는과정입니다. 28행에서 check가 true면 해당 문자열이 A에 있는것이므로 카운팅해줍니다.

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int t;
	string s, p;
		//횟수
		int cnt = 0;
		cin >> s >> p;
		//정확히 s.size()-p.size()+1번 비교함
		for (int i = 0; i<s.size() - p.size() + 1; i++)
		{
			//문자열이 있는지 확인하는 변수
			bool check = true;
			for (int j = 0; j < p.size(); j++)
			{
				//없으면
				if (s[i + j] != p[j])
				{
					check = false;
					break;
				}
			}
			//true면 B가 A에 존재하는거임.
			if (check)cnt++;
		}
		cout << cnt << endl;
}

결과

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

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

풀이

이 문제를 dp로 풀어야겠다고 생각한분들 대단합니다.. 단순히 배열에 값 넣어서 규칙에맞게 푸는줄알았는데 절대안되더군요 그리고 규칙을 찾으려해도 이미 보기에서 4일때 41이라서 직접규칙을 찾을 엄두도안났네요.. 그래서 dp로 답을구한분들의 풀이를 참고하였습니다. dp인걸 알고나서는 dp연산을위한 배열선언 -> 초기값 설정 ,, 이 두 가지가 기본이잖아요? 어려웠던 부분은 dp[n][2]가 아닌 dp[n][3]으로 선언해야한다는 것입니다.

초기값설정을 위해 규칙을 알아봅시다. n=1일때, 총3가지경우가 나옵니다.(호랑이가 없을 때, 왼쪽에 호랑이 있을 떄, 오른쪽에 있을 때) 각각의 경우를 1로(다 가능한 경우이므로 0이아닌 참값으로설정) 초기화 하고 n=2일떄,n=3일떄.... 의 경우의수를 구하면됩니다. 위에서 언급한 3가지의 케이스를 이용하여 각각의 경우에 대해 가능한 경우의수를 담아야합니다. dp배열을 선언하는 것과 이 연산의 식 세우기가 어렵습니다.

결론적으로, dp[n][0]+dp[n][1]+dp[n][2]는  2*n공간에서 호랑이를 배열할 수 있는(호랑이가없는경우도 하나의경우로포함됨) 모든경우의 수 입니다.

코드

#include<iostream>
using namespace std;
int dp[100001][3];
//arr[x][0]=x층 아무도없을 떄
//arr[x][1]=x층 왼쪽에 호랑이O
//arr[x][2]=x층 오른쪽에 호랑이O
int main()
{
	int n;
	cin >> n;
	//n=1일때 ==초기값설정
	//n=1일때 3가지경우이므로 각 경우 1로설정
	dp[1][0] = dp[1][1] = dp[1][2] = 1;
	for (int i = 2; i <= n; i++)
	{
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
	}
	cout << (dp[n][0] + dp[n][1] + dp[n][2]) % 9901 << endl;
}

결과

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

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

풀이

그리디기법을 기반으로한 시뮬레이션(구현)문제입니다. 두 문자열을 비교했을 떄 두 문자열의 차이(비교했을 때 다른 문자의 개수)가 최소가 될때의 차이를 구해야하는데, 사실 "a문자열에서 b문자열의 갯수를 일일이 찾는 문제" 를 구현한코드를 살짝 응용했다고볼 수 있습니다. 15행의 조건식이 다소 어렵다고 느껴지지만 직접 적어보면 이해가 갈 겁니다. "apple"과 "chococake" 에서 "apple" 이 "chococake"문자열 안에 포함되어있는지를 알아보는 과정을 직접 적어보시고 15행의 조건식, 18행의 조건식을 이해하기바랍니다. 그리고 문제는 차이의 최솟값을 구하므로 20~21행에서 차이를 발견하면 카운팅해주고 18행의 연산을 한번 마칠 때 마다 차이의 갯수를 가장작은값으로 초기화시켜주면되겠습니다. 

코드

#include<iostream>
#include<algorithm>
#include<string>
int arr[50];
using namespace std;
int main()
{
	string a, b;
	cin >> a >> b;
	int a_len = a.size();
	int b_len = b.size();
	//문자열의 최대길이가 50이므로 최악의경우 정답50가능
	int ans = 50;
	//하나씩 비교하며 
	for (int i = 0; i <b_len-a_len+1; i++)
	{
		int cnt = 0;
		for (int j = 0; j <a_len; j++)
		{
			//다를 떄마다 ++
			if (b[i + j] != a[j])
				cnt++;
		}
		//문제의 정답을 구하기위해 매번초기화
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}

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

문제

두 자연수 N과 P를 가지고  다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는  숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 

예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67*67 = 4489를 31로 나눈 나머지 25이다. 다음에는 25*67 = 1675를 31로 나눈 나머지 1, 다음에는 1*67 = 67을 31로 나눈 나머지 5가 차례대로 출력된다. 다음에는 5*67 = 335를 31로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.

즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 숫자 25, 1, 5가 계속 무한히 반복되게 된다.   또 다른 예로, N=9, P=3을 가지고 시작하면, 9*9 = 81이고 3으로 나눈 나머지는 0이며, 0*3 = 0이고 3으로 나눈 나머지도 0이기 때문에 처음 9를 제외하면 0이 무한히 반복되게 된다. 

N과 P를 입력받아 위와 같이 정의된 연산을 수행하였을 때,  반복되는 부분에 포함된 서로 다른 숫자의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 처음 시작하는  N과 P가 공백을 사이에 두고 주어진다. 단, 1<=N<=1,000, 2<=P<=97이다.  

출력

첫째 줄에 반복되는 부분에 포함된 서로 다른 숫자의 개수를 출력한다.

풀이

언제나 그렇듯 문제만 잘 이해하면 쉬운문제입니다. 

구현 할 때 문제를 잘 이해해봅시다. 숫자가 계속 순환하면서 싸이클을 이룰 때, 어떤특징을 가질까요? 싸이클의 개수를 구하는문제이므로 순환되는 수의 횟수를 담은 배열선언까지는 많은 분들이 할 수 있을것이고, 그러고나서 중요한 것은 숫자를 세다가 2번세는 경우가 나올 때 연산을 마치는것입니다. 예를들어 25->1->5일때 5다음에 25가 나올때 셈횟수가2가되는데 그렇다면 또 다시 같은 p로 나누기 때문에 25->1->5로 계속 무한히 반복할게 자명하기때문입니다.(생각을 잘해보세요.) 이런 아이디어만 구현할줄 알면됩니다. 마지막으로,순환되는 수는 0~p-1까지이므로 15행처럼 0부터 p전까지만 확인하면됩니다.   

코드

#include<iostream>
#include<vector>
using namespace std;
int check[1001];
void func(int x);
int n, p;
int main()
{
	cin >> n >> p;
	int cnt = 0;
	//계산함수
	func(n);

	//check[]가 2인 갯수 출력
	for (int i = 0; i <p; i++)
	{
		if (check[i] == 2)cnt++;
	}
	cout << cnt << endl;
}
void func(int x)
{
	//한번 나온값이 또 나오면?
	//또 나올 떄 까지의 과정들이 싸이클임
	if (check[x] == 2)return;
	check[x]++;
	func(x * n % p);
}

결과

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

문제

최근에 진솔이는 로봇 공학을 하기 시작했다. 그래서 포커 카드가 완전한 세트인지 확인하는 로봇을 만들기로 결심했다.

그는 프로그램을 작성하는 일을 분담했다. 그 프로그램은 카드의 모양(스페이드(♠), 하트(♡), 다이아몬드(♢), 클럽(♣))을 인식하는 것이다. 문제를 간단하게 하기 위해서 모든 카드는 하나의 모양과 하나의 숫자를 가진다고 가정한다.

여기서 그 모양은 실제 그림 대신 문자로 대체한다. P,K,H,T에 해당한다. 그리고 숫자는 1~13에 해당하는 정수이다. 로봇은 각각의 카드를 TXY의 형태로 '카드 이름'을 정하는데 T는 모양에 해당하고 XY는 숫자에 해당한다. 만약 만약 숫자가 1자리 숫자이면 X=0에 해당한다. ex) 01.

만약에 모양이 P이고 숫자가 9이면 P09이다.

완벽한 카드 한 세트는 52개로 이루어져 있다. (4 (모양)x 13(숫자))

로봇은 모든 카드의 '카드이름'을 읽고 문자열 S로 결합한다.

이제 진솔이가 프로그래밍 하는 것을 도와주자.  문자열을 읽어 얼마나 많은 카드를 잃어버렸는지 세면 된다.

만약에 2개의 같은 카드가 존재한다면 GRESKA이라고 출력하면 된다.

입력

오직 1줄만 문자열 S(1 ≤ |S| ≤ 1000)가 들어온다. 이것은 현재 가지고 있는 카드 이름에 해당한다.

출력

만약 똑같은 카드가 존재한다면 GRESKA을 출력한다.

그렇지 않으면 4개의 정수를 공백 문자로 구분하여 출력한다. 각각 P, K, H, T에 해당한다.

풀이

이런 구현문제를 어렵다고 생각하는분들은(저같은) 노트에 간단하게라도 어떻게 배열, 변수등을 선언하고 계산해서 출력할까?라고 생각하고 그 적어둔것을 코드로 옮겨보시고 생각은 되는데 막상 코드작성이 안되는 분들은 다른 분들의 코드를 보고 배우는게 좋을것같고 '이게맞는것같은데 코드가 왜 안돌아가지?' 싶으신분들은 거기서 더 생각하고 고민하는 노력을 해보세요.(확실히 노트에 적어보고 고민하고 하다보니 코드작성 때 수월하고 대충 이렇게 코드짜겟다고 적은걸 코드로 적어가다보니 여유가 생기네요.)

이 문제의 핵심은 각 문자(p,k,h,t)별로 1~13까지의 카드의 셈 횟수를 담을 2차원배열(중복되면 greksa출력해야함)을 선언하고, 입력된 카드의 수를 세기위한 1차원배열의 선언이라고 생각합니다. 딱히 어려운건 없고 39행에서 중복된 같은 카드가 생겼을 때 greksa를 출력하고 종료하는 코드를 작성함으로써 문제 조건을 만족시킬 수 있습니다. 코드를 보면 이해가 쉬울거에요. 

코드

#include<iostream>
#include<string>
using namespace std;
int card_num[4];
int card[4][14];
int main()
{
//스페이드:P 하트:K 다이아:H 클럽:T
	string s;
	cin >> s;
	char a;
	int b, c, d;
	int temp = 0;
	for (int i = 0; i < s.size(); i += 3)
	{
		a = s[i];
		b = s[i + 1] - '0';
		c = s[i + 2] - '0';
		d = b * 10 + c;
		switch (a)
		{
		case 'P':
			temp = 0;
			break;
		case 'K':
			temp = 1;
			break;
		case 'H':
			temp = 2;
			break;
		case 'T':
			temp = 3;
			break;
		}
		//만약 같은 수가 있다면 greksa출력
		//card[][]=1이면 greksa출력
		card[temp][d]++;
		card_num[temp]++;
		if (card[temp][d] == 2) 
		{
			cout << "GRESKA" << endl;
			return 0;
		}
	}
		for (int i = 0; i < 4; i++)
		{
			cout << 13 - card_num[i] << " ";
		}
		cout << endl;
	
	
}

결과