덧!

중간에 공부한 내용을 빼먹고 진도를 나가(…) 순서를 맞추기 위해 부득이하게 data를 수정했습니다 ㅠ.. 실제 학습일 : 2022.05.06

Introduction

본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다.

정렬 알고리즘 비교하기

비교

  • 앞서 다룬 네 가지의 정렬 알고리즘을 비교하면 아래와 같습니다.
  • 추가적으로 대부분의 프로그래밍 언어에서는 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어있습니다.
정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징
선택 정렬 O(N^2) O(N) 아이디어가 매우 간단합니다.
삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠릅니다.
퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠릅니다. 최악의 경우엔 그러나 시간 복잡도가 O(N^2)이 나올 수 있습니다.
계수 정렬 O(N + K) O(N + K) 데이터 크기가 한정된 경우 사용 가능하지만, 매우 빠르게 동작합니다.

기본 정렬 라이브러리 수행 시간 비교

from random import randint
import time

# 선택 정렬 수행 시간 측정
# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
	array.append(randint(1, 100))
# 선택 정렬 프로그램 성능 측정
start_time = time.time()
for i in range (len(array)):
	min_index = i
	for j in range(i + 1, len(array)):
		if (array[min_index] < array[j]):
			min_index = j;
	array[i], array[min_index] = array[min_index], array[i]
# 측정 종료
end_time = time.time()
# 수행시간 출력
print("선택 정렬 성능 측정 :", end_time - start_time)

# 삽입 정렬 수행시간 측정
array = []
for _ in range(10000):
	array.append(randint(1, 100))
start_time = time.time()
for i in range (1, len(array)):
	for j in range (i, 0, -1):
		if array[j] < array[j - 1]:
			array[j], array[j - 1] = array[j - 1], array[j]
		else :
			break
# 측정 종료
end_time = time.time()
# 수행시간 출력
print("삽입 정렬 성능 측정 :", end_time - start_time)

# 계수 정렬 수행시간 측정
array = []
for _ in range(10000):
	array.append(randint(1, 100))
count = [0] * (max(array) + 1)
start_time = time.time()
for i in range(len(array)):
	count[array[i]] +=  1
array_new = []
for i in range(len(count)):
	for j in range (count[i]):
		array_new.append(i)
# 측정 종료
end_time = time.time()
# 수행시간 출력
print("계수 정렬 성능 측정 :", end_time - start_time)

# 기본 라이브러리 정렬 수행시간 측정
array = []
for _ in range(10000):
	array.append(randint(1, 100))
start_time = time.time()
array.sort() # 하이브리드 방식으로 구조화 되어 있어 빠릅니다.
end_time = time.time()
print("기본 정렬 라이브러리 성능 측정 :", end_time - start_time)

# 실행 결과
# 선택 정렬 성능 측정 : 3.6304821968078613
# 삽입 정렬 성능 측정 : 5.138005971908569
# 계수 정렬 성능 측정 : 0.0011670589447021484
# 기본 정렬 라이브러리 성능 측정 : 0.0006279945373535156

두 배열의 원소 교체

문제 설명

  • paul은 두 개의 배열 A, B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수 입니다.
  • paul은 최대 K 번 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다.
  • paul의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며 여러분은 동빈이를 도와야 합니다.
  • N, K 그리고 배열 A, B의 정보가 주여졌을 때, 최대 K 번 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
  • 예를 들어 N = 5, K = 3 이고 배열 A, B가 다음과 같다고 해봅시다.
    • 배열 A = [1, 2, 5, 4, 3]
    • 배열 B = [5, 5, 6, 6, 5]
  • 이 경우 다음과 같이 연산 세번이 허용됩니다.
    • 연산 1) 배열 A의 원소 1 - 배열 B의 원소 6
    • 연산 2) 배열 A의 원소 2 - 배열 B의 원소 6
    • 연산 3) 배열 A의 원소 3 - 배열 B의 원소 5
  • 세번의 연산 이후 배열의 합을 수하면 A 배열의 원소의 합은 26이 되며, 이는 최대값이 됩니다.

문제의 조건

  1. 난이도 : 하
  2. 풀이시간 : 15분
  3. 시간제한 : 2초
  4. 메모리 제한 : 128MB
  • 입력 조건
    • 첫번째 줄에 N, K가 공백을 기준으로 구분되어 입력됩니다. (1 <= N <= 100000, 0 <= K <= N)
    • 두번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10000000보다 작은 자연수입니다.
    • 세번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10000000보다 작은 자연수입니다.
  • 출력 조건 : 최대 K 번 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력합니다.
# 입력 예시
5 3
1 2 5 4 3
5 5 6 6 5
# 출력 예시
26

문제 해결 아이디어

  • 핵심 아이디어 : 매번 배열 A에서 가장 작은 원소를 고르고, 배열 B에서 가장 큰 원소를 교체 합니다.
  • 가장 먼저 배열 A는 오름차순 정렬을, B는 내림차순으로 정렬합니다.
  • 이후 두 배열의 원소를 첫번째 인덱스부터 차례로 확인하면서 A와 B의 원소보다 작을 때만 교체를 수행합니다.
  • 이 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보작하는 정렬알고리즘을 이용해야 합니다.

내가 푼 방법(Python)

n, k = map(int, input().split())
arr_a = list(map(int, input().split()))
arr_b = list(map(int, input().split()))

arr_a.sort()
arr_b.sort()
l = n - 1
m = k
for i in range(0, m):
	if arr_a[i] < arr_b[l - i]:
    	arr_a[i], arr_b[l - i] = arr_b[l - i], arr_a[i]
	else :
		m += 1
		continue

result = 0
for i in range(n):
    result += arr_a[i]
print(result)

답안 예시(Python)

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

for i i (k):
	if a[i] < b[i]:
		a[i], b[i] = b[i], a[i]
	else :
		break

print(sum(a))

답안 예시(C++)

#include <bits/stdc++.h>

using namespace std;
int n, k;
vector<int>a, b;

bool compare(int x, int y)
	return x > y;

int main(void)
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a.push_back(x);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), compare);
	int result = 0;
	for (int i = 0; i < k; j++)
		if (a[i] < b[i])
			swap(a[i], b[i]);
		else
			break ;
	for (int i = 0; i < n i++)
		result += a[i];

	cout << result << '\n';
	return (0);
}

🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻