[25-1] C++

행렬을 활용한 이중, 삼중반복문

 

오늘 정리해볼 내용은

1. 이중 벡터를 활용한 행렬 표현하기

2. 3중 반복문을 활용하여 행렬 순회하기 (1) (2)

---

 

설명에 참고할 문제는 총 2개

백준 1268

백준 11651

 

두 문제 모두 이중벡터와 삼중반복문을 활용해서 풀었는데

나도 확실하게 감이 잡히지 않아 공부할 겸 이곳에 정리해보려 한다

---

먼저 이중 벡터를 만드는 방법부터,

 

1. 이중 벡터를 활용한 행렬 표현하기

 

vector<vector<int>> vector_name (N, vector<int> (M));

 

N * M의 이중 벡터 (행렬)를 선언한다

여기에 값들을 직접 입력 받고 싶다면 다음과 같이 이중 반복문을 활용한다

for (int i = 0;i < N;i++) {
	for (int j = 0;j < M;j++) {
		cin >> vector_name [i][j];
	}
}

 

이렇게 하면, 내가 입력하는 순서대로  N * M의 이중 벡터가 채워진다

 

cf. map 

cpp에는 py의 딕셔너리와 비슷한 map이 있다

map<int, vector<int>> map_name;
   for (int i = 0; i < N;i++){
      int x = 0;
      int y = 0;
      cin >> x >> y;
      map_name [y].push_back(x);
   }

 

위 코드는 x, y 좌표를 딕셔너리 형태로 받고 있다

특징은, key 부분에 y 좌표를 넣고 value 부분에 x 좌표들을 벡터의 형태로 넣고 있다는 점

아래 그림처럼 y 좌표가 중복될 때, x 좌표들을 벡터로 저장하는 것이다

이미지 제공 윤성준(my cpp tutor)

 이런식으로 꼭 행렬이 아니라 map 으로 저장할 수도 있다

map의 장점은

빈 곳을 자동으로 채워준다는 것 (-1 2 3이면 0과 1이 없는데, 빈 vector 를 굳이 안 만들어도 됨)

key 값이 음수가 될 수 있다는 점

또 key를 자동으로 오름차순 정렬하기 때문에 sort 필요 없음

 

cf. sort 

#include <algorithm>

for (auto& pair : map_name) {
	sort (pair.second.begin(), pair.second.end());
    for (int x: pair second) { 
    	cout << x << " " << pair.first << "\n";
    }
 }

 

map으로 저장된 값들에서 저렇게 하나씩이 pair이다

pair.first = key

pair. second = value

인 셈이다

 

sort를 통해서 pair.second에 벡터로 저장된 값들을 오름차순 정렬해주면

그대로 cout 했을 때 차례대로 작은 값들부터 출력되게  된다

 

2. 3중 반복문을 활용하여 행렬 순회하기 (1) 

 

3중 반복문

for (int i = 0;i < N;i++) {
	for (int j = 0;j < K;j++) {
		for (int k = 0;k < M;k++) {
		}
	}
}

 

이렇게 3개의 반복이 이루어지는 것이다

반복의 수명을 잘 생각해보면 

loop i : i = 0 부터 총 N번 반복, i가 N번 반복, 각 i마다 j가 K번, 각 j마다 k가 M번 → 총 N × K × M번 반복

loop j : j = 0 부터 총 K번 반복, i = 0일 때, j가 K번 반복, 각 j마다 k가 M번 반복 → 총 K × M번

loop k : k = 0 부터 총 M번 반복, i = 0, j = 0일 때 M번 반복

 

그럼 이제 실제 문제에서 살펴보면~

 

---

(1) 임시반장 구하기 

먼저 전체 코드를 하나씩 설명해겠다 (main코드)

 

1. 학생에 대한 정보 입력 받기

6학년 임시반장을 정하려고 하는 상황

N명의 학생들이 1~5학년 동안 각각 몇 반이었는지에 대한 정보를 담은 행렬이다

행 수는 N개, 열 수는 5개 (1,2,3,4,5 학년)

int N;
	cin >> N;

	vector<vector<int>> student(N, vector<int> (5));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> student[i][j];
		}
	}

 

2. 이제 행렬을 순회하며 누가 제일 아는 애가 많은지(?) 찾는다

같은 반을 해본 경험이 있으면 아는 애

여기서 고려해야 할 점은 

 

A. 자기 자신은 고려할 필요 없음 continue

if (i == j)
continue;

 

자기 자신은 항상 같은 반이니까

하지만 모두가 자기 자신을 고려하면 어처피 상대적으로, 가장 아는 애가 많은 사람을 찾는데는 문제가 없음

그래서 굳이 안따져도 되는 부분이긴 하지만 논리적으로 맞으니까 넣어둔다

 

B. count ++을 해줄 수 있는 정수 선언

만일 순회하며 비교하던 중, 같다면 (= 같은 반이라면), 정수 a = 1

이전에 만들어 둔 count 라는 1차원 벡터에 a 값을 업데이트 하는 것이다

count 벡터는 N자리 1차원 벡터이고, 초기값은 [0 0 0 0 ... 0 ] 이다

 

전체 코드는 다음과 같음

vector<int> counts(N);

 

for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j)
				continue;

			int a = 0;
			for (int k = 0; k < 5; k++) {
				if (student[j][k] == student[i][k]) {
					a = 1;
				}
			}
			counts[i] += a;
		}
	}

 

Q: count [i] += a ; 위치가 헷갈려요

 

btw 여기서 사용된 3중 반복문을 살펴보면

성준이가 찰떡같이 설명을 해놨다

참고하면 됨

 

3. 가장 아는 애가 많은 학생 한 명을 찾는거니까, count 벡터에서 값이 가장 큰 학생의 index를 출력한다

int max_count = 0;
int max_index = 0;
	for (int i = 0; i < counts.size(); i++) {
		if (counts[i] > max_count) {
			max_count = counts[i];
			max_index = i;
		}
	}
	cout << max_index+1 << endl;

 

max_count 값을 업데이트 하고,

그 값의 index를 max_index에 저장한다

학생 index는 0번부터 셌으니까, 출력할 때는 +1 해주는 것 잊지 말기

 

(2) 행렬 곱셈

1. 행렬A 와 B를 입력 받는다

행렬 A 는 N * M

행렬 B 는 M * K

int N = 0;
int M = 0;
cin >> N >> M;
	vector<vector<int>> A (N, vector<int>(M));
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			cin >> A [i][j];
		}
	}

int K = 0;
cin >> M >> K;
	vector<vector<int>> B (M, vector<int>(K));
	for (int i = 0;i < M;i++) {
		for (int j = 0;j < K;j++) {
			cin >> B [i][j];
		}
	}

 

반복문을 통해서 vector 입력 받는건 이제 ok

 

2. 곱셈의 결과값을 저장할 벡터 선언

이때 벡터는 N * K 행렬이 된다

vector<vector<int>> result(N, vector<int>(K,0));

 

for (int i = 0;i < N;i++) {
	for (int j = 0;j < K;j++) {
		result[i][j] = 0;
		for (int k = 0;k < M;k++) {
			result[i][j] += frist[i][k] * second[k][j];
			}
		}
	}

result [i] [j] = 0 으로 초기화 한번 시켜주고

곱을 누적합해준다

 

그리고 출력만 해주면 끝

for (int i = 0;i < N;i++) {
		for (int j = 0;j < K;j++) {
			cout << result[i][j] << " " ;
		}
		cout << "\n";
	}

 

반복 한번이 끝나면 줄 바꿈을 시켜서

N * K 행렬 형태로 출력될 수 있게 한다