Feel Coding

매번 이렇게 내가 정렬 기준을 새로 정해서 정렬하는 문제는 항상 자바로 풀었어서 이번에는 새로 정렬하는 법을 공부하고 C++로 풀어봤다.

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

bool cmp(tuple<int, string, int>& p1, tuple<int, string, int>& p2) {
	if (get<0>(p1) == get<0>(p2)) {
		return (get<2>(p1) < get<2>(p2));
	}
	else return (get<0>(p1) < get<0>(p2));
}
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	tuple<int, string, int>* arr = new tuple<int, string, int>[n];
	for (int i = 0; i < n; i++) {
		cin >> get<0>(arr[i]);
		cin >> get<1>(arr[i]);
		get<2>(arr[i]) = i;
	}
	sort(arr, arr + n, cmp);
	for (int i = 0; i < n; i++) {
		cout << get<0>(arr[i]) << " " << get<1>(arr[i]) << "\n";
	}
	return 0;
}

자연수 n이 주어졌을 때 n이 소수인지 아닌지 알아보려면 어떻게 해야 할까?

2부터 n-1까지 n을 나눠보면 된다.

하지만 다시 잘 생각해보면 굳이 n-1까지 가지 않아도 알 수 있다.

n / 2까지만 나눠보면 소수인지 아닌지 판별이 가능하다.

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

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (numbers[i] == 1) {
		}
		else if (numbers[i] == 2) {
			count++;
		}
		else {
			bool flag = false;
			for (int j = 2; j <= numbers[i] / 2; j++) {
				if (numbers[i] % j == 0) {
					flag = true;
					break;
				}
			}
			if (!flag) count++;
		}
	}
	cout << count;
	return 0;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	vector<int> v;
	for (int i = 1; i < 10000; i++) {
		if (i < 10) {
			v.push_back(i + i);
		}
		else if (i < 100) {
			v.push_back(i + i / 10 + i % 10);
		}
		else if (i < 1000) {
			v.push_back(i + i / 100 + i / 10 % 10 + i % 10);
		}
		else {
			v.push_back(i + i / 1000 + i / 100 % 10 + i / 10 % 10 + i % 10);
		}
	}
	for (int i = 1; i <= 10000; i++) {
		bool flag = false;
		for (int j = 0; j < v.size(); j++) {
			if (v[j] == i) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << i << endl;
		}
	}
	return 0;
}

LIS 문제에서 부등호 하나만 반대 부등호로 바꿔주면 된다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int* lds = new int[n];
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int longestLength = 0;
		for (int j = 0; j < i; j++) {
			if (numbers[i] < numbers[j]) {
				if (lds[j] > longestLength)
					longestLength = lds[j];
			}
		}
		lds[i] = longestLength + 1;
		if (lds[i] > maxLength)
			maxLength = lds[i];
	}
	cout << maxLength;
	return 0;
}

11053번 문제와 정확하게 일치하는 LIS(Longest Increasing Subsequence) 문제이다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* card = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}
	int* lis = new int[n];
	lis[0] = 0;
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int longestLengthBeforeI = 0;
		for (int j = 0; j < i; j++) {
			if (card[i] > card[j]) {
				if (lis[j] > longestLengthBeforeI)
					longestLengthBeforeI = lis[j];
			}
		}
		lis[i] = longestLengthBeforeI + 1;
		if (lis[i] > maxLength)
			maxLength = lis[i];
	}
	cout << maxLength << endl;
	return 0;
}

입력이 N (1 ≤ N ≤ 15)라길래 브루트포스로 풀었다.

조합은 시간 복잡도가 계승(팩토리얼)함수이기  때문에 n이 20 정도만 돼도 답을 구하기가 힘들다.

따라서 입력이 1 ≤ N ≤ 15 이라는 것을 보고 힌트를 얻었다. 마음놓고 조합으로 풀어도 된다는 것이구나.

조합(Combination)으로 N개 중 1개를 고르는 경우부터 N개를 고르는 경우까지 모든 경우를 다 구하고

그러고 나서 나중에 조건을 체크했다.

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

int** arr;
int n;
vector<int> profit;

void select(vector<bool> visited, vector<tuple<int, int, int>> result, int theNumberOfSelect, int num) {

	if (num == theNumberOfSelect) {

		int total = 0;
		if (get<2>(result[0]) + get<0>(result[0]) > n) {
			return;
		}
		for (int i = 1; i < theNumberOfSelect; i++) {
			if (get<2>(result[i]) + get<0>(result[i]) > n) {
				return;
			}
			if (get<2>(result[i - 1]) + get<0>(result[i - 1]) > get<2>(result[i])) {
				return;
			}
		}
		for (int i = 0; i < theNumberOfSelect; i++) {
			total += get<1>(result[i]);
		}

		profit.push_back(total);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num != 0) {
			if (get<2>(result[num - 1]) < i) {
				if (!visited[i]) {
					visited[i] = true;
					result[num] = make_tuple(arr[i][0], arr[i][1], i); //걸리는 기간, 받는 금액, 시작 날짜
					select(visited, result, theNumberOfSelect, num + 1);
					visited[i] = false;
				}
			}
		}
		else {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = make_tuple(arr[i][0], arr[i][1], i); //걸리는 기간, 받는 금액, 시작 날짜
				select(visited, result, theNumberOfSelect, num + 1);
				visited[i] = false;
			}
		}
	}
}

int main() {
	cin >> n;
	arr = new int*[n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	for (int i = 0; i < n; i++) {
		vector<tuple<int, int, int>> result(i + 1);
		vector<bool> visited(n);
		for (int j = 0; j < n; j++) {
			visited[i] = false;
		}
		select(visited, result, i + 1, 0);
	}
	int maxProfit = 0;
	for (int i = 0; i < profit.size(); i++) {
		if (profit[i] > maxProfit) maxProfit = profit[i];
	}
	cout << maxProfit;
	return 0;
}

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int originalNumber = n;
	int count = 0;
	do {
		int a = n % 10;
		int b = (n / 10 + n % 10) % 10;
		n = a * 10 + b;
		count++;
	} while (n != originalNumber);
	cout << count;
	return 0;
}

단계별로 풀어보기 동적 계획법 1의 11단계 문제

LIS(Longest Increasing Subsequence) 문제이다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	int* dp = new int[n]; //i까지의 최장 증가하는 수열의 길이를 저장하는 배열
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		int maxBeforeI = 0; //i 전까지 최장 증가하는 수열의 길이를 저장할 변수
		for (int j = 0; j < i; j++) { //i 전까지
			if (numbers[i] > numbers[j]) { //'증가하는' 조건을 만족하면서
				if (dp[j] > maxBeforeI) //더 긴 수열이 발견되면
					maxBeforeI = dp[j]; //업데이트
			}
		}
		dp[i] = maxBeforeI + 1; // i 전까지를 구했으니까 나 자신 i를 더해줘야 한다.
	}
	int maxDp = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] > maxDp)
			maxDp = dp[i];
	}
	cout << maxDp << endl;
	return 0;
}

동적 계획법의 특징 답게 특별한 계산 없이 해를 구할 수 있다.

나보다 작으면서 나보다 이전에 있는 LIS에 1만 더해주면 된다.

#include <iostream>
using namespace std;

void select(int numbers[], int result[], bool visited[], int n, int num) {
	if (num == 6) {
		for (int i = 0; i < 6; i++) {
			cout << result[i] << " ";
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num != 0) {
			if (!visited[i] && numbers[i] > result[num - 1]) {
				visited[i] = true;
				result[num] = numbers[i];
				select(numbers, result, visited, n, num + 1);
				visited[i] = false;
			}
		}
		else {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = numbers[i];
				select(numbers, result, visited, n, num + 1);
				visited[i] = false;
			}
		}
	}
}

int main() {
	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		int* numbers = new int[n];
		for (int i = 0; i < n; i++) {
			cin >> numbers[i];
		}
		int* result = new int[n];
		bool* visited = new bool[n];
		for (int i = 0; i < n; i++) {
			visited[i] = false;
		}
		select(numbers, result, visited, n, 0);
		cout << endl;
	}
	return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<String> list = new ArrayList<>();
        Set<String> set = new HashSet<>();
        for(int i = 0; i < n; i++) {
            set.add(in.next());
        }
        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()) {
            list.add(iterator.next());
        }
        list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length() != o2.length())
                    return o1.length() - o2.length();
                else
                    return o1.compareTo(o2);
            }
        });
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

HashSet을 List로 바꿀 수 있는 방법을 다시 공부해야겠다. 컬렉션 배웠던거 다시 복습해야지