게임 개발 로그

문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.   입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.   출력첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.   성공 코드  머지 소트를 연습하기 위해서 머지 소트를 구현해 봤다. 첫 제출에 시간 초과로 실패가 떴는데, 그 이유는 입출력 속도 탓이었다. 버릇처럼 endl을 사용하는 바람에 시간 초과가 떴고, endl 대신 "\n"을 넣어서 성공할 수 있었다.#include #include using namespace std;vector nums..

병합 정렬  병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘으로, 시간 복잡도는 O(nlogn)이다. 투 포인터 개념을 사용하여 배열의 원소를 나누며, 왼쪽, 오른쪽 그룹을 병합해간다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값(혹은 큰 값)을 배열에 추가하고, 포인터를 한 칸씩 이동시키는 방식이다.  합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (위키백과 발췌)  n-way 합병 정렬의 개념은 다음과 같다.정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로..

문제수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.  입력첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)  출력A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.   실패 코드실패 이유: 시간 초과 - vector를 사용하여 동적할당하던 것에서 전역변수로 바꿔 배열을 선언했는데도 시간 초과가 뜸.- Quick Selection Sort라는 것을 이용하여 필요한 부분만 Sorting을 하고 있는데도 시간 초과가 뜸.- cin, cout 등 입출력 속도를 향상시킬 수 있도록 명령어를 추가했는데 ..

퀵 정렬  퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해서 정렬하는 알고리즘이다. 평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)의 시간 복잡도를 가진다.     퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 ..