chaetudy

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

아이디어

N명 중 N/2명으로 이루어진 두 팀을 어떻게 짤 것인가.

1) 재귀 (백트래킹)

2) 순열

3) 비트마스킹

방법이 있는데, 문제 출제 의도에 맞게 1번으로 문제를 풀 것이다.

코드

// BOJ 14889: 스타트와 링크
// n명 중 n/2명씩 각각 스타트팀, 링크팀으로 나눈다.
// Sij는 i번 사람과 j번 사람이 같은 팀일 때 능력치
// i번, j번이 같은 팀에 속하면 팀에 더해지는 능력치는 Sij와 Sji

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

int n;
int stats[21][21];
bool visited[21];
int result = 1e9;

// idx번 선수를 start 팀으로 뽑고, cnt는 뽑은 명수
void dfs(int idx, int cnt) {

	if (cnt == n / 2) {
		vector<int> link, start;
		for (int i = 0; i < n; i++) {
			if (visited[i] == true) // 뽑은 선수들은 스타트팀으로
				start.push_back(i);
			else
				link.push_back(i);
		}

		// 팀 간의 능력치 차
		int s_sum = 0, l_sum = 0;
		for (int i = 0; i < start.size(); i++) {
			for (int j = i + 1; j < start.size(); j++) {
				s_sum += stats[start[i]][start[j]] + stats[start[j]][start[i]];
				l_sum += stats[link[i]][link[j]] + stats[link[j]][link[i]];
			}
		}

		result = min(result, abs(s_sum - l_sum));
		return;
	}

	for (int i = idx + 1; i < n; i++) {
		if (visited[i] == false) {
			visited[i] = true;
			dfs(i, cnt + 1); // 백트래킹
			visited[i] = false;
		}
	}

}


int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> stats[i][j];
		}
	}
	dfs(0, 0);

	cout << result << "\n";
}

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

아이디어

정수 N이 있다면, 2~N-1까지의 수를 N에 나누고, 그 나머지가 0인 수가 하나라도 있다면 소수가 아닌 걸로 판별한다.

코드

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

bool isDec(int num) {
	bool result = true;
	if (num == 1) return false;
	for (int i = 2; i < num; i++) {
		if (num % i == 0) return false;
	}
	return result;
}

int main()
{
	int N;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	int cnt = 0;
	for (const int& i : v) {
		if (isDec(i)) {
			cnt++;
		}
	}
	cout << cnt << "\n";
}

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

아이디어

가장 작은 원소와 가장 큰 원소를 곱하면 N을 구할 수 있다.

구현 방법에 대한 고민

priority_queue와 vector

먼저 min과 max를 구해야 했다. 처음에는 vector 컨테이너에 담아서 sorting을 해서 첫 번째 원소와 마지막 원소를 읽어 오는 방법이 떠올라 코드를 작성하고 있었는데, 문득 "sorting할 필요가 없는 컨테이너를 사용하면 더 효율적이지 않을까?" 라는 생각이 들어 priority_queue를 사용하게 되었다.

그런데 제출 결과 두 방식의 메모리, 시간 차이는 없음을 알 수 있었다. ㅎㅎ

priority_queue 사용

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

int main()
{
	cin.tie(0);

	int div_cnt = 0;
	cin >> div_cnt;
	
	priority_queue<int, vector<int>> pq;
	priority_queue<int, vector<int>, std::greater<int>> pq_greater;

	for (int i = 0; i < div_cnt; i++) {
		int key;
		cin >> key;
		pq.push(key);
		pq_greater.push(key);
	}
	int min = pq.top();
	int max = pq_greater.top();

	int result = min * max;
	cout << result << "\n";
}

vector 사용

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

int main()
{
	cin.tie(0);

	int div_cnt = 0;
	cin >> div_cnt;
	
	vector<int> v(div_cnt);

	for (int i = 0; i < div_cnt; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int min = v[0];
	int max = v[div_cnt - 1];

	int result = min * max;
	cout << result << "\n";
}

개요

분할 정복 방법을 통해 리스트를 정렬한다.

피봇을 정한 뒤 피봇의 위치를 확정해 가며 정렬한다.

시간 복잡도

최악의 경우 O(n^2), 평균적으로 O(nlogn)이다.

대부분 컴퓨터 아키텍쳐 설계 상 퀵 소트 내부 루프의 캐시 히트율이 높기 때문에, 일반적인 경우에 시간 복잡도 O(nlogn)인 알고리즘보다 빠르다.

코드

void quick_sort(int* arr, int low, int high) {
	// base condition
	if (low >= high) return;

	// divide
	int i = low, j = low;
	int& pivot = arr[high];
	for (;  j < high; j++) {
		if (arr[j] < pivot) {
			swap(arr[i++], arr[j]);
		}
	}
	swap(arr[i], pivot);

	// conquer
	quick_sort(arr, low, i - 1);
	quick_sort(arr, i + 1, high);
}

ref

공부하면서 많이 도움이 되었던 영상

https://youtu.be/cWH49IKDIiI

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

개요

두 인접한 원소를 정렬해 나간다.

구현은 쉬우나 효율은 좋지 않은 편에 속한다. 대충 이런 정렬이 있구나 하고 알고 넘어가면 된다.

55 07 78 12 42  초기값[파란색은 sorting]
07 55 78 12 42  첫 번째 패스(pass)
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  두 번째 패스(pass)
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  세 번째 패스(pass)
07 12 42 55 78  네 번째 패스(pass)
07 12 42 55 78  다섯 번째 패스(pass)
07 12 42 55 78  정렬 끝

시간 복잡도

n-1, n-2, ... 1번을 반복하게 되며 이를 식으로 나타내면 n(n-1)/2이므로, O(n^2)이다.

코드

void bubble_sort(int* p, int size) { 
	for (int i = 0; i < size - 1; i++) { 
		for (int j = 0; j < size - i - 1; j++) { 
			if (p[j] > p[j + 1]) { 
				swap(p[j], p[j + 1]); 
			}
		}
	}
}

ref

https://todaycode.tistory.com/46

(5/19) - X

https://school.programmers.co.kr/learn/courses/30/lessons/42746

아이디어가 도저히 안 떠올라서 그냥 답 보고 풀었다. 나중에 다시 풀어 봐야겠다.

나는 numbers의 원소들을 정수로 변환해서, 정수 자체를 어떻게 비교해야 할까만 생각했다.

다른 사람들 아이디어는 간단하고 똑똑했다! string 자체를 비교하면 되는 거였다.

코드

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

using namespace std;

bool compare(const string& a, const string& b) {
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";

    vector<string> v;
    for (const int& i : numbers) {
        v.emplace_back(to_string(i));
    }

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

    for (const string& s : v) {
        answer += s;
    }

    if (answer[0] == '0')
        return "0";
    return answer;
}

(5/19) - O

구현

priority_queue를 이용해서 풀었다. 특징이랑 내장 함수는 잘 모르는데, 원소들을 우선순위로 계속 정렬해 간다는 것만 알아서 선택했다. 근데 왜 int 하나로 독자적으로 만들어지지 않고 두 번째 타입으로 vector<int>를 넣어 줘야 컴파일 되는 걸까?.. key-value 쌍을 원소로 취하는 자료구조인가?....ㅎㅎ 긴가민가하면서 풀었다

priority_queue에 스코빌 지수들을 담는다. 내림차순이 default이므로 greater로 지정해 준다.

맨 앞의 두 원소가 가장 안 매운 스코빌 지수, 그리고 두 번째로 안 매운 스코빌 지수이기 때문에, top() 저장-pop()을 두 번 해 주면 된다. 이 둘을 섞어 준다.

섞은 스코빌 지수를 다시 priority_queue에 담는다.

맨 앞의 원소가 목표 스코빌 지수 K보다 크다면 그 다음 이어질 원소들도 K보다 클 것이다. 섞기를 중지하고 섞은 횟수를 return 한다.

Priority_queue

https://chae-d-2.tistory.com/156

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;

    priority_queue<int, vector<int>, greater<int>> pq;
    for (const int& i : scoville) {
        pq.push(i);
    }

    int mix_cnt = 0;

    while (true) {
        int des = pq.top();
        pq.pop();
        int src = pq.top();
        pq.pop();
        int mix_result = des + (src * 2);
        pq.push(mix_result);
        mix_cnt++;

        if (pq.top() >= K) {
            answer = mix_cnt;
            break;
        }
        if (pq.size() == 1 && pq.top() < K) {
            answer = -1;
            break;
        }
    }
    return answer;
}

(5/19 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/42586

구현

Queue를 이용하여 풀이.

queue는 이터레이터가 없으므로 순회 X, 정 탐색하고 싶다면 Deque를 사용할 것.

Queue

https://chae-d-2.tistory.com/153?category=1098972 

코드

// 각 배포마다 몇 개의 기능이 배포되는가
// 배포는 하루에 한 번만, 하루의 끝에 이루어짐
// 예를 들어 진도율 95%이고 속도가 하루에 4인 작업은 배포가 2일 뒤에 이루어짐

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int sz = progresses.size();
    queue<pair<int, int>> q;
    for (int i = 0; i < sz; i++) {
        q.push({ progresses[i], speeds[i] });
    }

    int day_cnt = 0;
    int out = 0;
    while (!q.empty()) {
		day_cnt++;
		int jindo = q.front().first + (q.front().second * day_cnt);
		if (jindo >= 100) {
			q.pop();
            out++;
			while (!q.empty()) {
				jindo = q.front().first + (q.front().second * day_cnt);
				if (jindo >= 100) {
					q.pop();
					out++;
				}
				else {
					break;
				}
			}
            answer.push_back(out);
            out = 0;
		}

	}


    return answer;
}

int main()
{
    vector<int> p = { 95, 90, 99, 99, 80, 99 };
    vector<int> s = { 1, 1, 1, 1, 1, 1};
    solution(p, s);
}