알고리즘 스터디 정렬 - 2309번
정렬 알고리즘 2309번 문제풀이
study안녕하세요. GDSC 안드로이드 파트 멤버 이하은입니다! 제가 이번 3주차에 맡은 문제는 2309번 입니다. 이름부터 호기심이 드는 문제인데, 어떤 문제인지 같이 보시죠!
백준 정렬 2309번. 일곱 난쟁이
https://www.acmicpc.net/problem/2309
가짜 난쟁이 2명을 어떻게 찾을 수 있을까요? 중요한 단서는 진짜 난쟁이 7명의 키의 합이 100이라는 것입니다. 따라서 9명의 키를 모두 더한 값에서 100을 뺀 다음에, 그 차이를 만들어낸 가짜 난쟁이 2명을 찾으면 됩니다! 이것을 코드로 구현하려면 어떻게 해야 할까요?
문제에 주어진 입력 예시는 다음과 같습니다.
20
7
23
19
10
15 i=5
25 j=6
8
13
위의 숫자들을 다 더하면 140이 나오는데요, 여기서 100을 뺐을 때 40이라는 차이를 만들어낸 가짜 난쟁이 두 명을 찾아서 이들을 제외하고 나머지 7명의 키를 오름차순으로 출력해주면 됩니다.
그 두 명을 찾기 위해 아래 코드처럼 이중 반복문을 사용할 수 있습니다. 이때 외부 루프는 합이 gap과 같아지는 두 원소를 찾을 때까지 반복되며, 내부 루프는 외부 루프의 현재 인덱스 바로 다음부터 배열 끝까지 탐색을 진행합니다.
bool found = false;
int i = 0;
while (!found) { // not found라면 반복
for (int j = i + 1; j < 9; j++) {
if (arr[i] + arr[j] == gap) {
// 가짜 난쟁이의 키는 0으로 만들기
arr[i] = 0, arr[j] = 0;
found = true;
break;
}
}
i++;
}
C++의 기본 배열은 원소 자체를 제거할 수 있는 방법이 없어서, 값을 0으로 만들고 출력에서는 이를 제외하는 방식으로 풀었습니다. 하지만, vector 컨테이너의 erase 함수를 사용하면 원소를 제거할 수 있습니다. 다만 주의할 점은 erase로 원소를 삭제하면 자동으로 한칸씩 원소들이 앞으로 당겨지기 때문에 i번째, j-1번째 원소를 삭제해줘야 합니다. 아래 C++ 코드들을 보시죠!
C++ 풀이
1. 기본 배열
#include <iostream>
#include <algorithm> // std::sort
using namespace std;
int main()
{
int arr[9]{}; // 0으로 초기화
int sum = 0;
// 난쟁이 9명의 키를 입력 받는다.
for (int i = 0; i < 9; i++) {
scanf("%d", &arr[i]);
sum += arr[i];
}
int gap = sum - 100;
bool found = false;
int i = 0;
while (!found) { // not found라면 반복
for (int j = i + 1; j < 9; j++) {
if (arr[i] + arr[j] == gap) {
// 가짜 난쟁이의 키는 0으로 만들기
arr[i] = 0, arr[j] = 0;
found = true;
break;
}
}
i++;
}
// 오름차순 정렬
std::sort(arr, arr + 9);
// 0을 제외하고 7명의 난쟁이 키 출력
for (int i = 2; i < 9; i++)
printf("%d\n", arr[i]);
return 0;
}
2. vector 컨테이너 사용
std::vector::erase 함수 레퍼런스
http://www.cplusplus.com/reference/vector/vector/erase/
#include <iostream>
#include <algorithm> // std::sort
#include <vector>
using namespace std;
int main()
{
vector<int> v; // 벡터는 크기 지정을 안 해줘도 된다!
int val, sum = 0;
for (int i = 0; i < 9; i++){
cin >> val;
v.push_back(val);
sum += val;
}
int gap = sum - 100;
bool found = false;
int i = 0;
while (!found) { // not found라면 반복
for (int j = i + 1; j < 9; j++) {
if (v[i] + v[j] == gap) {
v.erase(v.begin() + i); // 삭제 후 한칸씩 앞으로 당겨지므로
v.erase(v.begin() + (j - 1)); // j-1번째 원소 삭제
found = true;
break;
}
}
i++;
}
// 오름차순 정렬
sort(v.begin(), v.end());
for (auto& ele : v) // 범위 기반 for문
cout << ele << " ";
return 0;
}
이 문제를 파이썬으로 풀려면 어떻게 코드를 짜야 될까요?
Python 풀이
list = [int(input()) for i in range(9)]
total = sum(list)
for i in range(9):
for j in range(i + 1,9):
if 100 == total - (list[i] + list[j]):
a, b = list[i], list[j]
list.remove(a)
list.remove(b)
list.sort() # 오름차순 정렬
for i in range(len(list)):
print(list[i])
break
if len(list) < 9:
break
파이썬의 remove 함수는 인덱스가 아니라 ‘값을 기준으로’ 원소를 삭제합니다. 그런데 문제 조건에서 아홉 난쟁이의 키는 모두 다르다고 했기 때문에, 중복에 대한 고민 없이 ‘값을 기준으로’ 원소를 삭제할 수 있습니다.
sort 함수의 시간 복잡도
C++ STL algorithm의 std::sort 함수는 Introsort의 변형된 버전이라고 합니다. Introsort는 퀵정렬과 힙 정렬의 하이브리드이며, 마지막에 삽입 정렬까지 수행된다고 하네요. 그래서 이 std::sort 함수는 퀵정렬의 단점을 보완하여 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장합니다.
파이썬의 내장 함수 sort는 Timsort로 구현되어 있습니다. Introsort가 이론적인 최악의 경우를 대비해 변형시킨 알고리즘이라면, Timsort는 현실에서 있을 법한 다양한 데이터들에 대해 최적화를 시킨 알고리즘입니다. 기본적으로는 병합 정렬과 삽입 정렬의 하이브리드이며, 최악의 경우 O(NlogN)을 보장할 뿐 아니라 최선의 경우 O(N)에 수행도 가능한 알고리즘입니다. 이러한 Timsort는 Python 2.3부터 기본 정렬 알고리즘으로 사용되고 있으며, 이후 Java 등 많은 라이브러리에서 표준 정렬로 채택되었다고 하네요.
https://novlog.tistory.com/21
http://www.secmem.org/blog/2019/04/10/special-sorts/
https://realpython.com/sorting-algorithms-python/#the-timsort-algorithm-in-python
이미지 출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
내장 함수 sort의 실체를 얕게나마 알고나니 우리가 일반적으로 배우는 위와 같은 정렬 알고리즘들은 새발의 피에 불과하다는 걸 깨달았습니다. 퀵정렬과 같이 익히 알려진 알고리즘도 피벗을 어떻게 선택하느냐에 따라서 수십 가지 변형이 있고 각각의 특징이 다르며, 배열과 연결 리스트 등 어떤 자료구조를 사용하느냐에 따라서도 알고리즘의 동작이 달라질 수 있습니다.
정렬 알고리즘의 종류는 셀 수 없이 많고, 목적도 가지각색입니다. 심지어는 실용성은 전혀 없이 그저 재미로만 만들어진 알고리즘, 일부러 느리게 만든 알고리즘 등도 존재한다고 합니다. 하지만, 일반적으로 정렬은 효율적으로 자료를 검색하기 위해서 하는 것이라고 생각합니다. 대표적으로 선형 탐색보다 효율적인 이진 탐색도 정렬된 배열에서만 사용할 수 있는 알고리즘이죠.
이번 포스트를 통해 여러분도 정렬 알고리즘에 대해 새롭게 얻어가는 지식이 있었으면 좋겠네요!
마무리
2309번 풀이를 보니 확실히 파이썬이 C++보다 코드가 직관적이고 짧은 거 같은데, 아래 스크린샷에서 확인할 수 있듯이 사용한 메모리나 실행 시간 측면에서는 C++이 훨씬 우세하네요! 아직 파이썬 문법에는 익숙하지 않아서 거의 구글링에 의존하고 있지만, 이 스터디를 통해 파이썬에 더 익숙해졌으면 좋겠습니다!
그럼 이만 포스트를 마치겠습니다. 읽어주셔서 감사합니다.
