문제 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라. 예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자. 배열 A = [1, 2, 5, 4, 3..
이코테/정렬
문제 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 학생의 수 N이 입력된다. (1≤N≤100,000) 두 번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다. 출력 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다. 입력 예시 2 홍길동 95 이순신 77 출력 예시 이순신 홍길동 문제 해설 N의 크기가 100,000이기 때문에 시간 복잡도가 O(Nlo..
문제 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. 입력 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1≤N≤500) 둘째 줄부터 N + 1번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다. 출력 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다. 입력 예시 3 5 27 12 출력 예시 27 15 12 문제 해설 N의 범위가 500으로 매우 작고, 수의 범위 또한 100,000이하의 자연수이기 때문에 어떤 방식의 정렬 방법을 사용해도 상관없..
선택, 삽입, 퀵 정렬에 이어서 마지막으로 계수 정렬에 대해 공부해 보자. 계수 정렬(Count Sort) 계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작한다. 계수 정렬은 모든 데이터가 양의 정수일 때 데이터의 개수가 N개, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)의 수행 시간을 보장한다. 하지만 한 가지 조건이 붙는데, 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬이 이러한 특징을 가지는 이유는 계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 배열..
퀵 정렬은 삽입 정렬과 선택 정렬에 비해 훨씬 빠른 정렬 알고리즘이고 많이 사용되는 알고리즘이다. 병합 정렬과 함께 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다. 퀵 정렬 (Quick Sort) 기본 컨셉은 아래와 같다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식을 반복한다. 원리만 이해해도 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다. 퀵 정렬에서는 큰 숫자와 작은 숫자를 교환할 때의 기준을 정하는데 이를 피벗(Pivot)이라고 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 ..
선택 정렬은 매번 가장 작은 것을 선택해서 정렬했다. 선택 정렬은 알고리즘 문제 풀이에 사용하기에는 시간이 매우 오래 걸리기 때문에 다른 접근법이 필요할 듯하다. 삽입 정렬(Insertion Sort) 삽입 정렬은 데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입하는 식으로 정렬을 진행한다. 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 혹은 완전히 정렬되어있을 때는 매우 효율적이다. 반면에 선택 정렬은 데이터가 완전히 정렬되어있어도 시간 복잡도가 같다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는..
가장 기본적인 정렬 방법 중 하나인 선택 정렬에 대해서 알아보자. 선택 정렬 (Selection sort) 기본적인 컨셉은 전체 데이터에서 가장 작은 값을 맨 왼쪽에 넣고, 그다음엔 두 번째로 작은 값을 왼쪽에서 두 번째에 넣는 방식이다. 이런 식으로 반복해주면 점점 정렬이 될 것이고 마지막 데이터는 가만히 두어도 정렬된 상태일 것이다. 위의 그림에서는 총 7개의 데이터를 7-1번만큼 반복해서 정렬을 하였다. 데이터가 N개이면 반복 횟수는 N-1번일 것이다. ##메인 함수 부분## if __name__ == "__main__": array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1, len(arr..
