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

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수가 𝑁, 데이터(양수) 중 최댓값이 𝐾일 때 최악의 경우에도 수행 시간 O(N + K) 를 보장한다 계수 정렬 동작 예시 계수 정렬 소스코드 (Python) # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에..

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

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(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

정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됩니다.

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

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혔습니다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 합니다. 동빈이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있습니다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있습니다. 미로는 반드시 탈출할 수 있는 형태로 제시됩니다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하세요. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다. 미로 탈출: 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색합니다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일합니다. (1, 1) 지점부터 BFS를 수행하..

Python/이코테 2022. 6. 19. 01:39