Feel Coding

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

멀티탭도 일단 어떤 콘센트에 꽂아야 한다. 따라서 멀티탭의 개수만큼 빼줘야 한다. 그리고 선영이의 집에는 콘센트가 한 개 있기 때문에 이것도 더해줘야 한다.

즉, 모든 콘센트의 개수 + 1 - 멀티탭의 개수이다.

이 문제에서는 콘센트라는 단어와 플러그라는 단어를 반대로 쓴 것 같다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> multiTab(n);
	int total = 0;
	for (int i = 0; i < n; i++) {
		cin >> multiTab[i];
		total += multiTab[i];
	}
	cout << total + 1 - n;
	return 0;
}

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

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	int e, s, m;
	cin >> e >> s >> m;
	int a, b, c;
	a = b = c = 1;
	int cnt = 1;
	while (true) {
		if (e == a && s == b && m == c) {
			break;
		}
		a = (a + 1) % 16;
		b = (b + 1) % 29;
		c = (c + 1) % 20;
		if (a == 0)
			a = 1;
		if (b == 0)
			b = 1;
		if (c == 0)
			c = 1;
		cnt++;
	}
	cout << cnt;
	return 0;
}

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

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	string x, y;
	cin >> x >> y;
	string a = "";
	string b = "";
	for (int i = x.size() - 1; i >= 0; i--) {
		a += x[i];
	}
	for (int i = y.size() - 1; i >= 0; i--) {
		b += y[i];
	}
	int temp = stoi(a) + stoi(b);
	string result = "";
	while (true) {
		if (temp / 10 == 0) {
			result += (temp % 10 + '0');
			break;
		}
		result += (temp % 10 + '0');
		temp /= 10;
	}
	cout << stoi(result);
	return 0;
}

C++에서 두 수 a, b 중에 어떤 수가 더 큰지, 작은지 알고 싶다면

#include <algorithm>으로 <algorithm> 헤더를 추가하고

min(a, b);

또는

max(a, b);

이렇게 하면 된다.

하지만 배열이나 벡터의 원소들 중에서 최댓값을 찾고 싶다면 min_element, max_element 함수를 사용하면 된다. 이 함수들도 <algorithm> 라이브러리에 있기 때문에 <algorithm> 헤더를 포함하면 된다.

크기가 10인 배열 arr에서 최댓값을 찾아서 maxNum이라는 변수에 저장하고 싶다면

int maxNum = *max_element(arr, arr + 10);

이렇게 하면 된다. 앞에 역참조 연산자 *를 붙이는 이유는 max_element, min_element 함수의 반환값은 최댓값이 저장된 곳의 메모리 "주소"이기 때문이다. 따라서 값을 알고 싶다면 역참조연산자를 이용하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int arr[10] = { 10, 200, 340, 28, 50, 189, 84, 39, 1, 248 };
	cout << "최댓값: " << *max_element(arr, arr + 10) << endl;
	cout << "최솟값: " << *min_element(arr, arr + 10) << endl;
	return 0;
}

이 코드를 실행하면

이렇게 배열 arr의 원소 중 최댓값과 최솟값을 알아낼 수 있다.

벡터도 마찬가지이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector<int> v = { 10, 200, 340, 28, 50, 189, 84, 39, 1, 248 };
	cout << "최댓값: " << *max_element(v.begin(), v.end()) << endl;
	cout << "최솟값: " << *min_element(v.begin(), v.end()) << endl;
	return 0;
}

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

문제에서 주어준대로 재귀로 풀면 되기 때문에 아주 쉽게 풀 수 있었다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n, r, c;
int cnt = 0;
int result;
bool found = false;

void visit(int rowStart, int rowEnd, int colStart, int colEnd) {
	if (found)
		return;
	if (rowEnd - rowStart == 1) {
		if (++cnt && rowStart == r && colStart == c) {
			result = cnt;
			found = true;
			return;
		}
		else if (++cnt && rowStart == r && colEnd == c) {
			result = cnt;
			found = true;
			return;
		}
		else if (++cnt && rowEnd == r && colStart == c) {
			result = cnt;
			found = true;
			return;
		}
		else if (++cnt && rowEnd == r && colEnd == c) {
			result = cnt;
			found = true;
			return;
		}
		else {
			return;
		}
	}
	visit(rowStart, rowStart + (rowEnd + 1 - rowStart) / 2 - 1, colStart, colStart + (colEnd + 1 - colStart) / 2 - 1);
	visit(rowStart, rowStart + (rowEnd + 1 - rowStart) / 2 - 1, colStart + (colEnd + 1 - colStart) / 2, colEnd);
	visit(rowStart + (rowEnd + 1 - rowStart) / 2, rowEnd, colStart, colStart + (colEnd + 1 - colStart) / 2 - 1);
	visit(rowStart + (rowEnd + 1 - rowStart) / 2, rowEnd, colStart + (colEnd + 1 - colStart) / 2, colEnd);
}

int main() {
	cin >> n >> r >> c;
	n = pow(2, n);
	visit(0, n - 1, 0, n - 1);
	cout << result - 1;
	return 0;
}

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

정말 역대급 어려웠던 문제였다고 생각한다. 정답률은 50%가 넘는데 그거는 예제입력조차 정답이 나오지 않아서 사람들이 제출 시도 자체를 안 해서 그러는 것 같다. 솔직히 이 문제는 예제입력에서 정답이 나왔을 때 제출하면 거의 정답일 것 같다.

이 문제에서 주의할 것은 이 파일은 소설의 챕터이기 때문에 순서를 마음대로 바꾸면 안 된다. 무조건 입력으로 주어진 순서에서 인접한 파일끼리만 합칠 수 있다.

일단 코드부터 보자면

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		vector<int> v(n + 1);
		vector<int> sum(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
			if (i == 0) {
				sum[i] = v[i];
			}
			else {
				sum[i] = sum[i - 1] + v[i];
			}
		}
		vector<vector<int>> dp(n + 1, vector<int>(n + 1));
		for (int gap = 1; gap < n; gap++) {
			for (int start = 1; start + gap <= n; start++) {
				int end = start + gap;
				dp[start][end] = INT_MAX;
				for (int mid = start; mid < end; mid++) {
					if (dp[start][end] > dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1]) {
						dp[start][end] = dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1];
					}
				}
			}
		}
		cout << dp[1][n] << '\n';
	}
	return 0;
}

테스트 케이스가 여러개라 돌리는 가장 바깥 for문을 제외하고 3중 for문이 핵심이다.

이차원 배열 dp[i][j]에는 i번째 챕터부터 j번째 챕터까지 합치는데에 드는 최소비용을 저장한다.

우리가 구하고자 하는 것은 "하나의 파일"로 합칠 때 필요한 최소비용이므로 dp[1][n]을 구하면 된다.

3중 for문 중 가장 바깥 for문은 gap을 1씩 늘려가면서 돌아가는데 dp[i][j]에서 i와 j의 차이(간격)를 정해주는 for문이다.

만약 gap이 1이면 챕터 1과 2를 합친다던지 챕터 2와 3을 합치는 것과 같이 두 개의 연속된 챕터를 합치는 것이다.

gap이 2라면 챕터 1부터 챕터3까지 합친다던지 3개의 연속된 챕터를 합치는 것이다.

3중 for문 중 두 번째 for문(중간 for문)은 start를 1씩 늘려가면서 돌아가는데 dp[i][j]에서 i를 정해주는 for문이다.

즉, start는 "몇 번째 챕터부터" 더할지를 정하는 것이다.

gap이 3이고 start가 2라면 dp[2][2+3] 즉 dp[2][5]를 구하는 것이다.

따라서 end라는 변수를 만들어 start+gap을 end라는 변수에 저장해주었다. 윗줄 예시에서 end는 2+3=5이다.

제일 안쪽 for문은 mid를 1씩 늘려가면서 돌아간다. 파일을 합칠 때에는 두 개의 파일을 합쳐야 한다.

따라서 start~mid까지의 챕터와 mid+1~end 챕터를 더하게 될 텐데 그 두 부분으로 분리되는 부분이 바로 mid이다.

예를 들어 start가 1이고 gap이 4라서 dp[1][5]를 구해야 한다면 챕터1부터 챕터5까지를 합치는 최소 비용을 구하는 것인데

챕터1/챕터2~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 1)

챕터 1~2/챕터3~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 2)

챕터 1~3/챕터4~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 3)

챕터 1~4/챕터5 이렇게 두 부분을 합칠 수도 있다. (이 경우 mid는 4)

mid의 역할이 바로 이렇다.

for문의 조건 부분이 mid <= end가 아니라 mid < end인 이유는 최소한 두 부분으로는 나눠져야 하기 때문이다.

만약 end와 mid가 같다면

챕터 1~5/없음 (mid가 5라면 즉, mid가 end와 같다면)

이렇게 챕터 1~5를 제외하면 나머지 부분은 없기 때문에 무조건 mid는 end보다 작아야 한다.

그리고 sum[i]에는 첫 번째 챕터부터 i번째 챕터까지의 합이 저장되어 있다.

따라서 sum[end] - sum[start - 1]은

(챕터1~챕터end까지의 합) - (챕터1~챕터 start-1까지의 합)이기 때문에

챕터start~챕터end까지의 합을 뜻한다.

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

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int total = 0;
		int price;
		cin >> price;
		total += price;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int num, cost;
			cin >> num >> cost;
			total += (num * cost);
		}
		cout << total << '\n';
	}
	return 0;
}

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a > 10) {
			a = (a + 5) / 10 * 10;
		}
		if (a > 100) {
			a = (a + 50) / 100 * 100;
		}
		if (a > 1000) {
			a = (a + 500) / 1000 * 1000;
		}
		if (a > 10000) {
			a = (a + 5000) / 10000 * 10000;
		}
		if (a > 100000) {
			a = (a + 50000) / 100000 * 100000;
		}

		if (a > 1000000) {
			a = (a + 500000) / 1000000 * 1000000;
		}
		if (a > 10000000) {
			a = (a + 5000000) / 10000000 * 10000000;
		}
		cout << a << '\n';
	}
	return 0;
}

지난 번에 올린 이 글에 이어지는 내용이다. (링크↓)

https://breakcoding.tistory.com/81

사실 포인터는 배열과 매우 밀접한 관련이 있다.

배열의 이름은 배열의 시작 주소이다.

이게 정말인지 궁금하다면 출력해보면 된다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	cout << arr << endl;
	return 0;
}

배열의 이름을 출력해보니 메모리 주소가 저장된 것을 볼 수 있다. 이런 의미에서 배열은 근본적으로 포인터이다.

하지만 저게 배열의 시작 주소인지는 아직 알 수 없다.

지난 글에서 말했듯이 주소만 있다면 역참조 연산자 *를 통해 그 주소에 저장된 값(데이터)을 읽어올 수 있다.

역참조 연산자를 이용해서 배열이름이 정말 배열의 첫 번째 원소가 저장되어 있는 메모리 주소가 맞는지 확인해보자.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	cout << *arr << endl;
	return 0;
}

또 다른 방법으로도 확인할 수 있다.

주소를 확인하는 방법은 &연산자를 쓰면 된다. &arr[0]과 arr이 같은지 확인해보자.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	cout << "배열의 첫 번재 원소의 주소: " << &arr[0] << endl;
	cout << "배열 이름 arr:              " << arr << endl;
	return 0;
}

이제 배열의 이름 arr이 배열의 시작주소 즉, 배열의 첫 번째 원소인 1이 저장되어 있는 메모리 주소라는 것을 직접 확인해보았다.

배열의 시작 주소를 이용해서 배열의 원소에 접근하는 방법을 알아보자.

배열의 0번째 인덱스에 저장된 원소에 접근하려면 *(arr + 0), 배열의 1번 인덱스에 저장된 원소에 접근하려면 *(arr + 1), 2번 인덱스는 *(arr + 2), 3번 인덱스는 *(arr + 3) 이렇게 접근하면 된다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	cout << *(arr + 0) << endl;
	cout << *(arr + 1) << endl;
	cout << *(arr + 2) << endl;
	cout << *(arr + 3) << endl;
	cout << *(arr + 4) << endl;
	return 0;
}

즉 arr[3]과 *(arr + 3)은 같은 말이다.

arr에서 3 x 4(arr은 int 배열이므로 원소 하나는 4바이트)바이트만큼 떨어진 곳의 메모리주소에 저장된 내용을 읽어오라(역참조 연산자)는 것이다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	cout << arr[0] << " " << *(arr + 0) << endl;
	cout << arr[1] << " " << *(arr + 1) << endl;
	cout << arr[2] << " " << *(arr + 2) << endl;
	cout << arr[3] << " " << *(arr + 3) << endl;
	cout << arr[4] << " " << *(arr + 4) << endl;
	return 0;
}

arr[i]와 *(arr + i)는 똑같은 표현이라는 것을 알 수 있다.

그리고 &arr[i]와 arr + i도 똑같은 표현이다. arr[i]가 저장된 메모리 주소를 나타낸다.

정리하자면 배열의 첫 번째 주소는 '배열의 이름'으로 항상 노출되어 있고 나머지 원소는 첫 번째 원소의 주소 + offset 이런 방식으로 접근하는 것이다.

그러면

int* list = arr;

이렇게 해버리면 어떻게 될까?

list[1] 이런 식으로 list 포인터를 통해 arr과 똑같이 배열의 원소에 접근할 수 있게 된다.

다음 코드를 실행해보자.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	int* list = arr;
	for (int i = 0; i < 5; i++) {
		cout << "주소: " << list + i << " *(list + " << i << "): " << *(list + i) << " list[" << i << "]: " << list[i] << " *(arr + " << i << "): " << *(arr + i) << " arr[" << i << "]: " << arr[i] << endl;
	}
	return 0;
}

*(list + i), *(arr + i), list[i], arr[i] 이렇게 4개가 모두 똑같은 값을 출력하는 것을 볼 수 있다.

그리고 int 타입의 배열이기 때문에 주소는 4바이트씩 차이나는 것도 볼 수 있다. arr과 list은 거의 똑같다고 보면 된다.

굳이 차이점을 꼽자면 arr은 arr 자체가 005CFC34인거고 list는 4바이트 메모리 공간이 있고 그 공간에 005CFC34가 저장되어 있는 포인터 변수이다.

여기에서 주의해야 할 점은 arr나 list는 배열 전체를 가리키는 것이 아니다.

list는 arr이라는 배열의 첫 번째 원소를 가리키는 포인터 변수이다. arr의 시작 주소를 복사해서 list라는 포인터 변수에 그 주소를 저장한 것이다.

배열의 시작 주소(첫 번째 원소의 주소)는 가지고 있기 때문에 그 주소를 기준으로 얼마만큼 떨어져 있는 메모리에 접근하는 것이다. 그렇게 때문에 시작 주소 하나만 가지고 있어도 배열의 모든 원소에 접근이 가능하다.

따라서

cout << list[7];

이렇게 인덱스를 벗어나서 접근을 해도 아무런 오류가 나지 않는다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	int* list = arr;
	cout << list[7] << endl; //배열 인덱스를 벗어남
	return 0;
}

배열의 인덱스를 벗어나도 컴파일 에러, 실행 오류 모두 나지 않고 그 메모리에 저장되어 있던 아무 의미 없는 쓰레기값을 출력한다. 아니면 다른 프로그램에서 쓰고 있는 데이터를 마음대로 접근해서 출력한 것이다.

지금은 출력만 했으니 망정이지

list[7] = 0;

이렇게 그 메모리에 저장된 값을 마음대로 변경해버리면 정말 심각한 상황이 발생할 수도 있다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	int* list = arr;
	list[7] = 0; //이 주소에 저장된 값을 마음대로 바꿈
	cout << list[7] << endl;
	return 0;
}

이렇게 심각한 짓을 저질러도 아무런 오류 없이 이렇게

0을 출력한다.

아무튼 배열의 시작주소를 가리키는 포인터는 배열 전체를 가리키는 게 아니라는 것을 꼭 기억해야 한다.

번외로 배열과 포인터에서 정말 흥미로운 것을 발견할 수 있다.

덧셈은 교환법칙이 성립한다.

따라서 arr + i와 i + a는 똑같고 *(arr + i)나 *(i + a)는 똑같다

즉, arr[i]와 i[arr]은 똑같다.

#include <iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	cout << "arr[2]: " << arr[2] << endl;
	cout << "2[arr]: " << 2[arr] << endl;
	return 0;
}

2[arr]과 같은 요상한 코드를 실행해도 컴파일러는 컴파일할 때 *(2 + arr)로 하기 때문에 아무런 문제가 없는 것이다.

또 다른 흥미로운 것이 있다.

배열을 함수의 인자로 넘길 때 우리는

함수이름(배열이름, 배열의 크기);

이렇게 호출한다.

예를 들어 크기가 5인 int형 배열 arr을 함수 print의 인자로 넘겨주려면

print(arr, 5);

이렇게 호출하면 된다.

그러면 받는 쪽에서는

void print(int arr[], int size) {
	for(int i = 0; i < size; i++) {
    	cout << arr[i] << endl;
    }
}

int arr[] 이렇게 받는다. 여기에서 받은 arr[]은 배열 arr의 시작주소이다. 인자로 넘겨줄 때 arr을 인자로 준다는 것은 배열의 주소를 넘겨준 것이다.

그런데 주소는 포인터이기 때문에 함수를 정의할 때

void print(int* arr, int size) {
	for(int i = 0; i < size; i++) {
    	cout << arr[i] << endl;
    }
}

int arr* 이렇게 포인터로 받아도 된다.

int arr[]로 받으나 포인터인 int arr*로 받으나 함수 내용을 바꾸지 않아도 멀쩡히 잘 동작한다.

함수의 인자로 배열을 넘겨줄 때에는 복사본이 넘어가는 것이 아니라 원본이 넘어간다는 말을 많이 들었을 것이다. (일반적인 변수는 복사본이 넘어간다. call by value)

배열은 함수로 넘길 때 원본이 넘어간다는 것은 다음 코드의 실행결과를 보면 알 수 있다.

#include <iostream>
using namespace std;

void changeArray(int* arr, int size) {
	arr[2] = 10;
}

int main() {
	int arr[5] = { 1,2,3,4,5 };
	changeArray(arr, 5);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << endl;
	}
	return 0;
}

함수를 호출한 뒤에 배열 arr의 원소를 출력해봤더니 arr[2]가 10으로 변경된 것을 알 수 있다.

즉 배열은 원본이 넘어간다. (배열 전체를 매개변수로 넘기면 너무 용량이 커서 메모리를 너무 많이 차지하기 때문에 이렇게 한 것이다.)

그냥 일반 변수의 경우

#include <iostream>
using namespace std;

void changeA(int aa) {
	aa = 10;
}

int main() {
	int a = 5;
	changeA(a);
	cout << a << endl;
	return 0;
}

함수를 호출한 후에도 a는 변경되지 않는다.

changeA 함수가 호출되면 그 인자로 들어온 a의 값 5를 매개변수 aa에 복사하는 것이다. aa = 5; 이렇게.

그다음 그 aa를 10으로 바꾸는 것이다. 그러니까 당연히 원본 a는 변하지 않는다.

아무튼 배열은 일반 변수와 달리 복사본이 아닌 원본이 넘어간다고 알고 있을 텐데 이것은 엄밀히 말하면 정확하지 않다.

함수를 호출할 때에는 배열의 이름 즉 배열의 시작 주소를 넘기고

호출된 함수에서는 매개변수로 그 배열의 주소를 받는데 그 주소의 복사본이 넘어가는 것이다.

아까 그 일반 변수 a가 넘어간 것과 같이 배열의 주소가 하나의 변수로 넘어간 것이다.

그리고 나서 함수 내부에서는 그 주소를 통해 배열에 접근하는 것이다. 따라서 배열의 원본이 넘어간 것과 같은 효과를 하지만 사실은 배열의 원본이 넘어간 것이 아니라 배열의 주소가 복사본으로 넘어간 것이다.

프로그래밍 기초를 배울 때에는 포인터도 아직 안 배운 학생에게 이런 얘기까지 하면 너무 어렵기 때문에 일단은 그냥 배열은 원본이 넘어간다고 설명하는 것 같다.

그리고 배열에서 포인터를 썼을 때의 장점이 또 있다. 함수의 리턴 값으로 배열을 반환할 수는 없다. 하지만 포인터 즉 주소를 함수의 반환값으로 반환할 수는 있다.

이것에 대한 포스팅은 다음 포스팅에 이어가겠습니다. (링크 ↓)

https://breakcoding.tistory.com/310

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

그냥 LIS(Longest Increasing Sequence)를 구하면 된다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> boxes(n);
	for (int i = 0; i < n; i++) {
		cin >> boxes[i];
	}
	int maxBox = 0;
	vector<int> dp(n);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		int maxDp = 0;
		for (int j = 0; j < i; j++) {
			if (dp[j] > maxDp && boxes[j] < boxes[i]) {
				maxDp = dp[j];
			}
		}
		dp[i] = maxDp + 1;
		if (dp[i] > maxBox)
			maxBox = dp[i];
	}
	cout << maxBox;
	return 0;
}