뚝딱뚝딱

💡 3차원 벡터 정의

vector<vector<vector<int>>> arr

💡 3차원 벡터 resize() 함수 사용

//n,m,h

arr.resize(n, vector<vector<int>>(m, vector<int>(h)));

💡 쌍 pair

queue<pair<pair<int,int>, int>> q;

https://www.acmicpc.net/problem/1051

💡 숫자 정사각형

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

예제 입력

3 5
42101
22100
22101

출력

9

✅ 문제 풀이

주어진 행렬에서 가능한 모든 정사각형을 구해야 함을 알 수 있다. 따라서 이 문제는 무식하게 다 접근하는 브루트포스 알고리즘을 이용해야 한다.

• 먼저 입력의 형태를 보자. 입력으로 들어오는 행렬 값이 공백으로 구분되어 있지않고 붙어있다.
  => 따라서 string으로 받고, 한 문자씩 잘라서 숫자로 바꾸어준 후 벡터에 값을 반영할 것이다.
• 벡터가 다 채워졌으면, 이제 왼쪽 상단 꼭지점을 기준으로, 배열을 순회할 것이다.
  => 무슨말이냐 하면, 배열의 각 점을 정사각형의 왼쪽 상단 꼭지점으로 생각하고, 정사각형을 찾아보는 것이다.
• 그런데, 입력을 받을 때 행과 열의 크기를 받았다. 정사각형은 가로와 세로의 길이가 같아야 하기 때문에 행과 열 중에서 더 작은 값이 정사각형의 최대 길이가 될 수 있다.
• 따라서 행과 열 중 최소의 길이가 1이었다면, 최대 정사각형 길이는 1이기 때문에 크기가 1이다. 
• 그리고 행과 열 중 최소의 길이가 1이 아니라면 그 값을 m에 저장해 두고, 다음 절차를 통해 최대 길이를 찾아낼 수 있다.
• 먼저 정사각형의 한변의 길이가 2인 것부터 찾아볼 것이다.
• 현재 왼쪽 상단 꼭지점의 위치를 (i,j)라고 할 때 길이가 2인 정사각형의 꼭짓점은 (i+1, j) (i,j+1), (i+1, j+1)이 된다.
• 따라서 k가 1일 때부터 m보다 작을 때까지 정사각형을 키워가면서 조건을 만족하는지 보면 된다.
• i+k<N이고, j+k<M이면, 해당 정사각형은 행렬안에 유효한 것이다. 따라서 이런 경우에는 (i,j)가 (i+1, j) (i,j+1), (i+1, j+1)각각과 값이 동일한지 비교해주면 된다. 
  => 값이 동일하면, answer의 기존 값과 비교해서 더 큰 값으로 answer를 갱신해주면된다.
• 참고로 answer는 행렬을 순회하기 전에 1로 초기화 하여 생성해두어야 한다.
• 모든 순회가 끝난 후 최종 answer값을 제곱한 값을 출력해주면 된다. (문제에서 정사각형의 크기를반환하라고 하였기 때문이다.)

전체 코드는 아래와 같다.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	int m = min(N, M);//작은 값이 정사각형의 한 변의 max가 됨

	vector<vector<int>> rec(N, vector<int>(M, 0));

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;

		for (int j = 0; j < str.length(); j++) {
			rec[i][j] = str[j]-'0'; //char 문자를 숫자로 바꾸는 함수는 atoi를 쓰지만, string으로 되어 있는 경우엔 인자가 맞지 않으므로,'0'을 뻬주어서 구한다.
		}
	}

	if (m == 1) {
		cout << 1;
		return 0;
	}

	int answer = 1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 1; k < m; k++) {
				if (i + k < N && j + k < M) {//사각형이 범위에 들어오는지 확인
					int t = rec[i][j];//기준이 되는 값을 저장
					if (rec[i][j + k] == t && rec[i + k][j] == t && rec[i + k][j + k] == t) {
						answer = max(k + 1, answer);
					}
				}
			}
		}
	}

	cout << answer * answer;//크기는 변의 제곱

	return 0;
}

✏ c++ 문법 알고 넘어가기!

• 2차원 벡터 선언하기 : vector<vector<int>> vec(행크기, vector<int>(열크기, 초기값));
• string의 각 문자를 숫자로 변환 : string의 각 문자를 변환할 때는 그냥 str[i]-'0'을 해주면 숫자 값을 얻을 수 있다.
  만약 char로 선언된 문자라면, atoi(문자) 메서드를 사용하면 된다.
  => string의 한 문자를 위 메서드 쓸 수 없는 이유는 인자 형태가 맞지 않아서이다.

소프티어 lv2 "금고 털이" 문제 풀이 중 pair vector와 sort사용이 익숙치 않아 정리하는 글이다.

pair vector

vector<pair<int, int>> v;

vector에서는 한 요소에 두가지 값을 함께 넣으려면, 위와 같이 pair로 묶어서 정의해 주어야 한다.

"금고 털이" 문제에서 첫번째 int 요소에는 금속의 무게를 , 두번째 int 요소에는 금속의 가치를 저장해주었다.

각각의 값에 접근하려면, v.first, v.second로 접근할 수 있다.

sort

algorithm에서 정의한 정렬 함수 sort이다.

기본적으로 오름차순 정렬이고, pair vector의 경우 첫번째 값을 기준으로 오름차순 한다.

sort(v.begin(), v.end());

이렇게 하면 vector v를 첫번째 값인 금속 무게에 대해서 오름차순 정렬해준다.

그런데 나는 금속의 가치인 두번째 값에 대해서 내림차순 정렬하고 싶었다.

그래서 sort함수에, 따로 정의한 비교함수를 인자로 넣어, 이 기준으로 정렬해 주세요~라고 요청했다.

bool compare(const pair<int, int> &a, const pair<int, int> &b){
	return a.second>b.second;
}

 위와 같은 compare 함수를 정의해 주었다.

내가 헷갈렸던 점은, 부등호의 방향이다. 

처음에는 b쪽에 크다고 했는데, 이유는 정렬할 때 뒤에 있던게 컸었다..라고 생각한 것이다. 아무튼 나의 착각이고..

내림차순이 앞이 큰거니까, 먼저 위치한 a가 클 때 true로 정의해 주는 것이다.

반대로 오름차순이면? b쪽으로 부등호가 향해야 할 것이다.

이렇게 해서 기본 of 기본인 pair vector와 sort함수에 대해 정리해보았다.

다음에는 버벅거리지 않고 바로 구현하길~

https://softeer.ai/practice/6288

💡 금고 털이

• 무게가 W인 배낭, N개의 금속 종류가 있다.
• 최대의 가치를 갖도록 금속을 담는데, 무게 W를 넘지 않아야 한다.
• 금속은 1g당 가치를 갖는다.
• 따라서 높은 가치를 갖는 순서대로 배낭에 담아야 한다.
• 금속의 무게와 가치를 갖는 pair 벡터를 이용하였다.
• pair 벡터에서 두번째 요소인 가치에 따라 내림차순 정렬 하기 위해, 비교함수인 compare를 정의해주었다.
• 내림차순 정렬 후, 각 금속에 대해서, 무게가 현재의 W를 넘지 않으면, 그 무게만큼 넣고, 그렇지 않으면 W만큼 떼어다 넣기로 한다. 넣은 무게만큼 W에서 차감하는 방식이다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool compare(const pair<int, int> &a, const pair<int, int> &b){
  return a.second>b.second;
}//두번째 요소를 기준으로 내림차순 하도록..

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int W,N;
  cin>>W>>N;

  vector<pair<int, int>> v(N);
  for(int i=0; i<N; i++){
    cin>>v[i].first>>v[i].second;
  }

  sort(v.begin(), v.end(), compare);//두번째 요소를 통해 compare 하도록 비교함수 정의
  
  int value=0;
  for(int i=0; i<N; i++){
    if(W==0) break;
    int used=(v[i].first<=W)?v[i].first:W;
    value+=used*v[i].second;
    W-=used;
  }
  
  cout<<value;
  
   return 0;
}

pair 벡터 정렬만 할 줄 알면 되므로, 아주 쉽다.

앞의 달리기 경주를 풀고 난 뒤 이 문제를 보니, 어떻게 풀어야 할지 바로 감이 잡혔다.

이 문제 역시 map을 사용하여 해결할 수 있다.

string과 int가 짝을 이루고, 주어진 string을 통해 탐색하는 과정이 필요하다면 map을 사용할 것!

풀이는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    
    
	map <string, int> m1;

	for (int i = 0; i < name.size(); i++) {
		m1[name[i]] = yearning[i];
	}

	for (int i = 0; i < photo.size(); i++) {
		int cnt = 0;
		for (int j = 0; j < photo[i].size(); j++) {
			cnt += m1[photo[i][j]];
		}
		answer.push_back(cnt);
	}
    
    return answer;
}

string을 인덱스로 갖는 map을 하나 생성하여 주어진 값들을 대입해주었다.

그리고 photo를 한 줄 단위로 읽으며 값을 카운트 해주면 된다!

이 문제를 풀려고 했을 당시 처음엔 callings vector에 저장되어 있는 이름들을 players에서 찾아 내야 한다는 생각은 했으나, 이름과 등수를 바로바로 매치할 수 있는 방법이 떠오르지 않아서.. 단순히 while/for 반복문으로 하나씩 접근할 수 밖에 없었다.

그 코드는 아래와 같았고, 역시 몇개의 case에서 시간초과 문제가 발생하였다.

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {

	int sz = players.size();
	int cnt = 1;

	for (int i=0; i<callings.size(); i++){
		string temp = callings[i];

		if (i < callings.size() - 1 && temp == callings[i + 1]) {
			cnt++;
			continue;
		}

		for (int j = 0; j < sz; j++) {
			if (players[j] == temp) {
				int target = j - cnt;
				while (target < j) {
					swap(players[j], players[j - 1]);
					j--;
				}
				cnt = 1;
				break;
			}
		}
	}
	return players;
}

시간 초과가 발생한 부분은 [players를 일일이 탐색하는 부분]+[vector의 위치를 swap하는 부분] 이다. 

vector도 제법 빠른 자료구조라 생각했는데, 자리를 바꾸는 과정은 역시 O(N)이다.

이 문제의 핵심은 map을 사용하는 것이었다!!!!

map을 총 두개 사용하여 해결하였는데, 하나는 등수(int)를 기준으로 이름을 저장한 것과, 하나는 이름(string)을 기준으로 등수를 저장한 것이다.

이렇게 하면 반복문을 돌면서 callings에 있는 이름을 일일이 찾지 않고, 이름 자체를 인덱스로써 활용하여 현재 등수를 알아 낼 수 있다!!

해결한 코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
	//답 : vector라는 자료구조를 사용하는 것보다 map으로 정렬과정을 거친 후 vector에는 최종 결과 삽입만 하기.

	vector<string> answer;

	int sz = players.size();
	map <int, string> m1;//등수 별 이름 기억해두기
	map <string, int> m2;//이름 별 등수 기억해두기

	for (int i = 0; i<players.size(); i++) {
		m1[i] = players[i];
		m2[players[i]] = i;
	}

	for (int i = 0; i < callings.size(); i++) {
		string temp = callings[i];
		int tempIdx = m2[temp];
		m1[tempIdx] = m1[tempIdx - 1];//swap과정
		m1[tempIdx - 1] = temp;
		m2[temp] = tempIdx - 1;
		m2[m1[tempIdx]] = tempIdx;

	}

	for (auto temp : m1) {
		answer.push_back(temp.second);//m1의 두번째 요소(이름)들을 넣는다.
	}

	return answer;
}

그 결과 map을 활용해서 탐색 시간을 확실히 줄일 수 있었다!!

반환하고자 하는 것은 vector이므로, m1에 등수대로 적힌 이름들을 answer에 push_back하였고 이를 반환하도록 하였다.