코딩뚠뚠

풀이일시 : 2020-10-16 ​ 문제 : 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지..

풀이일시 : 2020-10-16 ​ 문제 : 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. ​ ​ 입력 : 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진..

#include #include #include using namespace std; int n; vector v; int getSum(string a) { int n = a.length(); int sum = 0; for (int i = 0; i < n; i++) { if (a[i] - '0' = 0) { //string 중 숫자만 구분해서 더한다. sum += a[i] - '0'; } } return sum; } bool compare(string a, string b) { if (a.length() != b.length()) //첫번째 고려사항 길이가 짧은것이 먼저온다. return a.length() < b.length(); else { //두번째 고려사항 길이가 같다면 합이 작은게 먼저온다. i..

풀이일시 : 2020-07-30 ​ 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ​ 입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. ex) 5 5 4 3 2 1 ​ 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. ex) 1 2 3 4 5 ​ 풀이 : 수의 개수가 100만 이하라는 것에 주목하자. -> O(N^2) 의 시간복잡도를 가지는 정렬 알고리즘을 사용하게되면 100만 * 100만 = 1조 까지 나올 수 있다. 하지만 시간제한이 1초이기 때문에 대략 이정도의 시..

풀이 일시 : 2020-07-30 ​ 문제 : 동규는 세수를 하다가 정렬이 하고싶어졌다. 숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다. 숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오. ​ 입력 : 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. ex) 3 1 2 ​ 출력 : 제일 작은 수, 그 다음 수, 제일 큰 수를 차례대로 출력한다. ex) 1 2 3 ​ 풀이 : 입력을 받은 뒤 알고있는 sort 알고리즘으로 sort 하여 print 한다. 크기가 3으로 정해져있기때문에 a[3]을 잡아놓고 시작한다. #include int main() { int a[3]..

풀이 일시 : 2020-08-16 ​ 위상정렬 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때 순서를 결정하기 위해 큐 사용 ​ 문제 : topology sort 수행 ​ 시간복잡도 : O(V+E) ​ 풀이 : #include #include #include #define MAX 10 using namespace std; int n, inDegree[MAX]; vector a[MAX]; void topologySort() { int result[MAX]; queue q; for (int i = 1; i

풀이 일시 : 2020-08-02 ​ 개념 : sort()의 활용방안 part2 ​ 활용1 : 클래스 대신 Pair 라이브러리 사용하기 #include #include #include using namespace std; int main() { vectorv; //vector pair 선언 v.push_back(pair(9, "A")); v.push_back(pair(8, "B")); v.push_back(pair(7, "C")); v.push_back(pair(5, "D")); v.push_back(pair(6, "E")); sort(v.begin(), v.end()); //숫자의 오름차순으로 정렬된다. for (int i = 0; i < v.size(); i++) { cout b.second.seco..

풀이 일시 : 2020-07-31 ​ 개념 : C++의 algorithm 헤더에 포함되어있는 함수로 정렬을 수행할 수 있다. ​ 활용1 : 기본 사용 - 주어진 숫자를 sort()로 쉽게 오름차순 정렬한다. #include #include using namespace std; int main(void) { int a[10] = { 9,3,5,4,1,10,8,6,7,2 }; sort(a, a + 10); for (int i = 0; i < 10; i++) { cout score < student.score; //기준 (내점수가 더 낮다면 우선순위가높다) } }; //클래스 생성완료 int main() { Student students[] = { Student("A",35), Student("B",24), ..