병합 정렬 (Merge Sort)

병합 정렬이란?병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 대표적인 정렬 알고리즘이다.배열을 작게 쪼개서 정렬한 뒤, 다시 합치면서 전체를 정렬해나가는 방식이다.핵심 개념 요약Divide (분할)배열을 반으로 나눈다.더 이상 나눌 수 없을 때까지 계속 쪼갠다 (즉, 길이가 1이 될 때까지).Conquer (정복)쪼개진 배열을 병합하며 정렬한다.두 개의 정렬된 배열을 하나의 정렬된 배열로 합친다병합 정렬 흐름예를 들어 배열이 아래와 같다고 해보자:[21, 10, 12, 20, 25, 13, 15, 22] 그림처럼 병합 정렬은 이 배열을 계속 반으로 쪼개고, 마지막에는 정렬된 조각들을 차례로 병합한다:가장 아래에선 [21], [10] 같이 한 원소짜리..

24060번: 알고리즘 수업 - 병합 정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1사용 언어: C++ 풀이Merge Sort (병합 정렬) 문제.기본 병합 정렬 구현 문제. 핵심은 정렬이 완료된 배열이 아니라, 정렬 중 원소가 배열 A에 저장되는 순간을 추적해서,K번째로 저장되는 값을 출력하는 것.병합 과정에서 A[i] = tmp[t]가 실행될 때마다 저장 횟수(cnt)를 세고,cnt == K가 되면 해당 값을 result에 저장한다.만약 저장 횟수가 K보다 작으면 -1 출력.#include using namespace std;int A[500001], tmp[500001];int N, K, cnt = 0, result = -1;void merge(int p, int q, int r) { int i = p, j = q + 1, t = ..

11650번: 좌표 정렬하기

11650번:  좌표 정렬하기사용 언어: C++ 풀이1) struct Point안에서 연산자 오버로딩을 통해 비교 방법을 만들거나,2) bool Compare 함수를 만들어서 포인트들을 비교할 수 있는 방법을 만든다.아래는 오버로딩을 할때 쓸 코드bool operator  아래는 2)로 푼 코드#include using namespace std;struct Point{ int x, y;};bool Compare(const Point &a, const Point &b){ if(a.x != b.x) { return a.x > N; vector V(N); for(int i=0; i> V[i].x; cin >> V[i].y; } sort(V.begi..

18870번: 좌표 압축

18870번:  좌표 압축사용 언어: C++ 풀이 실제로 값들을 비교해서 푸는게 아니라, 값들을 받아서 정렬 후 (중복값도 빼주면서), 정렬하지 않은 배열의 원소가 정렬된 배열의 몇 번째 인덱스인지 알아내면 그 값이 그 원소가 다른 몇 개의 원소보다 큰지 개수다.#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; int A[N]; for(int i=0; i> A[i]; } vector C; for(int i=0; i

2752번: 세수정렬

2752번: 세수정렬(BOJ C/C++) 사용 언어: C++ 문제 동규는 세수를 하다가 정렬이 하고싶어졌다. 숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다. 숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오. 입력 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. 출력 제일 작은 수, 그 다음 수, 제일 큰 수를 차례대로 출력한다. 첫 번째 풀이 그냥 버블정렬과도 같고 풀이들 중 시간복잡도가 가장 긴 O(n^2) 이다. 물론 지금은 배열의 크기가 작아서 상관없지만 크기가 커지만 이 풀이는 지양적이다. #include using namespace std; int ar..