소프트웨어 개발이야기

from teddy8

[BaekJoon][Greedy] 1080. 행렬

2019-07-04

teddy8

Algorithm

BaekJoon 백준 C C++ Greedy 그리디 Algorithm 알고리즘

문제
문제 설명
소스코드

문제

URL : https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

문제 설명

/* 문제 : [1080] 행렬
[input]
3 4
0000
0010
0000
1001
1011
1001
[output]
2
[설명]
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 
연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 
둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
*/

소스코드

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

using namespace std;

void changeArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2, int x, int y);
bool CompareTwoArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2);
void inputArray(vector<vector<int>> &arr);	// 2차원 배열에 데이터 입력
void outputArray(vector<vector<int>> &arr);

int main()
{
	int n, m;	// 행렬의 크기 n, m
	int count = 0; // 연산횟수 누적
	bool isEqual = false;
	cin >> n >> m;
	vector<vector<int>> arr1(n, vector<int>(m, 0));
	vector<vector<int>> arr2(n, vector<int>(m, 0));
	inputArray(arr1);
	inputArray(arr2);

	for (int i = 0; i <= (n - 3) && !isEqual; i++) {
		for (int k = 0; k <= (m - 3) && !isEqual; k++) {
			if (arr1[i][k] == arr2[i][k]) // 바꿀 필요 없으면 패스
				continue;

			changeArray(arr1, arr2, i, k);
			count++;
			isEqual = CompareTwoArray(arr1, arr2);
		}
	}

	if (CompareTwoArray(arr1, arr2) == true)
		cout << count;
	else
		cout << "-1";

	return 0;
}

bool CompareTwoArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2) {
	for (int i = 0, n; i < arr1.size(); i++) {
		for (int k = 0; k < arr1[i].size(); k++) {
			if (arr1[i][k] != arr2[i][k])
				return false;
		}
	}
	return true;
}

void changeArray(vector<vector<int>> &arr1, vector<vector<int>> &arr2, int x, int y) {
	for (int i = x; i < (x + 3); i++) { // 3x3범위의 모든 원소 반전 (1->0, 0->1)
		for (int k = y; k < (y + 3); k++) {
			arr1[i][k] = (1 - arr1[i][k]);
		}
	}
}

void inputArray(vector<vector<int>> &arr) {
	string s;
	for (int i = 0, n; i < arr.size(); i++) {
		cin >> s;
		for (int k = 0; k < arr[i].size(); k++) {
			arr[i][k] = s[k] - '0';
		}
	}
}

void outputArray(vector<vector<int>> &arr) { // 디버깅용
	for (int i = 0, n; i < arr.size(); i++) {
		for (int k = 0; k < arr[i].size(); k++) {
			cout << arr[i][k];
		}
		cout << endl;
	}
}

Read All

[BaekJoon][Greedy] 1049. 기타줄

2019-07-04

teddy8

Algorithm

BaekJoon 백준 C C++ Greedy 그리디 Algorithm 알고리즘

문제
문제 설명
소스코드

문제

URL : https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

문제 설명

/* 문제 : [1049] 기타줄
[input]
4 2
12 3
15 4
[output]
12
[설명]
Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 
따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 
6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.
끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 
각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 
적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.
첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 
둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 
가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
*/

소스코드

#include <iostream>

using namespace std;

int main()
{
	int min_packagePrice = 1234567890;	// 가장 저렴한 패키지 가격
	int min_price = 1234567890;		// 가장 저렴한 낱개 가격
	int n, m;				// 끊어진 기타줄의 개수, 기타줄 브랜드 개수
	int money;				// 필요한 돈

	cin >> n >> m;

	for (int i = 0, k, s; i < m; i++) {
		cin >> k >> s;
		if (min_packagePrice > k) 
			min_packagePrice = k;
		if (min_price > s) 
			min_price = s;
	}			

	if (min_packagePrice < (min_price * 6)) { // 패키지가 더 합리적이면
		money = (n / 6) * min_packagePrice;
		if (((n % 6) * min_price) < min_packagePrice) // 6개미만인데도 패키지가 더 합리적이면	
			money += (n % 6) * min_price;
		else
			money += min_packagePrice;
	}
	else  // 낱개가 더 저렴하거나 같으면 
		money = min_price * n;

	cout << money;
	return 0;
}

Read All

[BaekJoon][Greedy] 1946. 신입사원

2019-07-03

teddy8

Algorithm

BaekJoon 백준 C C++ Greedy 그리디 Algorithm 알고리즘

문제
문제설명
Solution
소스코드

문제

URL : https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

문제설명

/* 문제 : [1946] 신입사원
[input]
2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1
[output]
4
3
[설명]
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 
인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 
최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 
적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 
즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 
서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 
신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
*/

Solution

— —

소스코드

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

int main()
{
	map<int, int> rankingMap;	// 서류순위를 기준으로 오름차순하기 위해 map 사용
	int descCheckNum;
	int n;
	int testCase;

	cin >> testCase;
	vector<int> result(testCase, 0);

	for (int i = 0; i < testCase; i++) {
		cin >> n;

		for (int i = 0, k, s; i < n; i++) {
			cin >> k >> s;
			rankingMap[k] = s;
		}

		descCheckNum = rankingMap.begin()->second;	// 서류순위 1위의 면접순위를 할당
		int count = 1;

		// map의 begin(서류순위 1위)부터 iter->second == 1(면접순위 1위)까지 순회
		for (map<int, int>::iterator iter = rankingMap.begin(); iter->second != 1; iter++) {
			if (descCheckNum >= iter->second) {
				descCheckNum = iter->second;
				count++;
			}
		}

		result[i] = count;
		rankingMap.clear();
	}

	// 결과 출력
	for (vector<int>::size_type i = 0; i < result.size(); i++) {
		cout << result[i] << endl;
	}

	return 0;
}

Read All

JavaScript 모듈시스템

2019-07-02

teddy8

JavaScript

JavaScript js module system
- 모듈 시스템
- 출력값
모듈 시스템

ES6에 추가된 모듈시스템에 대해서 살펴보겠습니다.
자바스크립트 파일을 export 키워드를 통해 내보낸 후,
import 키워드를 통해 쉽게 가져올 수 있습니다.
아래의 간단한 예제로 살펴보겠습니다.

index.html —
```
<!DOCTYPE html>
<html lang="ko">
<head>
  <meta charset="UTF-8">
  <title>Module Sample</title>
  <script type="module" src="app.js"></script>
</head>
<body>
</body>
</html>
```
app.js —
```
import { sum } from './test.js';
sum(2, 3);
```
test.js —
```
export function sum(a, b) {
  console.log(`${a} + ${b} = ${a+b}`);
}
```
출력값
```
2 + 3 = 5
```
Read All

[BaekJoon][Greedy] 1120. 문자열

2019-07-01

teddy8

Algorithm

BaekJoon 백준 C C++ Greedy 그리디 Algorithm 알고리즘

문제
소스코드

문제

URL : https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

소스코드

/* 문제 : [1120] 문자열
[input]
adaabc aababbc
[output]
2
[설명]
길이가 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[0], B[0]가 다르면 차이는 1
A는 B보다 작거나 같기 때문에 앞이나 뒤에 알파벳을 추가함으로 써 A와 B의 차이를 최소로 할 수 있다
*/
#include <iostream>
#include <string>
using namespace std;

int main()
{
	string s1, s2;
	int count;
	int min = 1234567890;

	cin >> s1 >> s2;

	for (int i = 0; i <= (s2.length() - s1.length()); i++) {
		count = 0;
		for (int k = 0; k < s1.length(); k++) {
			if (s1[k] != s2[k + i])
				count++;
		}
		if (count < min)
			min = count;
	}

	cout << min;
	return 0;
}

Read All

[BaekJoon][Greedy] 1120. 문자열

2019-07-01

teddy8

Algorithm

BaekJoon 백준 C C++ Greedy 그리디 Algorithm 알고리즘

문제
소스코드

문제

URL : https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

소스코드

/* 문제 : [1120] 문자열
[input]
adaabc aababbc
[output]
2
[설명]
길이가 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[0], B[0]가 다르면 차이는 1
A는 B보다 작거나 같기 때문에 앞이나 뒤에 알파벳을 추가함으로 써 A와 B의 차이를 최소로 할 수 있다
*/
#include <iostream>
#include <string>
using namespace std;

int main()
{
	string s1, s2;
	int count;
	int min = 1234567890;

	cin >> s1 >> s2;

	for (int i = 0; i <= (s2.length() - s1.length()); i++) {
		count = 0;
		for (int k = 0; k < s1.length(); k++) {
			if (s1[k] != s2[k + i])
				count++;
		}
		if (count < min)
			min = count;
	}

	cout << min;
	return 0;
}

Read All

10/28

소프트웨어 개발이야기

[BaekJoon][Greedy] 1080. 행렬

문제

문제 설명

소스코드

[BaekJoon][Greedy] 1049. 기타줄

문제

문제 설명

소스코드

[BaekJoon][Greedy] 1946. 신입사원

문제

문제설명

Solution

소스코드

JavaScript 모듈시스템

모듈 시스템

출력값

[BaekJoon][Greedy] 1120. 문자열

문제

소스코드

[BaekJoon][Greedy] 1120. 문자열

문제

소스코드