정렬

[Silver III] 시리얼 번호 - 1431 문제 링크 성능 요약 메모리: 69108 KB, 시간: 20 ms 분류 정렬 제출 일자 2024년 2월 2일 10:55:41 문제 설명 다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다. 모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다. 시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다. A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인..

Radix Sort 지금까지는 정렬을 할 때 비교를 통해 정렬을 진행했습니다. 기수 정렬(radix sort)이란 정수를 선형 시간으로 정렬하기 위한 비교하지 않는(non-comparative) 알고리즘입니다. 문제에 따라 매우 다양한 기수 정렬이 존재합니다. 이번 장에서는 기수 정렬의 최수 유효 자리(least significant digit, LSD) 변형을 조사하면서 기본 10진수에 대해 집중할 예정입니다. Example var array = [88, 410, 1772, 20] 기수 정렬은 정수의 위치 표기법에 의존합니다. 배열을 최하위 자리의 숫자(1의 자리)를 기준으로 버킷에 나눕니다. 이 버킷들을 순서대로 비운다면, 다음과 같이 일부 정렬된 모습을 볼 수 있습니다. array = [410, 2..

Merge Sort 합병 정렬은 정렬 알고리즘 중 가장 효율적인 알고리즘 중 하나입니다. O(n log n)의 시간 복잡도를 가짐으로, 일반적인 정렬 알고리즘 중 가장 빠른 속도를 가집니다. 합병 정렬은 분할정복(divide and conquer)이라는 아이디어에서부터 시작되었습니다. 이는 큰 문제를 풀기 쉬운 작은 단위로 나눈 뒤, 마지막 결과물에 해결책을 합치는 방법입니다. 합병 정렬은 ‘먼저 분할하고, 나중에 합병’하는 방법입니다. Example 정렬되지 않은 카드 더미가 있다고 가정해봅시다. 1. 먼저, 카드 더미를 반으로 나눕니다. 이제 두 개의 정렬되지 않은 카드 더미가 있습니다. 2. 더 이상 나눌 수 없을 때까지 카드 더미를 나눕니다. 결국엔 각 카드 더미엔 하나의 카드만 남게 될 것입니다..

O(n^2) Sorting Algorithms O(n^2)의 시간 복잡도는 좋은 성능은 아니지만, 이번 장에서 배울 정렬 알고리즘은 이해하기 쉽고 어떠한 경우에서는 유용할 것입니다. 이 알고리즘은 메모리 공간을 O(1)만큼만을 차지하기 떄문에 공간이 효율적입니다. 작은 데이터셋에서는 이러한 정렬이 다른 복잡한 정렬보다 유리합니다. 이번 장에서는 아래의 정렬 알고리즘에 대해 배울 것입니다. 버블 정렬 (Bubble sort) 선택 정렬 (Selection sort) 삽입 정렬 (Insertion sort) 위 들은 모두 comparison-based 정렬 메소드들입니다. 저것들은 less-than 연산과 같이 요소들을 정렬하는 비교하는 메소드에 의존합니다. 이 비교 연산이 불리는 횟수가 정렬 기술의 성능을..

[Gold V] 두 수의 합 - 9024 문제 링크 성능 요약 메모리: 122436 KB, 시간: 508 ms 분류 이분 탐색, 정렬, 두 포인터 제출 일자 2024년 1월 21일 16:49:00 문제 설명 여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수 S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0} 가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2..

[Gold V] 행복 유치원 - 13164 문제 링크 성능 요약 메모리: 100712 KB, 시간: 200 ms 분류 그리디 알고리즘, 정렬 문제 설명 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자. ..

[Silver IV] ATM - 11399 문제 링크 성능 요약 메모리: 69108 KB, 시간: 12 ms 분류 그리디 알고리즘, 정렬 문제 설명 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, ..

[Gold V] 두 용액 - 2470 문제 링크 성능 요약 메모리: 78352 KB, 시간: 64 ms 분류 이분 탐색, 정렬, 두 포인터 문제 설명 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2,..