전체 글
-
동적 계획법 예제2: Longest Common Subsequence 문제Data Structure & Algorithm 2021. 4. 1. 16:50
먼저 문자열의 sub sequence는 문자열에 속한 각 문자의 순서를 유지한 채 만들 수 있는 부분집합입니다. 예를 들어 'AB'라는 문자열이 있는 경우 빈 문자열 ''와 'A', 'B', 'AB'가 모두 seb sequence가 됩니다. 'BA'는 순서가 바뀌었으므로 sub sequence가 되지 않습니다. 두 문자열 X, Y가 있을 때 문자열 간에 공통된 sub sequence 중 가장 긴 sequence의 길이를 구해보도록 합시다. X, Y의 길이가 길어짐에 따라 X의 sub sequence를 뽑아내서 다시 Y의 sub sequence들과 비교하도록 하는 brute force 방식으로 접근하기에는 연산량이 너무나 많아집니다. 이런 경우 보통 동적 계획법을 통해 해결 가능한 문제가 아닌지 의심해야 ..
-
동적계획법 예제1: 정수 리스트(배열)의 최대 부분합 구하기Data Structure & Algorithm 2021. 4. 1. 12:38
다음과 같이 정수 리스트가 주어졌다고 합시다. [-2, -3, 4, -1, -2, 1, 5, -3] 이 때 연속된 부분 리스트의 합 가운데 최대 값은 어떻게 구해야 할까요? 가장 먼저 생각해볼 수 있는 방법은 모든 부분배열을 만들어 그 합을 구한 뒤 가장 큰 값을 구하는 것이 되겠습니다. def maximum_sub_sum_bruteforce(data): max_sub_sum = int() for e in data: if e max_sub_sum: max_sub_sum = sub_sum re..
-
동적 계획법 (Dynamic Programming)Data Structure & Algorithm 2021. 2. 15. 13:06
동적 계획법(Dynamic programming)이란 최적의 하위 구조를 가진 문제를 처리하는 중에 반복되는 연산을 최소화하여 효율적인 알고리즘을 작성할 수 있도록 하는 프로그래밍 기법입니다. 1. 동적 계획법 유형의 문제인지 확인 문제 해결을 위해 완전 탐색 알고리즘을 적용했을 때 비효율적인 경우 내부적으로 동작하는 일련의 반복되는 연산 중 중복되는 동일 연산이 있는지 확인합니다. 만약 중복되는 연산이 있다면 연산 결과를 메모리에 임시로 저장하고 이후 동일 연산은 메모리 내에 미리 계산된 값을 사용하도록 코딩하여 효율적인 코드를 작성합니다. 중복되는 연산이라 함은 n항의 값을 구하기 위해 n-1항 이하의 연산 결과가 반복적으로 사용되는 것을 말합니다. 예를 들어 f(n) = f(n-1) + 1 또는 f..
-
Python 코드 실행 시간 측정 (성능측정)Python 2021. 2. 13. 09:58
python 코드의 순수 연산 시간과 전체 실행 시간을 측정하는 방법은 다음과 같습니다. 1. 순수 연산 시간의 측정 (코드의 성능을 확인): process_time()을 사용 process_time()은 sleep, io와 같은 pending time을 포함하지 않고 순수 연산에 들어간 시간만 측정하기 때문에 연산에 필요한 시간만 확인하고 싶을 때는 process_time()을 사용합니다. import time start_time = time.process_time() # 실행 시간을 측정할 코드 end_time = time.process_time() print(f"time elapsed : {int(round((end_time - start_time) * 1000))}ms") 2. 전체 실행시간의 측..
-
알고리즘의 효율성을 표현하는 Big-O 표기법Data Structure & Algorithm 2021. 2. 12. 09:27
Big-O표기법을 사용하여 알고리즘의 복잡도를 표현할 수 있습니다. 현대에 들어 컴퓨팅 파워가 올라가고 탑재되는 메모리량이 비약적으로 늘어남에 따라 공간 복잡도 보다 시간 복잡도를 줄이는데 비중을 두는 것이 일반적입니다. 따라서 이하 복잡도는 시간 복잡도만 다루도록 하겠습니다. Big-O는 데이터 증가량에 따른 알고리즘의 성능을 예측하기 위한 표기법이므로 상수항은 모두 무시하게 됩니다. (e.g) O(2n + 1) -> O(n), O(3000n² + 10000000) -> O(n²) 대표적인 복잡도와 sample code 1. O(1) - 상수시간 data = [1, 2, 3, 4, 5] def function(n): return n[0] == 1 function(data) 데이터량과 상관없이 항상 일정..
-
이진 탐색(Binary Search)Data Structure & Algorithm 2021. 2. 7. 09:21
정렬되어 있는 데이터에서 특정 데이터가 존재하는지 확인하는 알고리즘입니다. [아이디어] 데이터의 중간 인덱스에 해당하는 값과 찾고자 하는 값을 비교합니다. 중간 인덱스의 값과 찾는 값이 일치하면 데이터가 존재하는 것입니다. 찾고자 하는 값이 중간 인덱스의 값보다 작은 경우는 탐색 범위를 시작인덱스 ~ 중간인덱스 - 1 로 좁혀 다시 탐색을 진행합니다. 찾고자 하는 값이 중간 인덱스의 값보다 큰 경우는 탐색 범위를 중간인덱스 + 1 ~ 끝인덱스로 좁혀 다시 탐색을 진행합니다. 탐색 범위가 인덱스 하나로 좁혀졌으나 해당 인덱스의 값이 찾는 값과 다른 경우는 전체 데이터에서 찾는 값이 없다는 것을 의미합니다. 탐색할 인덱스가 하나 밖에 없는 상태에서 찾는 데이터가 hit하지 않으면 중간 인덱스의 값은 찾고자 ..
-
병합정렬(Merge Sort)Data Structure & Algorithm 2021. 2. 4. 09:04
[아이디어] 정렬하고자 하는 데이터를 분할하되 원소가 하나만 남을 때까지 분할합니다. 정렬할 데이터의 원소가 n개 있다고 할 때 n/2, n/2/2, n/2/2/2 ... 씩 분할해 가다가 원소가 하나만 남게 되는 경우 멈춥니다. 1/2씩 데이터를 분할하였으므로 분할 된 두 데이터를 정렬하여 병합합니다. 두 분할 데이터 각각의 가장 왼쪽 데이터 부터 비교해가며 작은 것이 앞에 오도록 정렬된 데이터로 병합합니다. 2의 과정을 데이터 길이가 n이 될 때까지 반복하면 정렬이 완료됩니다. [특징] 평균 시간복잡도는 O(nlogn)입니다. 최악의 경우에도 O(nlogn)을 보장합니다. 안정적인 시간복잡도를 보장하는 만큼 공간복잡도가 올라가는데, 병합정렬의 공간복잡도는 O(n)입니다. 병합정렬은 안정정렬이므로 동일..
-
계수정렬 (Counting Sort)Data Structure & Algorithm 2021. 1. 30. 08:55
계수는 수를 계산하다는 의미입니다. 계수 정렬에서는 정렬하고자 하는 데이터 안에 동일한 원소가 몇 번 들어 있는지를 계산하여 그 결과를 별도의 배열 또는 리스트에 저장하여 정렬에 사용합니다. hash table과 비슷한 아이디어라고 생각됩니다. [아이디어] 정렬할 데이터를 M이라고 할 때, M에서 가장 큰 값을 V라 합니다. 0 ~ V(총 V+1 개) 사이의 데이터 개수를 저장할 수 있는 배열 또는 리스트 N을 생성하고 N의 각 원소들을 0으로 초기화합니다. 예를 들어 M = [7, 5, 2, 3, 7, 1]이라 할 때 N = [0, 0, 0, 0, 0, 0, 0]이 됩니다. M을 선형으로 탐색하면서 M의 값에 해당하는 N의 인덱스 원소의 값에 1씩 더해갑니다. M의 모든 원소들의 값을 살펴보면 1, 2..