Gopythor

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다. 다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어입니다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 떄 사용할 수 있습니다. 최적 부..

Python/이코테 2022. 6. 22. 22:49

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 정렬된 배열에서 특정 수의 개수 구하기: 문제 해결 아이디어 내코드 from bisect import bisect_left, bisect_right N, x = map(int, input().split()) arr = list(map(int,input().split())) def sorted(arr, target): left = bisect_left(a..

Python/이코테 2022. 6. 20. 02:57

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm만큼의 길이를 가져갑니다. 손님이 왔을 때 요청한 총 길이가 M일 때..

Python/이코테 2022. 6. 20. 01:52

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해서 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다. O(logN) 이진 탐색의 시간 복잡도 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산횟수는 log₂N 에 비례합니다. 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남습니다. 2단계를 거치면 8개 가량의 데이터만 남습니다. 3단계를 거치면 4개 가량의 데이터만 남습니다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장합니다. 이진 탐색 소스코드: 재귀적..

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

문제 설명 동빈이는 두 개의 배열 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