유자의 코딩모험

해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘. 주어진 배열 중에 최솟값을 찾고 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1)/2만큼의 비교가 일어나기 때문에 n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자..

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 가장 큰 값을 배열의 맨 끝에 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다. 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라 지어졌다고 한다. 구현 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이므로 O(n^2) 정렬이 되어있든지 안되어있든지 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 구현이 매우 간단하고 소스코드가 직관적이다. 추가적인 메모..

1205번: 등수 구하기 첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000 www.acmicpc.net 문제풀이 먼저 점수를 입력받아서 송유진의 새로운 점수를 추가한 후 내림차순으로 정렬한다. 같은 점수가 있을 때는 그러한 점수의 등수 중에서 가장 작은 등수가 된다. 예제를 한 번 살펴보자. 랭킹 리스트가 100, 90, 90, 80일 때 각각의 드수는 1, 2, 2, 4등이 된다. 점수가 제일 처음 나온 인덱스 + 1이 등수가 되고 동일한 점수가 나올 때까지 인덱스를 이동해준다. 송유진의 점수와 동일한 점수를 만날 때까지 반복문을 진..

10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 N개의 정수를 오름차순으로 정렬하는 문제다. 이때 같은 정수는 한 번만 출력해야 한다. 벡터를 정렬해서 중복을 제거한 후 출력을 해주면 되는 아주 간단한 문제다! C++ 코드

1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제풀이 다음과 같이 함수 S를 정의한다. S = A[0] x B[0] + ... + A[N-1] x B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열해서 S의 최솟값을 구한다. A는 오름차순, B는 내림차순으로 정렬한 후에 곱하면 S의 최솟값을 구할 수 있다. C++ 코드