URL : https://www.acmicpc.net/problem/tag/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4
/* 문제 : [14501] 퇴사
[input]
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
[output]
45
[설명]
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
1일 2일 3일 4일 5일 6일 7일
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 200
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다.
5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다.
2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
*/
dp로 해결하며, 반대로 풀면 더 쉽게 풀 수 있다.
#include <iostream>
using namespace std;
int t[1000] = { 0 }; // 상담 완료하는데 걸리는 시간
int p[1000] = { 0 }; // 상담 시 받게 될 금액
int dp[1000] = { 0 };
int getBigNum(int x, int y) {
return x > y ? x : y;
}
int main()
{
int N;
int completed_t;
// 입력
cin >> N;
for (int i = 1; i <= N; i++)
cin >> t[i] >> p[i];
for (int i = N; i > 0; i--) {
completed_t = i + t[i];
if (completed_t > N + 1) // 퇴사일을 초과하면
dp[i] = dp[i + 1];
else
dp[i] = getBigNum(dp[i + 1], dp[completed_t] + p[i]);
}
cout << dp[1] << endl; // 가장 큰 수 출력
return 0;
}
URL : https://www.acmicpc.net/problem/tag/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4
/* 문제 : [2309] 일곱 난쟁이
[input]
20
7
23
19
10
15
25
8
13
[output]
7
8
10
13
19
20
23
[설명]
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다.
일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다.
뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
*/
7개를 더했을 때 합이 100이 되면 된다
즉, 9개를 다 더한 후, 어떤걸 2개 빼야 100이 나오는지
이렇게 반복문을 돌며 전수조사해보면 알 수 있다.
i값 k값
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
...
#include <iostream>
#include <algorithm>
using namespace std;
void solution(int *arr, int sum); // 제외될 2명의 난쟁이 파악
int main()
{
int height[9]; // 9명의 난쟁이 키 입력
int sum = 0;
// 9명의 난쟁이 키 입력
for (int i = 0, k; i < 9; i++) {
cin >> k;
height[i] = k;
sum += k; // 난쟁이 키 9개를 모두 더해줌
}
solution(height, sum);
sort(height, height + 9);
// 최종 7명의 난쟁이 출력
for (int i = 2; i < 9; i++)
cout << height[i] << endl;
return 0;
}
void solution(int *arr, int sum) {
for (int i = 0; i < 8; i++) {
for (int k = (i + 1); k < 9; k++) {
if ((sum - (arr[i] + arr[k])) == 100) { // 정렬 시 걸러내기 위해 -1 할당
arr[i] = -1;
arr[k] = -1;
return;
}
}
}
}
URL : https://www.acmicpc.net/problem/tag/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4
/* 문제 : [1065] 한수
[input]
(case1)110
(case2)1
(case3)210
(case4)1000
[output]
(case1)99
(case2)1
(case3)105
(case4)144
[설명]
어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다.
등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다.
N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.
출력
첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.
*/
n을 입력받고, 1 <= 한수 <= n 를 만족하는 한수의 개수를 찾아야 한다.
한수는 등차수열을 의미하며,
예를들어
579는 차수가 2인 등차수열
975는 차수가 -2인 등차수열이다.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
int n;
int count = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
s = to_string(i);
count++;
for (int k = 0, temp; k < s.length() - 1; k++) {
if (k == 0)
temp = (s[k] - s[k + 1]);
else if ((k > 0) && temp != s[k] - s[k + 1]) {
count--;
break;
}
}
}
cout << count;
return 0;
}
함수가 정의될 때 렉시컬환경을 기억하는 함수를 말합니다.
간략히 아래의 예제로 살펴보겠습니다.
소스코드 — example.js
function createCounterClosure() {
let count = 0;
return {
increase: function() {
count++;
},
getCount: function() {
return count;
}
}
}
const counter1 = createCounterClosure();
const counter2 = createCounterClosure();
counter1.increase();
counter1.increase();
console.log('counter 1의 값 : ' + counter1.getCount());
counter2.increase();
console.log('counter 2의 값 : ' + counter2.getCount());
실행 결과
counter 1의 값 : 2
counter 1의 값 : 1
객체지향프로그래밍에서 인스턴스와 비슷한 느낌입니다.
그럼 다른 예제도 보겠습니다.
example.js
for (var i = 0; i < 5; i++) {
setTimeout(function() {
i = 0;
console.log(i);
}, 1000)
}
위의 코드는 0 1 2 3 4를 출력할 것 같지만
5 5 5 5 5를 출력합니다.
이런 결과가 나타난 이유는 클로저는 외부 변수에 대해 값이 아닌 참조로 접근하기 때문입니다.
즉, 클로저는 최종 갱신된 변수(i)에 대해서만 접근할 수 있으므로, 외부 함수가 전체 for문을 실행하고
리턴한 최종 i의 값을 리턴하게 됩니다.
example.js
for (var i = 0; i < 5; i++) {
(function(j) {
setTimeout(function() {
console.log(j);
}, 1000);
})(i);
}
이런 부작용을 고치기 위해서 “즉시 호출된 함수 표현식(Immediately Invoked Function Expression. IIFE)”를
사용할 수 있습니다. 이러면 i의 값이 j에 대입되어 0 1 2 3 4가 출력됩니다.
Git에서 reset과 revert에 차이에 대해 이해합니다. —
reset과 revert는 작업을 하다가 작업내용을 다시 되돌려야 하는 경우 사용하는 방법입니다.
두 방법에 대한 차이를 간단히 정리하겠습니다.
reset
원격저장소에 push하기전 로컬저장소에서 되돌릴 경우
(push 이전엔 말그대로 서버엔 아무 영향이 없는 상태라 로컬데이터만 reset이나 rebase 하면 된다)
revert
원격저장소에 push한 후 되돌릴 경우
(push 한 이후엔 서버의 데이터가 바뀌어 있기 때문에 reset 이나 rebase 는 좋지 않다)
주로 이럴 때 사용합니다.
앞과 뒤에서 삽입, 삭제를 자주 할 때 ( 중간에서의 삽입, 삭제는 좋지 않음 )
검색을 거의 하지 않을 때
랜덤 액세스를 해야할 때
서버처럼 받은 패킷들을 차례대로 처리할 때 (이 경우는 deque가 아닌 자체 자료구조를 만들어 사용하기도 함)
예제 소스코드(1)
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<pair<int, int>> q;
q.push(make_pair(1, 2));
int a = 2, b = 3;
pair<int, int> p = make_pair(a, b);
q.push(p);
cout << q.front().first << ' ' << q.front().second;
cout << q.back().first << ' ' << q.back().second;
while (!q.empty())
{
pair<int, int> n = q.front();
q.pop();
cout << n.first << ' ' << n.second << '\n';
}
cout << q.size();
q.push(make_pair(4, 5));
q.push(make_pair(5, 6));
queue<pair<int, int>> emt;
swap(q, emt);
cout << q.size();
}
예제 소스코드(2)
#include <iostream>
#include <queue>
using namespace std;
struct room {
int start;
int end;
room(int start, int end) :start(start), end(end) {};
};
bool operator < (room r1, room r2) {
if (r1.end != r2.end)
return r1.end > r2.end;
else
return r1.start > r2.start;
}
int main()
{
priority_queue<room> pQue;
int n;
int compareNum = -1;
int count = 0;
cin >> n;
for (int i = 0, s, k; i < n; i++) {
cin >> s >> k;
pQue.push(room(s, k));
}
while (!pQue.empty()) {
room r = pQue.top();
pQue.pop();
if (compareNum <= r.start) {
compareNum = r.end;
count++;
}
}
cout << count;
return 0;
}