코딩무식자 전공생

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

문제

준표와 세준이는 서로 솔루션을 토론 하면서 다른 사람이 자신들의 솔루션을 듣지 못하게 하도록 서로 메시지를 주고받을 때 메시지를 암호화 하여서 주고받았다. 암호를 만드는 방법은 다음과 같다. 먼저 암호화 할 문자열을 1,1부터 위에서 아래 순서대로 채운다. 그리고 가장 밑의 행을 채운 후에는 오른쪽 열에서 다시 같은 과정을 반복한다.

만약에 "abcdefghijkl" 이라는 문자열을 3개의 열로 암호화 한다고 하자. 그러면 다음과 같이 표를 채울 수 있을 것이다.

그런 후에는 이제 왼쪽-> 오른쪽, 오른쪽-> 왼쪽, 왼쪽->오른쪽 ... 으로 읽으면서 다시 문자열을 만든다. 위의 경우에는 "aeijfbcgklhd" 가 될 것이다.

우리가 할 일은 다음과 같다. 암호화 된 문자열과 몇 개의 열로 암호화를 하였는지 주어져 있을 때 원래의 문자열을 구하는 프로그램을 작성하여라.

입력

열의 개수 K(1≤K≤20)가 주어지고 두 번째 줄에는 암호화 된 문자열(모두 영소문자)이 주어진다. (문자열의 길이는 200 이하이며 K의 배수이다.)

출력

첫 줄에 원래의 문자열을 출력한다..

풀이

이런 특정한 순서대로 입력된 수를 다시 출력 하는문제들은 노트에 대고 규칙을 찾아보면 금방 풀 수 있습니다. 

문제에서 문자열의 최대길이는 200이고 열의 최대길이는 20이므로 행은 최대 10임을 알 수 있습니다. 곧, 문제의 표를 만들기 위한 2차원 배열의 사이즈는 

map[10][20] 이 최대입니다. 저는 문제의 표를 만들고 규칙대로 풀었는데, 표를보면 짝수행은 정방향, 홀수행은 역방향으로 문자들이 이어집니다.

짝수행일 때 어떻게 표를 만들까요? 

2행을 예로들면, map[2][0]=s[0], map[2][1]=s[7], map[2][2]=s[8]인데, 규칙을 보면 각 값들이 (행*k) + 0, (행,*k)+1, (행*k)+2의 규칙성을 볼 수 있습니다.

홀수행일 때 3행을 보면 map[3][0]=s[11], map[3][1]=s[10], map[3][2]=s[9]인데 각 값들이 (행*k)+2, (행*k)+1, (행*k)+0의 규칙성을 갖습니다.

이를 소스코드로 구현 후 조건대로 출력하면됩니다.

코드

#include<iostream>
#include<string>
using namespace std;
char map[10][20];
int main()
{
	int k;
	string s;
	cin >> k;
	cin >> s;
	for (int i = 0; i < s.size() / k; i++)
	{
		if(i%2==0)//짝수행
			for (int j = 0; j < k; j++)
			{
				map[i][j] = s[i * k + j];
			}
		else
		{
			int c = k - 1;
			for (int j = 0; j < k; j++)
			{
			
				map[i][j] = s[i*k+c];
				c--;
			}
		}
	}
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < s.size() / k; j++) {
			cout << map[j][i];
		}
	}
	cout << endl;
}

결과

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

문제

N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이기게 된다. 세 장의 카드가 (7, 8, 10)인 경우에는 합은 7+8+10 = 25가 되고 일의 자리 수는 5가 된다. 어떤 사람이 받은 카드가 (7, 5, 5, 4, 9)인 경우 (7, 4, 9)를 선택하면 합이 20이 되어 일의 자리 수는 0이 되고, (5, 5, 9)를 선택하면 합이 19가 되어 일의 자리 수는 9가 된다. 게임을 이기기 위해서는 세 장의 카드를 선택할 때 그 합의 일의 자리 수가 가장 크게 되도록 선택하여야 한다.

예를 들어, N=3일 때

• 1번 사람이 (7, 5, 5, 4, 9),
• 2번 사람이 (1, 1, 1, 1, 1),
• 3번 사람이 (2, 3, 3, 2, 10)의 

카드들을 받았을 경우, 세 수의 합에서 일의 자리 수가 가장 크게 되도록 세 수를 선택하면

• 1번 사람은 (5, 5, 9)에서 9,
• 2번 사람은 (1, 1, 1)에서 3,
• 3번 사람은 (2, 3, 3)에서 8의

결과를 각각 얻을 수 있으므로 첫 번째 사람이 이 게임을 이기게 된다.

N명에게 각각 다섯 장의 카드가 주어졌을 때, 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 찾는 프로그램을 작성하시오. 가장 큰 수를 갖는 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

입력

첫 줄에는 사람의 수를 나타내는 정수 N이 주어진다. N은 2이상 1,000이하이다. 그 다음 N 줄에는 1번부터 N번까지 각 사람이 가진 카드가 주어지는 데, 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어진다. 각 정수 사이에는 한 개의 빈칸이 있다.

출력

게임에서 이긴 사람의 번호를 첫 번째 줄에 출력한다. 이긴 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

풀이

구현문제를 풀 때 마다 항상 느끼는건데 어려운 자료구조,알고리즘이 들어가있지않은 문제를 푸는데도 코딩하는데 어려움을 느끼는 저의 무능함을 반성하게됩니다..(거의 1년 째 되가는데도...)

이 문제에서 중요한 건 20~33행에 이르는 4중 반복문을 구현할 수 있느냐입니다. 모든 경우를 따져야 하므로 22~26행처럼 작성해야 각각의 인원들이 갖고있는 5개의 카드의 자릿수의 최고3조합을 따져볼 수 있습니다. 이 때 큰숫자3개의조합이 가장큰 일의자리를 갖는게 아니므로 각각의카드값들을 정렬할 필요는없습니다. 그리고 각각의 인원별로 자릿수가 최대인 값을 저장해둡니다. 그리고 32행을 살펴보면 각 인원의 최고자릿수값을 저장해둠과 별개로 35행의 비교연산을 위해 전체의 최대값을 구해놓습니다. 마지막으로 배열에 저장해둔 값을 최고값과 비교하며 그때의 index를 출력합니다.

**소스코드의 주석을 보면 이해가 갈겁니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int arr[1000][5];
int score[1000];
int main()
{
	int n;
	cin >> n;
	vector<int>v;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			cin >> arr[i][j];
		}
	}
	//최대값을 구하자
	int max_value = 0;
	//각 인원의 최대값을 구하기위해 22행수행
	for (int i = 0; i < n; i++)
	{
		//5개 카드중 3개조합으로 최대값구하기
		for (int j = 0; j < 5; j++)
		{
			for (int k = j + 1; k < 5; k++)
			{
				for (int l = k + 1; l < 5; l++)
				{
					//각 인원의 최대값 저장
					score[i] = max(score[i], (arr[i][j] + arr[i][k] + arr[i][l]) % 10);
				}
			}
		}
		//비교연산을 위해 전체 최대값저장
		max_value = max(max_value, score[i]);
	}
	int index = 0;
	//각 인원의 값과 비교해가며 최대값일 때 index출력
	for (int i = 0; i < n; i++)
	{
		if (score[i] == max_value)
			index = i + 1;
	}
	cout << index << endl;
}

결과

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

문제

상근이는 체스판을 만들려고 한다.

체스판은 검정칸과 흰칸으로 이루어져 있다. 가장 왼쪽 위칸의 색은 검정색이고, 나머지 색은 검정과 흰색이 번갈아가면서 등장한다. 검정색은 'X'로, 흰색은 '.'로 표시한다.

상근이의 체스판은 R행 * C열로 이루어져 있어야 한다. 또, 각각의 행의 높이는 문자 A개만큼 이며, 각각의 열의 너비는 문자 B개 만큼이다. 예제 출력을 보고 이해하면 쉽다.

R, C, A, B가 주어졌을 때, 상근이의 체스판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 두 양의 정수 R과 C가 주어진다. (1 ≤ R, C ≤ 10)

둘째 줄에 두 양의 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 10)

출력

출력은 R * A행 C * B열로 이루어져 있어야 하며, 문제에서 설명한 상근이의 체스판을 출력한다.

풀이

별찍기 문제 응용문제라고 생각하면됩니다. 다만, 반복문을 어디까지 이해하고 쓸줄 아느냐가 중요합니다.

처음엔 반복문을 구성할 때 행에 대해 for(int i=0; i<r*a;i++), 열에 대해 for(int j=0; j<c*b;j++)이렇게 반복문을 작성하였는데 이렇게 작성하면 문제에서 주어진 규칙성을 응용하지않고 하나하나 규칙을  따로 찾아서 구현해야하므로 까다롭기 때문에 반복되는 규칙을 곧바로 코드로 옮기면 풀이가 쉬워집니다. 소스코드는 말보다 직접보는게 이해가 빠를 것 같아서 주석으로 달아놓았고, 중요한 건 19행의 조건문입니다. 

행과 열에서 각각 덩어리로 구성되는 문자열 "xxx", "..."을 각각 하나로 보되 각각 a,b만큼 찍히는만큼 하나로 보는겁니다.

보기에서 1행과2행을 한덩어리로 보고, 열에서 "xxx", "..."을 각각 한 덩어리로 보면 i,j로 갖고노는 단순 반복문구성이됩니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int r, c, a, b;
	cin >> r >> c >> a >> b;
	//5행을
	for (int i = 0; i < r; i++)
	{
		//2번씩 출력=총 10줄
		for (int j = 0; j < a; j++)
		{
			//1열당 5개의덩어리
			for (int k = 0; k < c; k++)
			{
				//그 5개가 각각 3개의문자이룸
				for (int l = 0; l < b; l++)
				{
					if ((i + k) % 2 == 0)
						cout << "X";
					else cout << ".";
				}
			}
			cout << endl;
		}
	}
}

결과

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

문제

평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 중 하나이다. 그림-1은 1번, 2번, 3번 세 장의 색종이가 순서대로 놓인 상태를 보여준다.

그림-1

여기에 그림-2에서 보인 것처럼 4번 색종이가 하나 더 놓이면 3번 색종이는 완전히 가려서 보이지 않게 된다. 그리고, 1번 색종이와 2번 색종이는 부분적으로 가려 보이며, 4번 색종이는 완전히 보이게 된다.

그림-2

N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분의 면적을 구하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 색종이의 장수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 이어서 N장의 색종이에 관한 입력이 각 색종이마다 한 줄씩 차례로 주어진다. 색종이가 놓이는 평면은 가로 최대 101칸, 세로 최대 101칸으로 구성된 격자 모양이다. 격자의 각 칸은 가로, 세로 길이가 1인 면적이 1인 정사각형이다. 

편의상 가로 6칸, 세로 6칸으로 이루어진 격자의 예를 들어 설명하면, 각 칸에 표시된 값 (a,b)는 해당 칸의 번호를 나타낸다. 가장 왼쪽 아래의 칸은 (0,0) 가장 오른 쪽 위의 칸은 (5,5)이다. 

색종이가 놓인 상태는 가장 왼쪽 아래 칸의 번호와 너비, 높이를 나타내는 네 정수로 표현한다. 예를 들어, 위 그림에서 회색으로 표시된 색종이는 (1,4)가 가장 왼쪽 아래에 있고 너비 3, 높이 2이므로 1 4 3 2로 표현한다. 색종이가 격자 경계 밖으로 나가는 경우는 없다. 

출력

입력에서 주어진 순서에 따라 N장의 색종이를 평면에 놓았을 때, 입력에서 주어진 순서대로 각 색종이가 보이는 부분의 면적을 한 줄에 하나씩 하나의 정수로 출력한다. 만약 색종이가 보이지 않는다면 정수 0을 출력한다. 

풀이

좌표상에서 색종이(사각형)가 겹칠 때 겹치는 부분의 넓이, 각 사각형의 보이는 넓이 등의 문제는 각 색종이(사각형)를 좌표상에 각각의 숫자로 칠하고 칠해진 부분의 합을 출력하면됩니다. 

이 문제도 살펴보면, 2가지색종이를 칠할 때 첫번째 색종이의 좌표들을 모두 1로 칠하고 그다음 색종이를 2, 다음 색종이를 3.... 이렇게 칠하면 최종적으로 좌표상에 칠해져있는 숫자의 합이 그 색종이의 부분넓이(문제에서 원하는 답)가 됩니다.

코드

#include<iostream>
#include<vector>
using namespace std;
int map[102][102];
int main()
{
	int n;
	int x, y, w, h;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y >> w >> h;
		for (int a = x; a < x + w; a++)
		{
			for (int b = y; b < y + h; b++)
			{
				map[a][b] = i;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		int sum = 0;
		for (int a = 0; a < 101; a++)
		{
			for (int b = 0; b < 101; b++)
			{
				if (map[a][b] == i)
					sum++;
			}
		}
		cout << sum << endl;
	}
}

결과

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

문제

수많은 토너먼트를 거쳐 최종 플레이어 $$N명이 남아있다. 각 플레이어는

$$M장씩의 숫자가 적힌 카드를 가지고 있으며, 이들은 매 턴 자신이 가진 카드 중 가장 큰 카드를

두고 비교를 하는데, 그 카드들 중 가장 큰 수를 가진 플레이어가 1점을 획득한다. 그 턴에

사용된 카드는 버리기로 한다. ( 가장 큰 수를 가진 플레이어는 여러 명일 수 있다. )

$$M번의 경기 후 가장 많은 점수를 획득한 플레이어는 몇 번 플레이어인가 ?

입력

입력의 첫 줄에 플레이어의 수 N과 가진 카드 수 M이 입력 된다. (2≤N≤100,1≤M≤100)

그 다음 N줄에 걸쳐 각 플레이어가 들고 있는 카드에 적힌 숫자들이 입력된다. (1≤ 카드에 적힌 숫자 ≤100)

출력

최종 승자의 번호를 출력한다.

플레이어의 번호는 1번부터 $$N번까지 입력받은 순서로 주어진다고 가정한다.

가장 많은 점수를 획득한 플레이어가 여러 명일 경우, 빈칸을 사이에 두고 플레이어들의

번호를 오름차순으로 출력한다.

풀이

규칙찾기문제는 규칙만 찾으면  구현이 쉬운반면 이런 시뮬레이션 구현문제는 확실히 기본적인 구현능력이 있느냐 없느냐를 판단하기에 좋은 것 같습니다. 말그대로 생각한 것을 그대로 소스로 구현하는 능력이 필요합니다. (기업의 코딩테스트가 어려운 알고리즘 문제가 아닌 시뮬레이션,구현문제를 많이 내는 이유가 이런 것 때문 아닐까요??)

소스코드를 보면 알겠지만 말그대로 의식의 흐름대로 풀어나갔습니다. 어려운 내용은 없고 설명은 주석으로 대체하겠습니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100][100];
int score[100];
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < m; j++) 
			cin >> arr[i][j];
		sort(arr[i], arr[i] + m);
	}
	//갖고있는 3장씩의 카드중
	for (int i = 0; i < m; i++)
	{
		//값을 비교할 초깃값을 0으로설정
		int temp = 0;
		//가장 큰값구하고
		for (int j = 0; j < n; j++)
			temp = max(temp, arr[j][m - i - 1]);
		//구해진 가장 큰값을 가진 사람점수++;
		for (int j = 0; j < n; j++)
			if (temp == arr[j][m - i - 1])
				score[j]++;
	}
	//가장큰 값을 구하고,
	int max_score = 0;
	for (int i = 0; i < n; i++)
		max_score = max(max_score, score[i]);
	//그 값을 가지는 사람을 출력
	for (int i = 0; i < n; i++)
		if (max_score == score[i])
			cout << i + 1 << " ";
	cout << endl;
}

결과