Gopythor

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

Python/이코테 2022. 6. 19. 20:17

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

Python/이코테 2022. 6. 19. 18:29

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다. 퀵 정렬이 빠른 이유: 직관적인 이해 .이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN) 를 기대할 수 있습니다 너비 X 높이 = 𝑁 × 𝑙𝑜𝑔𝑁 = 𝑁𝑙𝑜𝑔𝑁 퀵 정렬의 시간 복잡도 퀵 정렬은 평균의 경우 O(NlogN) 의 시간 복잡도를 가집니다. 하지만 최악의 경우 O(N²) 의 시간 복잡도를 가집니다. 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬..

Python/이코테 2022. 6. 19. 17:35

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 선택정렬에 비해 구현 난이도가 높은 편이지만 실행시간 측면에서 더 효율적으로 동작합니다. 삽입 정렬 소스코드 (Python) arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(arr)): for j in range(i, 0, -1): #(start, end, step) if arr[j] < arr[j -1]: # 한 칸씩 왼쪽으로 이동 arr[j], arr[j -1] = arr[j -1], arr[j] else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 break 삽입 정렬의 시간 복잡도 삽입 정렬의 시간 복잡도는 O(N²)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어..

Python/이코테 2022. 6. 19. 04:02

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 선택 정렬 동작 예시 선택 정렬 소스코드(Python) arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(arr)): if arr[min_index] > arr[j]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] # 스와프 print(arr) 선택 정렬의 시간 복잡도 선택 정렬은 n번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다. 구현방식에 따라서 사소한 오차는 있을 ..

Python/이코테 2022. 6. 19. 03:22

문제 설명 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다. 제한 조건 strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다. 입출력 예stringsnreturn ["sun", "bed"..

Go/Programmers 2022. 5. 29. 22:07

QuickSort Divide and conquer algorithm After determining the pivot, the position of the pivot is confirmed and aligned Quicksort has many variations based on pivot. When comparing numbers, the pivot is the standard. The speed varies depending on the position of the pivot. There are left pivot, right pivot, middle pivot, and random pivot. O(n²) in the worst case Range, Criteria, Compare, Swap qui..

Go/Study record 2022. 3. 17. 18:44

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers. Return any array that satisfies this condition. Example 1: Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.Example 2: Input: nums = [0] Output: [0]Constraints: 1

Go/Leet Code 2022. 3. 15. 01:45