본문으로 바로가기

주어진 상황에 맞게 적절한 정렬 알고리즘을 사용하여 문제를 해결할 수 있다.

2750: 수 정렬하기

선택 정렬, 삽입 정렬, 거품 정렬, 3가지 방식으로 풀었다.

#include <cstdio>
#include <cstring>

void swap(int*, int*);// 두 변수의 값을 바꾸는 함수
void sort(int*, int);// 선택 정렬 함수

int main() {
  int n;
  scanf("%d", &n);
  
  int arr[1000];
  for (int i=0; i<n; i++) {
    scanf("%d", &arr[i]);
  }
  
  sort(arr, n);
  
  for (int i=0; i<n; i++) {
    printf("%d\n", arr[i]);
  }
  
  return 0;
}

void swap(int &x, int &y) {
  int tmp = x;
  x = y;
  y= tmp;
}

void sort(int *array, int length) {
  for (int i=0; i<length; i++) {
    int min = array[i];// 정렬이 남은 수 중 가장 작은 수
    int minIdx = i;// 정렬이 남은 수 중 가장 작은 수의 인덱스
    for (int j=i+1; j<length; j++) {// i번째 인덱스부터 가장 작은 수를 선택하여 정렬
      if (array[j] < min) {
        min = array[j];
        minIdx = j;
      }
    }
    swap(array[i], array[minIdx]);// i번째 인덱스를 정렬이 남은 수 중 가장 작은 수로 설정
  }
}
#include <cstdio>
#include <cstring>

void swap(int*, int*);// 두 변수의 값을 바꾸는 함수
void sort(int*, int);// 삽입 정렬 함수

int main() {
  int n;
  scanf("%d", &n);
  
  int arr[1000];
  for (int i=0; i<n; i++) {
    scanf("%d", &arr[i]);
  }
  
  sort(arr, n);
  
  for (int i=0; i<n; i++) {
    printf("%d\n", arr[i]);
  }
  
  return 0;
}

void swap(int &x, int &y) {
  int tmp = x;
  x = y;
  y= tmp;
}

void sort(int *array, int length) {
  for (int i=0; i<length; i++) {
    int key = array[i];// i번째 인덱스의 수
    for (int j=0; j<i; j++) {// 적절한 위치에 수를 삽입하고 한 칸씩 뒤로 밀어낸다
      if (array[j] > key) {
        swap(array[j], key);
      }
    }
    array[i] = key;
  }
}
#include <cstdio>
#include <cstring>

void swap(int*, int*);// 두 변수의 값을 바꾸는 함수
void sort(int*, int);// 거품 정렬 함수

int main() {
  int n;
  scanf("%d", &n);
  
  int arr[1000];
  for (int i=0; i<n; i++) {
    scanf("%d", &arr[i]);
  }
  
  sort(arr, n);
  
  for (int i=0; i<n; i++) {
    printf("%d\n", arr[i]);
  }
  
  return 0;
}

void swap(int &x, int &y) {
  int tmp = x;
  x = y;
  y= tmp;
}

void sort(int *array, int length) {
  for (int i=0; i<length-1; i++) {
    for (int j=i+1; j<length; j++) {
      if (array[i] > array[j]) {// 마주한 인덱스를 비교하여 더 큰 수가 뒤로 가게 한다
        swap(array[i], array[j]);
      }
    }
  }
}

2751: 수 정렬하기 2

병합 정렬, 힙 정렬, 퀵 정렬, 3가지 방식으로 풀었다.

#include <cstdio>
#include <vector>
using namespace std;

void sort(vector<int>&, int, int);// 병합 정렬
void merge(vector<int>&, int, int, int);// 병합 

int main() {
  int n;
  scanf("%d", &n);
  
  vector<int> v;
  v.resize(n);
  
  for (int i=0; i<n; i++) {
    scanf("%d", &v[i]);
  }
  
  sort(v, 0, n-1);
  
  for (auto e: v) {
    printf("%d\n", e);
  }
  
  return 0;
}

void sort(vector<int>& v, int s, int e) {
  if (s < e) {
    int m = (s+e)/2;
    sort(v, s, m);// 배열의 반의 왼쪽
    sort(v, m+1, e);// 배열의 반의 오른쪽
    merge(v, s, m, e);// 병합
  }
}

void merge(vector<int>& v, int s, int m, int e) {
  vector<int> tmp;// 임시 배열
  
  // 반으로 나뉜 두 배열을 비교해가면서 병합
  int i = s, j = m+1;
  while (i <= m && j <= e) {
    if (v[i] < v[j]) {
      tmp.push_back(v[i]);
      i++;
    } else {
      tmp.push_back(v[j]);
      j++;
    }
  }
  
  // 나머지 값들을 마저 넣어준다
  while (i <= m) tmp.push_back(v[i++]);
  while (j <= e) tmp.push_back(v[j++]);
  
  // 정렬된 임시 배열을 원래 배열로 복사한다
  int k = 0;
  for (int i=s; i<=e; i++) {
    v[i] = tmp[k++];
  }
}
#include <cstdio>
#include <vector>
using namespace std;

void swap(int*, int*);// 두 변수의 값을 바꾸는 함수
void heapify(vector<int>&, int, int);// min-heap 트리를 만들어주는 함수
int root(vector<int>&, int);// min-heap 트리의 루트 원소를 반환하는 함수

int main() {
  int n;
  scanf("%d", &n);
  
  vector<int> v;
  v.resize(n+1);// 편의를 위해 인덱스 1부터 시작
  
  for (int i=1; i<=n; i++) {
    int x;
    scanf("%d", &x);
    heapify(v, x, i);
  }
  
  for (int i=0; i<n; i++) {
    printf("%d\n", root(v, n-i));
  }
  
  return 0;
}

void swap(int &x, int &y) {
  int tmp = x;
  x = y;
  y= tmp;
}

void heapify(vector<int>& v, int key, int length) {
  v[length] = key;
  int i = length;// 추가된 원소의 인덱스
  while (i != 1) {
    int j = i/2;// 부모의 인덱스
    // heapify: 부모의 값이 자식의 값보다 크면 부모와 자식의 값 교체
    if (v[j] > v[i]) {
      swap(v[i], v[j]);
      i = j;
    } else {
      break;
    }
  }
}

int root(vector<int>& v, int length) {
  int i = 1;// 루트 인덱스
  int ret = v[i];// 루트 원소 (최소값)
  
  v[i] = v.back();// 인덱스의 마지막 원소를 우선 루트로 올린다
  v.pop_back();
  
  // 트리를 타고 내려오면서 자식의 값이 부모의 값보다 작으면 부모와 자식을 교체한다
  while (1) {
    int left = 2*i;// 왼쪽 자식
    int right = 2*i+1;// 오른쪽 자식
    
    // 왼쪽 자식, 오른쪽 자식 모두 없는 경우
    if (right > length && left > length) {
      break;
    }
    // 왼쪽 자식만 존재하는 경우
    else if (right > length) {
      if (v[i] < v[left]) break;// 부모가 더 작으면 중단
      swap(v[i], v[left]);
      i = left;
    }
    // 왼쪽 자식과 오른쪽 자식이 모두 존재하는 경우
    else {
      // 왼쪽 자식의 값이 오른쪽 자식의 값보다 작은 경우
      if (v[left] < v[right]) {
        if (v[i] < v[left]) break;
        swap(v[i], v[left]);
        i = left;
      }
      // 오른쪽 자식의 값이 왼쪽 자식의 값보다 작은 경우
      else {
        if (v[i] < v[right]) break;
        swap(v[i], v[right]);
        i = right;
      }
    }
  }
  
  return ret;
}
#include <cstdio>
#include <vector>
using namespace std;

void swap(int*, int*);// 두 변수의 값을 바꾸는 함수
void sort(vector<int>&, int, int);// quick sort

int main() {
  int n;
  scanf("%d", &n);
  
  vector<int> v;
  v.resize(n);
  
  for (int i=0; i<n; i++) {
    scanf("%d", &v[i]);
  }
  
  sort(v, 0, n-1);
  
  for (auto e: v) {
    printf("%d\n", e);
  }
  
  return 0;
}

void swap(int &x, int &y) {
  int tmp = x;
  x = y;
  y= tmp;
}

void sort(vector<int>& v, int start, int end) {
  int i = start;
  int j = end;
  int pivot = v[(i+j)/2];
  
  while (i <= j) {
    while (v[i] < pivot) i++;
    while (v[j] > pivot) j--;
    if (i <= j) {
      swap(v[i], v[j]);
      i++;
      j--;
    }
  }
  
  if (start < j) sort(v, start, j);
  if (end > i) sort(v, i, end);
}

10989: 수 정렬하기 3

계수 정렬과 기수 정렬, 2가지 방식으로 풀었다.

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

int main() {
  int n;
  scanf("%d", &n);
  
  vector<int> v;
  vector<int> k;
  k.resize(10001);
  fill(k.begin(), k.end(), 0);
  
  for (int i=0; i<n; i++) {
    int x;
    scanf("%d", &x);
    if (!k[x]++) {
      v.push_back(x);
    }
  }
  
  sort(v.begin(), v.end());
  
  for (auto e: v) {
    for (int i=0; i<k[e]; i++) {
      printf("%d\n", e);
    }
  }
  
  return 0;
}
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<vector<int>>> v;
vector<int> k;

void sort();// 기수 정렬 

int main() {
  int n;
  scanf("%d", &n);
  
  v.resize(6);
  for (int i=0; i<6; i++) {
    v[i].resize(10);
  }
  
  k.resize(10001);
  
  for (int i=0; i<n; i++) {
    int x;
    scanf("%d", &x);
    if (!k[x]++) {
      v[0][0].push_back(x);
    }
  }
  
  sort();
  
  for (auto e: v[5]) {
    for (auto f: e) {
      for (int i=0; i<k[f]; i++) {
        printf("%d\n", f);
      }
    }
  }
  
  return 0;
}

void sort() {
  int mod = 1;
  for (int i=1; i<6; i++) {
    for (int j=0; j<10; j++) {
      for (auto e: v[i-1][j]) {
        int r = (e/mod)%10;
        v[i][r].push_back(e);
      }
    }
    mod *= 10;
  }
}

2108: 통계학

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int MIN = -1;
const int MAX = 8001;

int main() {
  int n;
  scanf("%d", &n);
  
  vector<int> v;
  v.resize(n);
  
  int sum = 0;
  int min = MAX;
  int max = MIN;
  int k = 0;
  int nc[8001];// number count
  memset(nc, 0, sizeof(nc));
  
  for (int i=0; i<n; i++) {
    scanf("%d", &v[i]);
    sum += v[i];
    min = min < v[i] ? min : v[i];
    max = max > v[i] ? max : v[i];
    
    int j = v[i]+4000;// 편리를 위해 0~8000까지 계산 후 -4000한 값을 출력한다
    nc[j]++;
    k = k > nc[j] ? k : nc[j];
  }
  
  sort(v.begin(), v.end());
  
  printf("%.0f\n", (float)sum/n);
  printf("%d\n", v[n/2]);
  
  vector<int> fn;// frequent number
  for (int i=0; i<8001; i++) {
    if (nc[i] == k) {
      fn.push_back(i);
    }
  }
  
  if (fn.size() > 1) {
    sort(fn.begin(), fn.end());
    printf("%d\n", fn[1]-4000);
  } else {
    printf("%d\n", fn[0]-4000);
  }
  
  printf("%d\n", max-min);
  
  return 0;
}

산술평균, 중앙값, 최대값과 최소값의 차이는 어렵지 않게 구할 수 있다. 다만 최빈값을 구할 때 해당 값이 나온 수를 체크하려 했는데 음수를 체크할 수 없어 임시로 +4000하여 범위를 -4000~40000~8000으로 설정한 후 추후에 -4000 해주었다.

1427: 소트인사이드

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

int main() {
  char s[11];
  scanf("%s", s);
  
  vector<int> v;
  
  auto l = strlen(s);
  for (auto i=0; i<l; i++) {
    int e = s[i] - '0';
    v.push_back(e);
  }
  
  sort(v.begin(), v.end(), greater<int>());// sort descending order
  
  for (auto e: v) {
    printf("%d", e);
  }
  
  puts("");
  return 0;
}

greater 함수를 이용해 내림차순으로 정렬해주면 된다.

1181: 단어 정렬

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

int main() {
  int n;
  scanf("%d", &n);
  
  vector<vector<string>> v;
  v.resize(51);
  
  while (n--) {
    string s;
    cin >> s;
    auto l = s.length();
    auto p = find(v[l].begin(), v[l].end(), s);
    if (p == v[l].end()) {// 중복 단어 방지
      v[l].push_back(s);// 글자 수 별로 따로 저장
    }
  }
  
  for (auto e: v) {
    sort(e.begin(), e.end());
    for (auto f: e) {
      cout << f << '\n';
    }
  }
  
  return 0;
}

글자 수 별로 문자열을 따로 저장하고 각각 정렬해주면 된다.


댓글을 달아 주세요