우리들의 T'SPACE

효율적인 정렬을 위한 강력한 무기, 합병 정렬 프로그래밍 분야에서 정렬 알고리즘은 매우 중요한 위치를 차지합니다. 데이터를 특정 순서로 정렬하는 것은 다양한 문제를 해결하는 데 필수적입니다. 이러한 정렬 알고리즘 중 하나인 머지 소트(Merge Sort)는 분할 정복(Divide and Conquer) 기법을 활용하여 효율적이고 안정적인 정렬을 수행합니다. 작동 원리 살펴보기 머지 소트는 다음과 같은 세 단계로 진행됩니다. 1. 분할(Divide) 먼저, 정렬해야 할 배열을 두 개의 서브 배열로 나눕니다. 이 과정을 재귀적으로 반복하여 배열의 크기가 1이 될 때까지 계속 분할합니다. 배열의 크기가 1이 되면 더 이상 나눌 수 없으므로, 이를 기저 조건(base case)으로 합니다. 2. 정복(Conqu..

* 문제 이해와 해결 과정 땅을 고르게 만들어야 함. 땅을 고르게 만드는 방법에는 2가지가 존재하며 각각 소요시간이 다름. 땅의 높이는 0~256이 될 수 있음. 나에게 주어지는 것은 땅의 가로, 세로 길이와 각 땅의 높이, 인벤토리에 보관 중인 블럭들임. 첫 시도는 실패했는데, 2가지 작업을 동시에 해줄 수 있다는 점과 높이가 0~256일 때의 모든 경우를 고려하여 탐색해야 한다는 점을 간과했다. 결국 문제에서 원하는 것은 최소 시간과 높이다. 높이가 0일 때 시간이 가장 적게 들 수도 있고, 높이가 256일 때 시간이 가장 적게 들 수도 있다. 1)블럭을 파내어 인벤토리에 넣는 작업과 2)인벤토리에 있는 블럭을 꺼내어 쌓는 작업을 적절하게 사용해야한다는 뜻이다. 그래서 높이가 0일때 부터 256일때 ..

https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net * 해결 아이디어 N명의 사람의 15%를 구한 후, 1~30점 난이도 의견 배열의 앞과 뒤에서 1씩 빼준다. 그려면 30% 절사평균이 구현되며, 배열에 들어있는 값들을 평균내어 문제에 알맞게 출력하면 된다. #include #include #include #include #include #include #include #include #include #include #..

C++ 입출력 최적화: sync_with_stdio와 cin.tie 이해하기 코딩테스트에서 표준 입출력을 사용할 때 주로 scanf/printf 또는 cin/cout을 사용합니다. C++에서는 string과 같은 편의 기능을 제공하는 cin/cout을 주로 사용하게 됩니다. 그러나 주의해야 할 점은 cin/cout을 사용할 때 시간초과를 막기 위해 특별한 조치가 필요하다는 점입니다. 1. ios::sync_with_stdio(0)과 cin.tie(0) C++에서는 입출력 버퍼를 동기화하는 작업이 기본적으로 수행됩니다. 그러나 이 작업은 입출력의 양이 많을 때 시간을 소비할 수 있습니다. 따라서, 입출력 작업이 많은 경우에는 이 동기화 작업을 해제하는 것이 좋습니다. 동기화 작업 해제를 위해 아래의 두 명..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net #include #include using namespace std; int main() { int count = 0; int test_case; cin >> test_case; int n, m, ipt;//문서의 개수, 궁금한 문서 위치, 중요도 for (int i = 0; i > n >> m; queue q; priority_queu..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net #include #include // for sorting using namespace std; const int MAX_SIZE = 100000; int binarySearch(int arr[], int low, int high, int target) { while (low > n; // Dynamic allocation of memory for ..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. #include #include #include using namespace std; int m, n; int main(void) { cin..

https://www.acmicpc.net/problem/1436 문제 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작..