꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/10824 string을 통해 bigInteger 덧셈을 구현하면 간단히 풀리는 문제였습니다. #include #include #include using namespace std; string bigNumAdd(string num1, string num2) { long long sum = 0; string result; //1의 자리부터 더하기 시작한다 while (!num1.empty() || !num2.empty() || sum) { if (!num1.empty()) { sum += num1.back() - '0'; num1.pop_back(); } if (!num2.empty()) { sum += num2.back() - '..

문제 링크입니다: https://www.acmicpc.net/problem/1561 문제를 'x분에 몇 번째 학생부터 몇 번째 학생이 놀이기구를 타는가?'로 바꾸어야했던 문제였습니다. 알고리즘은 아래와 같습니다.1. 놀이기구 수보다 아이들의 수가 적으면 아이들의 수를 출력해주면 됩니다.2. 이분 탐색을 통해 마지막 아이가 탑승한 시간을 찾습니다.3. (2번에서 구한 시간 - 1)분까지 몇 명의 아이들이 탑승했는지 탐색합니다.4. 3번을 토대로 2번에서 구한 시간에 마지막으로 탑승하는 아이가 타는 놀이기구를 찾으면 됩니다. #include #include using namespace std; const int MAX = 10000; int N, M; int ride[MAX]; long long binary..

문제 링크입니다: https://www.acmicpc.net/problem/2917 조건이 많이 붙어있는 BFS(Breadth First Search) 알고리즘 문제였습니다.해당 문제를 풀기 위해서는 나무들로부터의 최소거리를 찾기 위해 queue 자료구조를 사용해야하고 경로를 찾기 위해서는 priority_queue를 사용해야합니다.나무들로부터의 최소거리를 찾는 것까지는 성공했으나 경로를 priority_queue를 이용해서 풀 생각을 못 했기 때문에 kdk8361님(http://organize-study.tistory.com/34) 포스팅을 참고해서 풀었습니다. 알고리즘은 아래와 같습니다.1. dist[][] 배열은 나무들로부터의 최소거리이기 때문에 나무들의 좌표를 queue에 넣고 dist[i][j]..

문제 링크입니다: https://www.acmicpc.net/problem/2923 그리디하게 접근해야함을 증명해야하는 알고리즘 문제였습니다.처음에 A의 Max와 B의 Min을 더해주면 답이라고 접근했고 이후에는 모르겠어서 솔루션을 참고했습니다. 그리디하게 접근하기 위해 아래와 같이 가정을 하고 증명해 나가야합니다.i) A의 Max와 B의 Min을 더하는 것이 가장 큰 값이다ii) A의 Max와 B의 Min을 더하는 것은 가장 큰 값이 아니다. i)와 같이 가정을 했을 경우 B의 다른 값을 넣어도 최적의 값에서 감소시킬 수 없다는 것이 자명합니다. 따라서, i)와 같은 경우에는 B의 Min과 동일한 값을 더해서 똑같은 값을 구하는 것이 최적입니다. ii)와 같이 가정을 했을 경우 Ax + Bx 가 가장 ..

문제 링크입니다: https://www.acmicpc.net/problem/15633 제곱수인 경우에는 약수 하나만 더해준다는 것만 유의한다면 쉽게 풀 수 있는 문제였습니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; long long sum = 0; for (int i = 1; i*i

문제 링크입니다: https://www.acmicpc.net/problem/3047 간단한 정렬 문제였습니다. #include #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); vector v(3); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); string s; cin >> s; for (int i = 0; i < s.length(); i++) cout

문제 링크입니다: https://www.acmicpc.net/problem/1550 간단한 진법 변환 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); string s; cin >> s; long long result = 0; long long temp = 1; for (int i = s.length() - 1; i >= 0; i--) { if (s[i] >= '0' && s[i]

문제 링크입니다: https://www.acmicpc.net/problem/1212 간단한 진법 변환 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); string s; cin >> s; //0인 경우 if (s == "0") { cout

문제 링크입니다: https://www.acmicpc.net/problem/2153 문제를 잘 읽어야하는 문제였습니다.해당 문제에서는 1도 소수로 간주하기 때문에 에라토스테네스의 체 함수를 진행할 때 minFactor[0]만 -1로 초기화해줘야합니다.단순 에라토스테네스의 체 구현 문제였기 때문에 쉽게 풀 수 있는 문제였습니다. #include #include #include #include using namespace std; const int MAX = 52 * 20 + 10; int minFactor[MAX]; void eratosthenes(void) { //이 문제에서는 1도 소수;; minFactor[0] = -1; for (int i = 1; i < MAX; i++) minFactor[i] =..

문제 링크입니다: https://www.acmicpc.net/problem/11286 앞서 푼 최소 힙, 최대 힙 문제보다는 까다로웠지만 pair 형 힙을 사용하면 쉽게 풀 수 있는 문제였습니다.이 문제의 경우 절댓값 최소 힙을 구현하는게 편할 것 같아 기존과는 다르게 디폴트 우선순위 큐에서 - 를 곱한 값을 넣도록 했습니다. #include #include #include #include #include #include using namespace std; map visited; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; priority_queue pq; for (int i = 0; i < N; i++) { i..