![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/10814 문제온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입출력 예시 풀이 sort()는 기본적으로 안정 정렬을 지원하지 않기 때문에, 사용하면 틀리게 된다.결국, 입력을 받을 때 인덱스를 같이 저장하거나, 안정 정렬을 지원하는 stable_sort()를 사용해야한다. 아래 코드는 stable_sort()를 사용한 풀이다.#include #include #include using namespace std;struct Member { int age; ..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/11931 문제N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램을 작성하시오. 입출력 예시 풀이 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); int N; cin >> N; vector nums; for (int i = 0; i > n; nums.push_back(n); } sort(nums.rbegin(), nums.rend()); for (int i : nums) { cout
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/10989 💣 메모리 초과 메모리 제한이 8MB인게 핵심인 문제다. 퀵 정렬 시도하자마자 바로 컷 당해버렸다!계수 정렬을 이용하는 문제이다. 카운팅 소트Counting Sort라고도 한다.⭐ 그리고 입력받는 자연수들을 굳이 배열로 저장하여 갖고있을 필요도 없다! ⭐최대 1,000,000개의 값이 들어오는데 이 값들을 전부 배열에 저장하면 메모리 초과! 그 후 시간 초과, 출력 초과도.. 마주쳤는데.. 원인과 해결방법은 아래 풀이와 함께 참고하자. ✒ 카운팅 정렬의 원리 카운팅 정렬은 흥미롭게도 비교 기반 정렬 알고리즘이 아닌 정렬 알고리즘이다. 카운팅 정렬에서 카운트 배열을 사용하는 이유는, 주어진 배열의 각 원소의 출현 ..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/2751 🧨 시간 초과! 처음은 퀵 정렬로 구현하였으나 시간 초과로 실패했다. 두 번째엔 힙 정렬로 바꾸었지만 시간 초과! #1힙 정렬을 구현하였을 때, 시간초과의 원인은 출력방식에 있었다.cout endl;endl을 "\n"로 바꾸니 힙 정렬 구현 코드의 수정 없이도 바로 통과되었다.(무거운 flush 연산과 관련된 이야기인데, 조만간 따로 정리해 볼 예정이다.) #2설마! 처음에 구현했던 퀵 정렬도 혹시...? 하는 마음에 endl을 "\n"로 바꾸어 시도해 보았지만 여전히 시간초과다.🤣나의 퀵 정렬 구현 코드를 다시 살펴보니, 피벗(pivot)을 랜덤 선택하는 과정을 넣지 않아, 최악의 pivot이 선택되는 듯 하..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/2750 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입출력 예시 풀이 #1 | 퀵 정렬 (Quick Sort) 구현퀵 정렬(Quick Sort)을 구현한 풀이#include #include using namespace std;/* a와 b를 바꾸어주는 함수 */void swap(int& a, int& b) { int tmp = a; a = b; b = tmp;}/* pivot을 기준으로 벡터를 분할하는 함수 */int partition(vector& vec, int low, int high) { int pivot = vec[high]; int i ..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/1003 문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibona..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/1309 문제어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입출력 예시 풀이 | Dynamic Programming우리의 크기가 N 일 때 사자를 배치하는 경우의 수를 DP(N)으로 표현하였습니다..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/1010 문제재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/9655 문제돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입출력 예시 풀이 #1 | 랜덤 값을 이용한 풀이 (시뮬레이션)게임 진행에 대한 시뮬레이션을 하듯 1과 3 중 하나를 선택하는 경우를 바탕으로 풀었다.#include #include #include using namespace std;int main() { //.# 랜..
![]()
🔗 문제 링크 : https://www.acmicpc.net/problem/2747 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입출력 예시 풀이 #include using namespace std;int fib[50];int main() { ..
