[2025 1학기 알고리즘 스터디] 신지은 #1주차

1. 수 정렬하기3(https://www.acmicpc.net/problem/10989)

첫 번째 시도 - 실패, 그림 그리면서 열심히 했는데.. 메모리 초과 :(

#include<iostream>
using namespace std;

void SortFunction(int arr[], int n) { //정수 배열 정렬
    for (int i = 1; i < n; i++) {
        int k = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > k) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = k;
    }
}

int main() {
    int n; //몇 개의 정수를 입력할 것인지 결정
    cin >> n;

    int* numbers = new int[n]; //정수형 포인터를 선언해서 동적 배열 할당

    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    SortFunction(numbers, n);

    for (int i = 0; i < n; i++) {
        cout << numbers[i] << "\n"; //줄 바꾸기
    }

    delete[] numbers;

    return 0; //프로그램 종료
}

 

두 번째 시도 - 성공! 메모리 초과를 막기 위해서 배열의 크기를 미리 지정하고 코드 길이도 줄였습니다 :)

#include <iostream>
using namespace std;

int main() {
    int n; //몇 개의 정수를 입력할 것인지 결정
    cin >> n;
    
    int count[10001] = { 0 }; //문제에서 주어진 배열 크기 제한

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        count[num]++; //해당 숫자의 count를 증가
    }

    for (int i = 1; i <= 10000; i++) { //순차적으로 배열을 검사
        while (count[i] > 0) {
            cout << i << "\n";
            count[i]--;
        }
    }
    return 0;
}

이 코드는 사용자로부터 입력받을 수의 개수를 입력받고 count 배열을 이용하여 0부터 10000까지의 자연수가 몇 번 등장했는지 기록하는 역할을 합니다. count[i]는 숫자 i가 몇 번 등장했는지 나타내고 배열의 인덱스 값이 숫자 값이라고 생각하면 됩니다. 각 숫자를 입력받고 해당 숫자가 등장한 횟수를 증가시킵니다. count[i]가 0보다 크다면 i에 해당하는 숫자를 사용자가 입력했음을 의미하므로 count[i]만큼 i를 출력합니다. while(count[i] > 0)은 수 i가 등장한 횟수만큼 출력하고 그 후에 count[i]--로 하나씩 감소시켜 더 이상 출력되지 않도록 합니다.

 

하지만 이 방법도 단점이 있습니다. 

수의 범위가 커질 수록 비효율적이고 입력값이 너무 커질 경우 메모리와 입력 시간에 영향을 줄 수도 있습니다.

즉, 이 코드는 수의 범위가 적고 수가 많이 있을 때 효율적이라고 볼 수 있습니다.

---

2. 카드(https://www.acmicpc.net/problem/11652)

처음에 1번 문제에서 사용한 배열 count를 사용해서 2번 문제도 간단하게 풀 수 있을 거라고 생각했는데

어림도 없길래 최빈값을 계산하는 알고리즘을 chat gpt에 물어봤습니다..

#include<iostream>
#include<map>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int max = 0;
	long long int maxN = 0;

	map<long long int, int>card; //map 선언, 큰 범위의 정수도 처리할 수 있도록 long long int
	for (int i = 0; i < n; i++)
	{
		long long int temp;
		cin >> temp;
		card[temp]++;
	}
	for (auto& val : card)
	{
		if (val.second > max)
		{
			max = val.second; //map의 value값
			maxN = val.first; //map의 key값
		}
	}
	cout << maxN << endl;
	return 0;
}

 

이 코드는 사용자가 입력한 숫자 카드 중에서 가장 많이 등장한 정수를 찾아서 출력합니다. n번 동안 사용자가 입력한 숫자 카드를 하나씩 받아 temp에 저장합니다. card[temp]++는 temp가 card에 이미 존재하면 그 값을 1 증가시키고 만약 존재하지 않으면 temp를 새로운 키로 추가하고 값은 1로 설정합니다. map에서 각 key-value 쌍을 순회하면서, val.second (value, 즉 등장 횟수)가 max보다 크면 해당 값을 max로 업데이트하고 그와 관련된 val.first (key, 즉 숫자)를 maxN으로 업데이트합니다. 이 부분은 가장 많이 등장한 숫자와 그 숫자의 등장 횟수를 찾는 부분입니다.

 

카드 문제를 풀면서 최빈값을 출력해내기 위해서 map에 대해 공부했습니다.

map은 C++에서 제공하는 연관 배열이고 각 key-value를 쌍으로 데이터를 저장하는 자료 구조입니다.

이러한 특성 덕분에 map을 이용하면 빈도수 계산이나 key-value를 기반으로 하는 문제에서 유용하게 사용할 수 있습니다.

 

이 문제에서 사용된 map의 장점

자동 정렬 - 내부에서 오름차순으로 키를 자동 정렬

빠른 검색, 삽입, 삭제 - 이진 탐색 트리를 기반으로 구현

---

3.좌표압축(https://www.acmicpc.net/problem/18870)

이 문제는 좌표압축에 대한 이해가 필요합니다...

주어진 좌표들이 만약 2, 4, -10, 4, 3이라면

이 좌표들을 오름차순으로 정렬해서 -10, 2, 3, 4, 4가 되고 각 좌표에 대해 자신보다 작은 값들의 개수를 계산합니다.

-10보다 작은 값은 없으니까 압축된 값은 0이고

2보다 작은 값은 -10 한 개니까 압축된 값은 1

3보다 작은 값은 -10, 2 두 개니까 압축된 값은 2

4보다 작은 값은 -10, 2, 3 세 개니까 압축된 값은 3

따라서 좌표압축 후의 결과는 1 3 0 3 2 가 되는 것입니다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n; //숫자의 개수를 입력

    int* x = new int[n];
    int* wink = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> x[i];
        wink[i] = x[i];
    }

    sort(wink, wink + n);
    int newSize = unique(wink, wink + n) - wink;

    for (int i = 0; i < n; i++) { //정렬된 배열에서 현재 값이 몇 번째로 작은지 찾기
        int compressedValue = lower_bound(wink, wink + newSize, x[i]) - wink;
        cout << compressedValue << " ";
    }
    cout << endl;

    delete[] x;
    delete[] wink;

    return 0;
}

이 프로그램은 먼저 n개의 좌표를 입력받고 2개의 배열을 만듭니다. wink 배열을 오름차순으로 정렬하고 unique()함수를 사용해서 중복을 제거합니다. 이제 wink 배열에는 중복 없이 정렬된 좌표 목록이 남아있을 것입니다. 이제 원래 좌표가 정렬된 좌표 목록에서 몇 번째 작은 값인지 찾기 위해 lower_bound()함수를 사용합니다. 이 함수는 이진 탐색을 이용해서 특정 값이 처음 등장하는 위치를 찾아줍니다. 찾은 위치를 wink 배열의 index로 변환하면 이게 압축된 좌표 값이 되는 것입니다!

 

여기서 이진 탐색이란 찾고자 하는 값을 배열의 가운데 값과 비교하고 가운데 값이 찾는 값보다 크면 왼쪽 부분만 탐색, 가운데 값이 찾는 값보다 작으면 오른쪽 부분만 탐색하는 방법입니다.

 

이 문제에서 사용된 algorithm의 장점

자동 정렬 - 수동으로 정렬 알고리즘을 구현할 필요 x

중복 제거 - 연속된 중복 원소를 제거해서 메모리를 추가로 사용하지 않고 제자리 수행

이진 탐색 - 압축된 값으로 변환하는데 사용