[2025 1학기 알고리즘 스터디] 김민주 #1주차

알고리즘 스터디 1주차 : 정렬

 

1.  수 정렬하기 3

https://www.acmicpc.net/problem/10989

 

---

 

1번 문제는 수 정렬하기입니다! 

 

💡문제 분석 및 알고리즘 설계

N이 최대 10,000,000이고, 메모리 제한이 있으므로 생각나는 가장 빠른 정렬 방식을 택해서 구현했는데요

바로바로 QuickSort 입니다

 

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

int n;
vector <int> num;

int partition(vector<int>& arr, int l, int r) {
    int pivot_index = (l + r)/2;
    swap(arr[pivot_index], arr[r]);

    int pivot = arr[r];
    int i = l-1;
    for (int j =l; j < r; j++) {
        if (arr[j] <= pivot) {
            i += 1;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[r]);
    return (i+1);
}

void quicksort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int p_index = partition(arr, l, r);
        quicksort(arr, l, p_index - 1);
        quicksort(arr, p_index + 1, r);
    }
}

int main() {
    cin >> n;
    num.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    quicksort(num, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << num[i] << "\n"; 
    }

    return 0;
}

 

실행 결과는 아래와 같이 메모리 초과가 났습니다

 

코드를 짜기전에 메모리 계산을 안한 탓입니다

퀵소트는 각 수들을 저장해야하므로 10,000,000개의 수를 퀵소트 한다고 하면,

10,000,000개의 수를 저장해야합니다 ....

 

 

이럴때 사용하는 것이 카운팅 소트입니다

자연수의 범위가 한정되어있으므로 10,000,000개의 수를 모두 저장할 필요없이

10,001 개의 공간만이 필요합니다

 

Counting Sort는 아래와 같이 구현했고 입출력 시간을 줄이기위해 ios를 끊어주었습니다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, idx;
int cnt[10001]= {};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> idx;
		cnt[idx] += 1;
	}

	for (int i = 1; i < 10001; i++)
	{
		for (int j = 1; j <= cnt[i]; j++)
		{
			cout << i << "\n";
		}
	}
}

 

---

2. 카드

https://www.acmicpc.net/problem/11652

 

---

💡문제 분석 및 알고리즘 설계

숫자가 적혀있는 카드 N장, 

가장 많이 가지고 있는 카드를 구해라

 

for문과 if문으로 단순하게 구현했습니다

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int N;
long long card;
vector<long long> vec;
int maxNum = 0;
int cnt = 0;

int main(){
    freopen("input.txt", "r", stdin);
    cin >> N;
    int maxNum = 0;
    int cnt = 0;

	for (int i = 0; i < N; i++){
		cin >> card;
		vec.push_back(card);
	}

	sort(vec.begin(), vec.end());
    long long result = vec[0];


	for (int i = 1; i < N; i++){
		if (vec[i] == vec[i - 1]){
			cnt += 1;
			if (cnt > maxNum){
				maxNum = cnt;
				result = vec[i];
			}
		}else {
			cnt = 0;
        }
	}
	cout << result;
    return 0;
}

 

 

 

 

---

3. 좌표 압축

https://www.acmicpc.net/problem/18870

 

---

💡문제 분석 및 알고리즘 설계

숫자 배열 중 각 숫자보다 작은 수의 개수를 출력하는 문제입니다.

 

초기 알고리즘은 p는 sort 하고,

p2 기준으로 for문 돌리면서 오름차순으로 정렬된 p와 숫자가 같아지면,

그 수의 index 출력하도록 했습니다.

 

그러나 중복 값을 고려하지 못했고, 시간초과도 발생했습니다.

 

 

💡 틀린 부분 수정 or 다른 풀이

1. vector에서의 중복 값 제거 코드 추가
2. 시간초과 해결법
   • lower_bound 사용
   • pair 로 index랑 값을 묶어서 vector하나만 sort

풀이는 아래와 같습니다.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int N;

int main(){
    //freopen("/home/user/cpp_baekjoon/input.txt", "r", stdin);
    cin >> N;
    vector <int> p;
    p.resize(N);
    
    for (int i=0; i<N; i++){
        cin >> p[i];
    }
    vector <int> p2;
    p2 = p;

    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
     

    for (int i=0; i<N; i++){
        cout << lower_bound(p.begin(), p.end(), p2[i]) - p.begin() << " ";
    }
    return 0;
}

 

>>> 이 문제를 풀면서 배운 내용

vector 중복 값 제거

1. 벡터를 `sort` 한다.
2. `unique` 함수를 통해 중복된 값들을 벡터의 뒷부분으로 보낸다.
3. `erase` 함수를 통해 중복된 값을 제거한다.  

sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());

---

lower_bound 함수

이진탐색기반.
std::lower_bound() 함수는 정렬된 원소에 이진 탐색을 적용하여, 

특정 값 이상이 처음 나타나는 위치를 탐색하여 위치를 반환한다. 

반대로, upper_bound도 가능.  

반환형은 iterator이므로 index를 구하기위해서는 
lowet_bound 값에서 배열 첫번째 주소를 가리키는 배열의 이름을 빼주어야 한다.  

lower_bound(p.begin(), p.end(), p2[i]) - p.begin()