[알고리즘 공부 8일차]

1.수 정렬하기

시간복잡도가 O(n^2)인 삽입정렬을 통해 해결할수있다

#include <iostream>

using namespace std;
int main(void)
{
	int a,i = 0,temp;
	int b[1000];
	cin >> a;
	temp = a;
	while (temp--)
	{
		cin >> b[i++];
	}
	for (int i = 0; i < a; i++)
	{
		for (int j = i + 1; j < a; j++)
		{
			if (b[j] <= b[i])
			{
				temp = b[i];
				b[i] = b[j];
				b[j] = temp;
			}
		}
	}
	for (int i = 0; i < a; i++)
	{
		printf("%d\n", b[i]);
	}
}

2. 수정렬하기 2

algorithm에 내장되어있는 sort() 함수를 이용하여 해결하였다

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
	int a,i=0,temp;
	int b[1000000];
	cin >> a;
	temp = a;
	while (temp--)
	{
		cin >> b[i++];
	}
	sort(b, b + a);
	for (int i = 0; i < a; i++)
	{
		printf("%d\n", b[i]);
	}
}

3. 수정렬하기 3

메모리가 매우 한적정이다 카운팅알고리즘을 사용하면서 메모리를 줄여야한다 이경우 값을 입력받으면서 최대값을 구하고 최대값만큼만 반복을 하면서 시간과 공간모두 절약한다

#include <cstdio>

using namespace std;

int C[10001] = { 0, };
int main() {

    int N, i, j, temp, max;

    scanf("%d", &N);

    max = 0;
    for (i = 0; i < N; i++) {
        scanf("%d", &temp);
        C[temp]++;
        if (temp > max) max = temp;
    }

    for (i = 0; i <= max; i++) {
        for (j = 0; j < C[i]; j++) printf("%d ", i);
    }
    printf("\n");
    return 0;
}

4. 통계학

배열은 두개를 사용한다 정수형 크기 500000배열과 8001의 배열이다 전자에는 입력받은 정수만큼만 사용하고 후자는 최빈값을 나타내기위해 인자의 빈도를 체크한다.

정수 a를 입력받아 a만큼 수를 입력받아 배열에 저장한다 이때 입력받은수 +4000을해 빈도를 체크한다 (배열의 인덱스이기때문에 양의 정수로 만들어야해서)

다음 최빈값을 제일 먼저 나오는것으로 정하고 최빈값이 두개 일경우 두번째로 작은수를 하라고 문제에 명시되어있기때문에 key + 1부터 반복문을 통해 최빈값을 정한다

산술평균은 round()함수를 통해
중앙값은 배열의 중앙값 (n-1/2)(0부터시작하기때문)
최빈값은 위의 방법대로
범위는 sort()로 정렬한후에 마지막값에서 첫번째값을 빼주면된다.

5.소트 인사이드

크기 11의 char배열을만들어 입력받은후 반복문을 통해 길이를 잰다
다음 길이만큼 반복문을 통해 정렬해주면된다. sort()를 이용할수도있다

6.좌표 정렬하기

pair 클래스를 통해 문제를 해결했다 pair 클래스에 x,y좌표를 입력받은후 sort()함수를 통해 정렬 가능하다

7.좌표 정렬하기

6번에서 y를 먼저 정렬하면 해결가능하다 입력이 x , y 일때 x를 세컨드에 y를 퍼스트에 넣어준다음 정렬하고 출력도 이와같이 하면 해결가능하다.

8. 단어 정렬

스트링 벡터를 통해 해결했다 벡터에 입력받은후 sort함수에서 compare 사용자 정의 함수를 넣어준다 사이즈가 같다면 내용을 비교하고 다르다면 사이즈의 비교값을 리턴해주면된다 출력에서는 같은값은 한번 출력하라고 했으므로 temp값에 출력값을 넣어 비교해주면서 하면된다.

9. 나이순 정렬

8번과 비슷하다 stable정렬을 이용해 안정성을 확보한다

10. 좌표 압축

1. 매 좌표마다 값,index를 vector pair형태로 저장한다.

2. 값을 기준으로(vector.first) 오름차순 정렬

3. 오름차순 정렬된 상태에서 답을 ans vector에 index 오름차순로 중복을 고려하여 저장

4. ans vector의 값을 출력