코딩무식자 전공생

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

결과

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

문제

m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.

그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.

박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.

출력

각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.

풀이

삼성sw exprt 문제에서 본 것 같은데 단순히 문제를 코드로 구현할 수 있는지를 보는 문제입니다.

각 열 마다 박스가 움직이는 횟수를 알아야하고(box변수), 모든 열을 조사하여 박스의 총 이동횟수를 구해야합니다(ans변수). 방법1(30행~36행)은  박스가 땅에 떨어질때 횟수를 세므로, 마지막인덱스-현재위치-박스움직임의횟수 로 구할 수 있습니다. 방법2는 방법1을 개선한 코드로, 더 직관적이라고 할 수 있습니다.

코드

#include<iostream>
#include<algorithm>
int map[100][100];
using namespace std;
int main()
{
	int t,m,n;
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		//답을 출력하기위한 ans변수
		int ans = 0;
		cin >> m >> n;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> map[i][j];
			}
		}
		for (int i = 0; i < n; i++)
		{
			//각 열 마다 박스이동횟수 초기화
			int box = 0;
			for (int j = m - 1; j >= 0; j--)
			{
				//방법1
				//현재자리가 박스 놓여져있을 때
				if (map[j][i] == 1)
				{
					//마지막행인덱스-현재위치-움직인박스길이
					ans += (m - 1) - j - box;
					//박스 한칸움직임.
					box++;
				}

				//방법2
				/*if (map[j][i] == 0)
					box++;
				else
					ans += box;*/
			}
		}
		cout << ans << '\n';
	}
}

결과

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

문제

틱택토(Tic-Tac-Toe)는 오목과 아주 유사한 형태의 보드게임이다.

게임 방법은 아래와 같다.

1. 종이 위에 가로줄 2줄 세로줄 2줄을 그린다.
2. 이렇게 생긴 9칸 위의 빈칸에 플레이어 1은 O, 플레이어 2는 X를 번갈아가며 그린다.
3. 먼저 O 또는 X를 3개가 직선으로 이어지게 하면 승리하고 게임이 끝난다.
4. 이어지는 직선이 없고, 더는 그릴 빈칸이 없으면 무승부로 게임이 종료된다.

남녀노소 모두 즐길 수 있는 아주 쉬운 게임이지만, 중간에 끝났는지 눈치를 못 채고 계속하는 경우가 있다. 그래서 당신은 제3의 공정하고 자비 없는 냉정한 심판을 두고 싶었다.

각 플레이어가 교대로 O 또는 X를 그린 위치가 입력되면 누가 언제 이기는지를 출력하는 프로그램을 작성하시오.

입력

첫째 게임을 먼저 시작할 플레이어의 번호가 입력된다. 플레이어의 번호는 1 또는 2이다.

다음 9개의 줄에 게임이 끝날 때까지 번갈아가며 어느 위치에 그렸는지 좌표가 입력된다. 좌표는 가로 행, 세로 열의 순으로 입력된다. 가장 왼쪽 위는 (1, 1), 가장 오른쪽 아래는 (3, 3)이다.

이미 입력된 좌표가 주어지는 경우는 없으며, 항상 게임이 끝나는 입력만 주어진다.

출력

승자가 결정되는 즉시 이긴 플레이어의 번호를 출력한다. 플레이어의 번호는 1 또는 2이다. 무승부라면 0을 출력한다.

풀이

빙고게임처럼 단순한 구현문제이지만 쉽게 구현하지못했고 다른 분의 코드를 참조했습니다.ㅠㅠ 

참조: https://hsdevelopment.tistory.com/213?category=1013710

입력을 받을 때 마다 승부의 여부를 확인합니다. 이 때 25행~28행 처럼 코드를 작성하면 입력을 받고 승부의 여부를 확인했을 때 그 이후의 모든 승부를 확인하지않게됩니다. 문제에서 "승부를 찾는 즉시 출력한다"를 만족합니다.(문제가 모호합니다. "승부를 찾는 즉시 출력한다"가 바로 출력하는게 아니라 승부 확인 후 "그 이후의 모든 연산을 하지않는다"로 해석해야합니다.) 승부는 행,열,대각선(좌->우, 우->좌) 모두 확인합니다.(브루트포스)

게임판의 크기는 [3][3]이지만 시작 좌표는 1,1 이므로 x,y의 index만 조심하면될 것 같습니다.

코드

#include<iostream>
int map[3][3];
using namespace std;
int func(int x);
int main()
{
	int num;
	cin >> num;
	int x, y;
	int value;
	int ans = 0;
	bool check = false;
	//num이1이면O표시, 2이면X표시
	for (int i = 0; i < 9; i++)
	{
		if (i % 2 == 0)value = num;
		else
		{
			if (num == 2)value = 1;
			else value = 2;
		}
		cin >> x >> y;
		x--, y--;
		map[x][y] = value;
		if (!check)
		{
			ans = func(value);
			if (ans != 0)check = true;
		}
	}
	cout << ans << endl;
}
int func(int x)
{
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (map[i][j] != x)break;
			if (j == 2)return x;
		}
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (map[j][i] != x)break;
			if (j == 2)return x;
		}
	}
	for (int i = 0; i < 3; i++)
	{
		if (map[i][i] != x)break;
		if (i == 2)return x;
	}
	for (int i = 0; i < 3; i++)
	{
		if (map[i][2 - i] != x)break;
		if (i == 2)return x;
	}
	return 0;
}

결과

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

문제

빙고 게임은 다음과 같은 방식으로 이루어진다.

먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다

다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.

차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.

이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다.

철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.

출력

첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지 출력한다.

풀이

100퍼센트 구현문제입니다. 사회자가 숫자를 부를 때 마다 빙고인지 아닌지 행,열,대각선 모두 검사해야합니다. 빙고를 확인하는 검사는 행 빙고 검사, 열 빙고 검사, 대각선(좌->우), (우->좌) 총 4가지입니다. 이것을 소스로 구현하면 끝입니다. 중요한 건 42행, 52행 처럼 바깥for문내에 sum을 0으로 초기화 시켜야 그 행 or 열 라인의 빙고를 판별 할 수 있습니다. 대각선 검사는 총 두번밖에안되므로, 그리고 규칙성을 가지므로(0,0,1,1,2,2,   0,4, 1,3, 2,2 등..) 1차원배열로 검사합니다. 그리고 실수하기 쉬운것은 빙고의 개수를 확인하는 cnt변수를 전역변수가 아닌 빙고검사함수내의 지역변수로 선언해야한다는것입니다. 한번 검사하여 빙고가아니면 총 빙고의 갯수를 세는 변수는 초기화가되어야합니다.

코드

#include<iostream>
using namespace std;
int map[5][5];
void func(int call);
bool bingo();
int main()
{
	int call;
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> map[i][j];
	for (int i = 0; i < 25; i++)
	{
		cin >> call;
		//부르는 값을 0으로바꿈
		func(call);
		//빙고확인//참이면 빙고완료
		if (bingo())
		{
			cout << i + 1 << endl;
			break;
		}
	}
}
void func(int call)
{
	//부르는 값을 0으로초기화
	for (int i = 0; i < 5; i++)
		for(int j=0;j<5;j++)
		if (call == map[i][j])
		{
			map[i][j] = 0;
			return;
		}

}
bool bingo()
{
	int cnt = 0;
	//행 빙고, 열빙고, 대각선 빙고 확인
	for (int i = 0; i < 5; i++){
		int sum = 0;
		for (int j = 0; j < 5; j++) {
			sum += map[i][j];
		}
		if (sum == 0)
			cnt++;
		}

	//열빙고
	for (int i = 0; i < 5; i++) {
		int sum = 0;
		for (int j = 0; j < 5; j++) {
			sum += map[j][i];
		}
		if (sum == 0)
			cnt++;
	}
	
	//대각선빙고: 좌에서 우
	int sum = 0;
	for (int i = 0; i < 5; i++)
		sum += map[i][i];
	if (sum == 0)cnt++;

	//대각선빙고: 우에서 좌
	sum = 0;
	for (int i = 0; i < 5; i++)
		sum += map[i][5 - 1 - i];
	if (sum == 0)cnt++;

	if (cnt >= 3)
		return true;
	else return false;

}

결과